akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<cstring>
#define M 108
int dp[M*10][5000];
char map1[M][M];
int a[M];
int b[M*100];
int c[M];
int n,m;
int my_hash[M];
int o[4][2]={
    0,-1,
    1,0,
    0,1,
    -1,0
};
int min(int x,int y){
    if(x>y) return y;return x;
}
int max(int x,int y){
    if(x<y) return y;return x;
}
int main(){
    int sp,tmax;
    while(~scanf("%d%d",&sp,&tmax)&&(sp+tmax)){
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)scanf("%s",&map1[i]);
        int n1;scanf("%d",&n1);
        for(int i=0;i<n1;i++){
            char str[100];
            int t1;scanf("%s%d",str,&t1);
            my_hash[str[0]-'A']=t1;
        }
        int m1;scanf("%d",&m1);
        int sx=0,sy=0;
        int num=1;
        memset(b,0,sizeof(b));
        for(int i=0;i<m1;i++){
            char str[20];int m2;
            scanf("%s%d",str,&m2);
            int oo;
            if(str[0]=='U') oo=3;
            else if(str[0]=='R') oo=2;
            else if(str[0]=='D') oo=1;
            else if(str[0]=='L') oo=0;
            for(int i=0;i<m2;i++){
                sx=sx+o[oo][0];
                sy=sy+o[oo][1];
                int t1=map1[sx][sy]-'A';
                b[num++]=my_hash[t1];
            }
        }
//        puts("@@@@@@@@@");
        int n2;scanf("%d",&n2);
        for(int i=0;i<n2;i++){
            scanf("%d",&c[i]);
        }
//        for(int i=0;i<num;i++){
//            printf("%d ",b[i]);
//        }
//        printf("%d!!!\n",num);
//        puts("");
        memset(dp,0,sizeof(dp));
        int t2=1<<n2;
        t2--;
//        printf("%d\n",t2);
        dp[0][t2]=sp;
        for(int i=0;i<num-1;i++){
            for(int j=t2;j>=0;j--){
                if(dp[i][j]<=0) continue;
                if(dp[i][j]<=b[i+1]){
//                    printf("%d!!!!!\n",b[i+1]);
                    for(int k=0;k<n2;k++){
                        if(j&(1<<k)){
                            int tt=j^(1<<k);
                            int t1=min(tmax,dp[i][j]+c[k]);
                            dp[i][tt]=max(t1,dp[i][tt]);
                        }
                    }
                }
                else{
                    int t1=dp[i][j]-b[i+1];
                    dp[i+1][j]=max(dp[i+1][j],t1);
                }
            }
        }
        int flag=0;
        for(int i=0;i<=t2;i++){
            if(dp[num-1][i]>0) flag=1;
//            printf("%d  !!\n",dp[num-1][i]);
        }
        if(flag) puts("YES");else puts("NO");
    }
    return 0;
}
/*
1 10
3 3
AAA
CAA
CBC
3
A 0
B 10000
C 9
3
D 2
R 1
U 2
5
4
4
4
4
4
*/

Measured memory_bytes: 22172
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int main()
{
   long H;
   cin >> H;
   if(H==1){
       cout << H;
   }
   else {
       long count = 0;
       long i;
       for( i = 1;;){
           H=H/2;
           if(H==1){
               break;
           }
           else{
               i = 2*i;
               i++;
           }
       }
       cout << 2*i+1;
   }
   return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int K = scan.nextInt();
        long[] w = new long[N];
        long[] d = new long[N];
        for(int i=0;i<N;++i){
            w[i] = scan.nextLong();
            d[i] = scan.nextLong();
        }
        
        long left =0;
        long right = 2000000000000000000L;
        while(true){
            long X = (left+right)/2;
            long k = 0;
            for(int i=0;i<N;++i){
                if(X>=w[i])k += (X-w[i])/d[i] +1;
            }
            if(k >=K)right = X;
            else left = X;
            if(right-left == 1)break;
        }
        System.out.println(right);
    }
}

Measured memory_bytes: 96388
def main():
    tmp = input()
    ls = list(map(int, input().split(' ')))
    count = 0
    
    for i in range(len(ls)):
        minj = i
        
        for j in range(i, len(ls)):
            if ls[j] < ls[minj]:
                minj = j
        ls[i], ls[minj] = ls[minj], ls[i]

        if minj != i:
            count += 1

    print(' '.join(map(str,ls)))
    print(count)
    
if __name__ == '__main__':
    main()

Measured memory_bytes: 7704
#include <stdio.h>
#define M 10000

int main(void){
	
	int n,m,A[M];
	int sum = 0;
	scanf("%d %d",&n,&m);
	for(int i = 0; i < m; i++){
		scanf("%d", &A[i]);
		sum += A[i];
	}
	if(sum <= n) printf("%d",n-sum);
	else printf("-1");
	
	
}

Measured memory_bytes: 1772
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)

int N;
LL A[100010];
const LL mod = 1e9 + 7;

LL inv(LL x){
	LL ret = 1;
	for(LL i = mod - 2 ; i > 0 ; i /= 2){
		if(i&1) (ret *= x) %= mod;
		x = x * x % mod;
	}
	return ret;
}

int main(){
	cin >> N;
	repp(i,0,N) cin >> A[i];
	LL fctn = 1;
	repp(i,1,N+1) (fctn *= i) %= mod;
	LL s = 0;
	repp(i,0,N) s += 2 * A[i];
	s = s % mod;
	LL ans = 0;
	repp(i,0,N){
		(ans += (i?s:s*inv(2)%mod) * inv(i+1)) %= mod;
		s = (s + mod - A[i] + mod - A[N-1-i]) % mod;
	}
	cout << ans * fctn % mod << endl;
	return 0;
}


Measured memory_bytes: 1024
import sys
 
chash = {}
for i in range( ord( 'a' ), ord( 'z' )+1 ):
    chash[ chr( i ) ] = 0
 
for line in sys.stdin:
    for i in range( len( line ) ):
        if line[i].isalpha():
            chash[ line[i].lower() ] += 1
 
for i in range( ord( 'a' ), ord( 'z' )+1 ):
    print( "{:s} : {:d}".format( chr( i ), chash[ chr( i ) ] ) )

Measured memory_bytes: 4240
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

int main() {
    string s;
    cin >> s;
    set<int> se;
    for(int i=0;i<s.size();i++){
        se.insert(s[i] -'a');
    }
    if(se.size()==3){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    int W,H,N;
    cin >> W >> H >> N;
    vector<int> x(N),y(N),a(N);
    for(int i=0;i<N;i++){
        cin >> x[i] >> y[i] >> a[i];
    }
    int wm=0,wM=W,hm=0,hM=H;
    for(int i=0;i<N;i++){
        if(a[i]==1){
            if(x[i]>wm) wm=x[i];
        } 
        if(a[i]==2){
            if(x[i]<wM) wM=x[i];
        } 
        if(a[i]==3){
            if(y[i]>hm) hm=y[i];
        } 
        if(a[i]==4){
            if(y[i]<hM) hM=y[i];
        } 
    }
    int ans=0;
    if((wM-wm)>0 &&(hM-hm)>0)ans=(wM-wm)*(hM-hm);
    cout << ans <<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;

char getmaxchar(string str, char ref)
{
  char tmp = str[0];
  for (auto c : str) {
    if (c > ref)
      tmp = min(tmp, c);
  }
  return tmp;
}


int main()
{
  string input;
  cin >> input;
  int full_character = 0;

  char box[26];
  for (int i=0; i<26; i++)
    box[i] = -1;

  for (int j=0; j<input.length(); j++) {
    int index = input[j] - 'a';
    if (box[index] != -1) {
      cout << "Already input! box[" << index << "] : " << 'a'+index << endl;
      exit(1);
    } else {
      box[index] = j;
    }
  }


  if (input.length() == 26) {

    for (int ind=input.length(); ind>0; ind--) {

      if (input[ind] >= input[ind-1]) {
        int start = ind;
        int length = input.length()-(ind);

        cout << input.substr(0, ind-1) << getmaxchar(input.substr(start, length), input[ind-1]) << endl;
        //cout << "debug: refchar : " << input[ind-1] << endl;
        //cout << "debug: strtchar: " << input[ind-1] << endl;
        return 0;
      }

    }

    cout << -1 << endl;
    return 0;
  } else {
    for (int i = 0; i < 26; i++) {
      if (box[i] == -1) {
        //cout << "First not used character: " << (char)(i+'a') << endl;
        cout << input << (char)(i+'a') << endl;
        return 0;

      }
    }
  }

}

Measured memory_bytes: 256
N, M = map(int, input().split())

dp = [1, 2]
A = [int(input()) for _ in range(M)]
if M != 0:
    if M >= 2 and A[0] == 1 and A[1] == 2:
        dp = [0, 0]
    elif A[0] == 1:
        dp = [0, 1]
    elif A[0] == 2:
        dp = [1, 0]
else:
    A = [0]

MOD = 1000000007

if N == 1:
    print (1)
elif N == 2:
    print (dp[-1])
else:
    cnt = 0
    for n in range(2, N):
        while(cnt < M - 1 and A[cnt] < n + 1):
            cnt += 1
        if A[cnt] == n + 1:
            dp[0] = dp[1]
            dp[1] = 0
        else:
            new_val = (max(dp[0], 0) + max(dp[1], 0)) % MOD
            dp[0] = dp[1]
            dp[1] = new_val

    print (dp[-1])


Measured memory_bytes: 7080
#include <algorithm>
#include <iostream>
#include <string>

using namespace std;

int main() {
  int n;
  string s;
  cin >> n >> s;
  int r = 0;
  int b = 0;
  for (char c : s) {
    if (c == 'R')
      ++r;
    else
      ++b;
  }
  if (r > b) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }

  return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h> 
 
#define INF (1<<31)//INT_MAX/2
#define MOD 1000000007
 
using ll  = long long;
using ull = unsigned long long;
 
int main(int argc, char *argv[])
{
    int N;
    std::cin >> N;

    std::vector<int> a(N);
    for (int i = 0; i < N; i++) {
        std::cin >> a[i];
    }

    bool flag = false;
    for (int i = 0; i < N; i++) {
        if (a[i] % 2 != 0) {
            flag = true;
        }
    }

    if (flag) {
        std::cout << "first" << std::endl;
    } else {
        std::cout << "second" << std::endl;
    }
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;

int main() {
    ll A, B, C, D;
    cin >> A >> B >> C >> D;
    REP(i, 100){
        C -= B;
        if(C < 1) {
            cout << "Yes" << endl;
            break;
        } else if (A < 1) {
            cout << "No" << endl;
            break;
        }
        A -= D;
        if(C < 1) {
            cout << "Yes" << endl;
            break;
        } else if(A < 1) {
            cout << "No" << endl;
            break;
        }
    }
}

Measured memory_bytes: 3616
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include <cmath>
#include <limits>
#include<set>
#include <iomanip>
#include <queue>
#include <string>
#pragma GCC optimize("Ofast")
using namespace std;
const long long INF=20000000000;
//setprecision(2) <<

const int MOD = 1000000007;

long long max(long long a,long long b){
	if(a<b)return b;
	else return a;	
}
long long min(long long a,long long b){
	if(a>b)return b;
	else return a;	
}
long long gcd(long long a,long long b){
	if(a<b)swap(a,b);
	if(a%b==0)return b;
	else return gcd(a%b,b);
}

long long lcm(long long a,long long b){
	return a*b/gcd(a,b);
}

long long com(long long n,long long k){
	
}
long long getDigit(long long n){
	if(n==1)return 1;
	else return log10(n)+1;
}

class Point{
public:
	long long x;
	long long y;
};


int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int a,b,w;
	cin>>w>>a>>b;
	if(a+w<b){
		cout<<b-a-w<<endl;
		return 0;
	}
	if(b+w<a){
		cout<<a-b-w<<endl;
		return 0;
	}
	cout<<0<<endl;
	
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,s,n) for (int i = (s); i < (n); ++i)
#define rrep(i,n,g) for (int i = (n)-1; i >= (g); --i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define len(x) (int)(x).size()
#define dup(x,y) (((x)+(y)-1)/(y))
#define append push_back
#define Field(T) vector<vector<T>>
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
  int n;
  cin >> n;
  int ans = dup(n,111) * 111;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3592
#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> h(100000);
vector<int> cost(100000);

int ans(int n)
{
    if (cost.at(n) != -1)
        return cost.at(n);
    cost.at(n) = min(ans(n - 1) + abs(h.at(n) - h.at(n - 1)), ans(n - 2) + abs(h.at(n) - h.at(n - 2)));
    return cost.at(n);
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> h.at(i);
        cost.at(i) = -1;
    }
    cost.at(0) = 0;
    cost.at(1) = abs(h.at(1) - h.at(0));
    cout << ans(n - 1) << endl;
}

Measured memory_bytes: 4096
/* Never Say Die */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <bitset>
using namespace std;
typedef long long LL;
typedef double D;
typedef pair<int, int> pii;
#define mp(a, b) make_pair(a, b)
#define fir first
#define sec second
inline int min(int a, int b) {return a < b ? a : b;}
inline int max(int a, int b) {return a > b ? a : b;}
int ch = 0;
template <class T> inline void read(T &a) {
	bool f = 0; a = 0;
	while (ch < '0' || ch > '9') {if (ch == '-') f = 1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {a = a * 10 + ch - '0'; ch = getchar();}
	if (f) a = -a;
}


int n;
int a[100005];

int main() {
	read(n);
	for (int i = 1; i <= n; i++) read(a[i]);
	sort(a + 1, a + n + 1);
	if (a[1] == a[n]) {
		if (a[1] != n - 1 && a[1] * 2 > n) puts("No");
		else puts("Yes");
	}
	else {
		if (a[n] - a[1] > 1) puts("No");
		else {
			int l = 1, r;
			while (a[l + 1] == a[1]) l++;
			r = n - l;
			if (r < 2) puts("No");
			else {
				if (r / 2 + l >= a[n] && l < a[n]) puts("Yes");
				else puts("No");
			}
		}
	}

	return 0;
}




Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD 1000000007
ll fast_expo(ll x,ll p)
{if(p==0) return 1;
else if(p%2==0){ ll t=fast_expo(x,p/2)%MOD;return (t*t)%MOD;} else return (x*(fast_expo(x,p-1))%MOD)%MOD;}

int main()
{
     int n;
     cin>>n;
     int a[n],b[n],c[n];
     int dp[n][3];
     for(int i=0;i<n;i++)
     {
          cin>>a[i]>>b[i]>>c[i];
     }
     dp[0][0]=a[0];
     dp[0][1]=b[0];
     dp[0][2]=c[0];
     for(int i=1;i<n;i++)
     {
          dp[i][0]=max(dp[i-1][1]+a[i],dp[i-1][2]+a[i]);
          dp[i][1]=max(dp[i-1][0]+b[i],dp[i-1][2]+b[i]);
          dp[i][2]=max(dp[i-1][0]+c[i],dp[i-1][1]+c[i]);
     }
     cout<<max({dp[n-1][0],dp[n-1][1],dp[n-1][2]});
}


Measured memory_bytes: 2688
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <map>

//#include <bits/stdc++.h>
using namespace std;
#define print(x) cout<<(x)<<endl
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define ll long long int
#define pb push_back

int main() {
  int a, b, c;
  cin >> a >> b >> c;  

  if(a+b >= c) print("Yes");
  else print("No");
}


Measured memory_bytes: 256
//by yjz
#include<bits/stdc++.h>
using namespace std;
#define FF first
#define SS second
#define PB push_back
#define MP make_pair
typedef long long ll;
const int Imx=2147483647;
const int mod=1000000007;
const ll Lbg=2e18;
//My own input/output stream
#define geti(x) x=getnum()
#define getii(x,y) geti(x),geti(y)
#define getiii(x,y,z) getii(x,y),geti(z)
#define puti(x) putnum(x),putsp()
#define putii(x,y) puti(x),putnum(y),putsp()
#define putiii(x,y,z) putii(x,y),putnum(z),putsp()
#define putsi(x) putnum(x),putendl()
#define putsii(x,y) puti(x),putnum(y),putendl()
#define putsiii(x,y,z) putii(x,y),putnum(z),putendl()
inline ll getnum()
{
	register ll r=0;register bool ng=0;register char c;c=getchar();
	while(c!='-'&&(c<'0'||c>'9'))c=getchar();
	if(c=='-')ng=1,c=getchar();
	while(c>='0'&&c<='9')r=r*10+c-'0',c=getchar();
	if(ng)r=-r;return r;
}
template <class T> inline void putnum(T x)
{
	if(x<0)putchar('-'),x=-x;
	register short a[20]={},sz=0;
	while(x>0)a[sz++]=x%10,x/=10;
	if(sz==0)putchar('0');
	for(int i=sz-1;i>=0;i--)putchar('0'+a[i]);
}
inline void putsp(){putchar(' ');}
inline void putendl(){putchar('\n');}
inline char mygetchar(){register char c=getchar();while(c==' '||c=='\n')c=getchar();return c;}
int n,m;
vector<int>con[100111];
vector<int>ans,ans2;
bool vis[100111];
void dfs(int x,bool f)
{
	vis[x]=1;if(f)ans2.PB(x);else ans.PB(x);
	for(auto u:con[x])
	{
		if(!vis[u])
		{
			dfs(u,f);
			if(x!=1||f)return;
			f=1;
		}
	}
}
int main()
{
	getii(n,m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		getii(x,y);
		con[x].PB(y);
		con[y].PB(x);
	}
	dfs(1,0);
	putsi(ans.size()+ans2.size());
	reverse(ans2.begin(),ans2.end());
	for(int i=0;i<ans2.size();i++)puti(ans2[i]);
	for(int i=0;i<ans.size();i++)puti(ans[i]);
	return 0;
}

Measured memory_bytes: 11128
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#define _USE_MATH_DEFINES
#include <cmath>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <iomanip>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-8;
const int MOD = 1000000007;
// const int MOD = 998244353;
const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
// const int dy[] = {1, 1, 0, -1, -1, -1, 0, 1},
//           dx[] = {0, -1, -1, -1, 0, 1, 1, 1};

struct IOSetup {
  IOSetup() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    cerr << fixed << setprecision(10);
  }
} iosetup;
/*-------------------------------------------------*/
int main() {
  vector<int> win{300000, 200000, 100000};
  int x, y; cin >> x >> y; --x; --y;
  int ans = 0;
  if (x < 3) ans += win[x];
  if (y < 3) ans += win[y];
  if (x == 0 && y == 0) ans += 400000;
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int main() {
  int N, K;
  cin >> N >> K;
  vector<int> A(N);
  for(int i = 0; i < N; i++){
    cin >> A.at(i);
  }
  
  for(int i = 0; i < N - K; i++){
    if(A.at(K + i) > A.at(i)){
      cout << "Yes" << endl;
    }
    else{
      cout << "No" << endl;
    }
  }
      
}

Measured memory_bytes: 4048
import sys;
import math;
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def get_array(): return list(map(int, sys.stdin.readline().strip().split()))
def get_string(): return sys.stdin.readline().strip()

N,W = get_ints();
arr = [];
for i in range(N):
    tarr = get_array();
    arr.append(tarr);
dp = [[0 for i in range(W+1)] for i in range(N+1)];
for i in range(1,N+1):
    for j in range(1,W+1):
        if(j-arr[i-1][0])>=0:
            dp[i][j]=max(dp[i-1][j],arr[i-1][1]+dp[i-1][j-arr[i-1][0]]);
        else:
            dp[i][j]=dp[i-1][j]


print(dp[N][W]);
    


Measured memory_bytes: 218200
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 266666;const ll inf=1e16;
int n,a[N],fa[N];vector<Pii>e[N];ll res;
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
struct node{
	ll v1,v2;int p1,p2;
	inline void updone(ll v, int p){
		if(v<v1){
			if(p1!=p)v2=v1,p2=p1;
			v1=v;p1=p;
		}
		else if(v<v2){
			if(p1!=p)v2=v,p2=p;
		}
	}
	inline void upd(const node &a){
		updone(a.v1,a.p1);updone(a.v2,a.p2);
	}
}f[N],g[N];
inline node add(node a, int b){a.v1+=b;a.v2+=b;return a;}
pair<ll,int>ans[N];
void dfs1(int u, int Fa){
	rep(i,0,SZ(e[u])-1)if(e[u][i].fi!=Fa)
		dfs1(e[u][i].fi,u),f[u].upd(add(f[e[u][i].fi],e[u][i].se));
	umin(ans[fa[u]],f[u].p1!=fa[u]?make_pair(f[u].v1+a[u],f[u].p1):make_pair(f[u].v2+a[u],f[u].p2));
	f[u].updone(a[u],fa[u]);
}
void dfs2(int u, int Fa){
	umin(ans[fa[u]],g[u].p1!=fa[u]?make_pair(g[u].v1+a[u],g[u].p1):make_pair(g[u].v2+a[u],g[u].p2));
	g[u].updone(a[u],fa[u]);
//	static int s[N];int len=0;
//	rep(i,0,SZ(e[u])-1)if(e[u][i].fi!=Fa)s[++len]=e[u][i].fi;
	node qz=(node){inf,inf,0,0};
	rep(i,0,SZ(e[u])-1)if(e[u][i].fi!=Fa)
		g[e[u][i].fi].upd(add(qz,e[u][i].se)),qz.upd(add(f[e[u][i].fi],e[u][i].se));
	node hz=(node){inf,inf,0,0};
	per(i,SZ(e[u])-1,0)if(e[u][i].fi!=Fa)
		g[e[u][i].fi].upd(add(hz,e[u][i].se)),hz.upd(add(f[e[u][i].fi],e[u][i].se));
	rep(i,0,SZ(e[u])-1)if(e[u][i].fi!=Fa)g[e[u][i].fi].upd(add(g[u],e[u][i].se));
	rep(i,0,SZ(e[u])-1)if(e[u][i].fi!=Fa)dfs2(e[u][i].fi,u);
}
int main() {
	read(n);rep(i,1,n)read(a[i]);
	rep(i,1,n-1){
		int u,v,w;read(u);read(v);read(w);
		e[u].pb(Pii(v,w));e[v].pb(Pii(u,w));
	}
	rep(i,1,n)fa[i]=i;
	while(1){
		int sum=0;rep(i,1,n)sum+=find(i)==i;if(sum==1)break;
		rep(i,1,n)ans[i]=make_pair(inf,i);
		rep(u,1,n)f[u]=g[u]=(node){inf,inf,0,0};
		dfs1(1,0);dfs2(1,0);
	//	rep(i,1,n)printf("%d:%d %lld\n",i,ans[i].se,ans[i].fi);puts("");
		rep(i,1,n)if(find(i)==i&&ans[i].se>=1&&ans[i].se<=n){
			int u=find(i),v=find(ans[i].se);
			if(u!=v)res+=ans[i].fi,fa[u]=v;
		}
	}
	cout<<res;return 0;
}


Measured memory_bytes: 56192
if __name__ == '__main__':
    from sys import stdin
    input = stdin.readline

    N = 100
    WHITE = 0
    GRAY = 1
    BLACK = 2

    M = [[0]*N for _ in range(N)]
    color = [WHITE]*N  # colorの初期化は最初に行っておく。
    d = [0]*N
    f = [0]*N

    def dfs_visit(u):
        global tt
        color[u] = GRAY
        tt += 1
        d[u] = tt # 最初の訪問
        for v in range(n):
            if M[u][v] == 0:
                continue
            if color[v] == WHITE:
                dfs_visit(v)
        color[u] = BLACK
        tt += 1
        f[u] = tt # 訪問の完了

    def dfs():
        global tt
        tt = 0

        for u in range(n):
            if color[u] == WHITE:
                # 未訪問のuを始点として深さ優先探索
                dfs_visit(u)
        for u in range(n):
            print(str(u+1) + ' ' + str(d[u]) + ' ' + str(f[u]))

    n = int(input())
    for _ in range(n):
        u, k, *vv = input().split()
        u = int(u)-1  # 0オリジンにする
        k = int(k)    # kは使わない
        for v in vv:
            v = int(v)-1
            M[u][v] = 1
    dfs()



Measured memory_bytes: 5748
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
constexpr int di[] = { 0, 1, 0, -1 }, dj[] = { 1, 0, -1, 0 };
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define SORT(v) sort((v).begin(), (v).end())
#define SORTR(v) sort((v).rbegin(), (v).rend())
#define all(v) (v).begin(), (v).end()
#define N 100005
constexpr ll inf = 100000000000000;
/*cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);*/


bool check(int mid){

  return false;
}

ll serch(ll ok,ll ng) {
	while (abs(ok-ng) > 1) {
		ll mid = (ok + ng) / 2;
		if (check(mid))ok = mid;
		else ng = mid;
	}
	return ok;
}

int main(){
  ll k,x;
  cin>>k>>x;
  if(k*500>=x){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
  return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <vector> 
#include <algorithm>

#include <boost/range/algorithm.hpp>


using namespace std;
namespace brange = boost::range;

using u8t = uint8_t;
using u16t = uint16_t;
using u32t = uint32_t;
using u64t = uint64_t;

int main(void)
{
  int W, H;
  cin >> W >> H;
  vector<pair<u64t, bool>> c(W + H);
  for(int i = 0; i < W; i++){
    int t;
    cin >> t;
    c[i] = {t, true};
  }
  for(int i = 0; i < H; i++){
    int t;
    cin >> t;
    c[i + W] = {t, false};
  }

  brange::sort(c, [](auto const& a, auto const& b){return a.first < b.first;});

  int a = W + 1, b = H + 1;
  u64t rslt = 0;
  for(int i = 0; i < c.size(); i++){
    if(c[i].second){
      rslt += c[i].first * b;
      --a;
    }else{
      rslt += c[i].first * a;
      --b;
    }
  }
cout << rslt << endl;
return 0;
}


Measured memory_bytes: 3960
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<functional>
#include<fstream>
#include<utility>
#define rep(N) for (int i = 0; i < N; i++)
#define For(i, N) for (i = 0; i < N; i++)
#define re return 0

using namespace std;
using ll = long long int;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vb = vector<bool>;
using vs = vector<string>;
using pii = pair<int, int>;
using pis = pair<int, string>;

template<typename T>
void say(T s) {
	cout << s << endl;
}

int main() {
	int N, Y;
	int i, j;
	cin >> N >> Y;
	for (i = 0; i <= N; i++)
		for (j = 0; j <= N - i; j++) {
			if (10000 * i + 5000 * j + 1000 * (N - i - j) == Y) {
				cout << i << " " << j << " " << N - i - j << endl;
				re;
			}
		}
	say("-1 -1 -1");
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, a, b) for(int i = a; i < b; i++)
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  FastIO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef long long int lli;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }

int dx[] = {1, 1, 0, -1, -1, -1, 0, 1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};

ll mod = 1000000007;

ll modpow(ll x, ll n){
    if ( n == 0 ) return 1;
    if (n % 2 == 0){
        ll half = modpow(x, n/2);
        return half * half % mod;
    }else{
        return x * modpow(x, n-1) % mod;
    }
}

ll choose(ll n, ll r){
    ll mul = 1;
    ll div = 1;
    for(int i = 0; i < r; i++){
        mul *= n - i;
        div *= i + 1;
        mul %= mod;
        div %= mod;
    }
    return mul * modpow(div, mod-2) % mod;
}

int main(){
    ll x;
    ll y;
    cin >> x >> y;
    if ((x + y) % 3 != 0) {
        cout << 0 << endl;
        return 0;
    }
    ll n = (x + y) / 3;
    x -= n;
    y -= n;
    if (x < 0 || y < 0){
        cout << 0 << endl;
        return 0;
    }
    ll ans = choose(x + y, x);
    cout << ans << endl;
}

Measured memory_bytes: 3600
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please


int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);


	int N, M;
	cin >> N >> M;

	int A[31] = {};
	rep(i, N) {
		int K;
		cin >> K;

		rep(i, K) {
			int a;
			cin >> a;

			A[a]++;
		}
	}

	int kotae = 0;
	rep1(i, M) {
		if (A[i] == N) kotae++;
	}

	co(kotae);

	Would you please return 0;
}

Measured memory_bytes: 256
import java.util.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main {

	int INF = 1 << 28;

	void run() {
		Scanner sc = new Scanner(System.in);
		for(;;) {
			int n= sc.nextInt();
			if(n == 0) break;
			long a[] = new long[n+1];
			for(int i=0;i<n;i++) a[i] = sc.nextInt();
			a[n] = 0;
			long sum = 0;
			sort(a);
			for(int i=0;i<n;i++) {
				sum += a[i];
				a[i+1] += a[i];
			}
//			debug(a);
			System.out.println(sum);
		}
	}

	public static void main(String[] args) {
		new Main().run();
	}

	void debug(Object... os) {
		System.err.println(Arrays.deepToString(os));
	}
}

Measured memory_bytes: 13000
#include<bits/stdc++.h>
using namespace std;

int n;
long long psum[3003], f[3003];

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; ++i)
		cin >> psum[i], f[i] = psum[i], psum[i] += psum[i - 1];
	for(int i = 2; i <= n; ++i) {
		int ed = n - i + 1;
		for(int j = 1; j <= ed; ++j)
			f[j] = psum[j + i - 1] - psum[j - 1] - min(f[j], f[j + 1]);
	}
	cout << f[1] * 2 - psum[n] << endl;
	return 0;
}

Measured memory_bytes: 256
import copy
import math
import string
import heapq
import bisect
import sys
sys.setrecursionlimit(10**7)

K,N = map(int,input().split())
A = list(map(int,input().split()))

a = min(abs(A[N-1]-A[0]),K-abs(A[N-1]-A[0]))
for i in range(N-1):
    a = max(a,abs(A[i]-A[i+1]))
print(K-a)

Measured memory_bytes: 26236
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <string>
#include <bitset>
#include <deque>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define print(x) cout<<(x)<<endl
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define RREP(i, n) for (int i = (n)-1; i >= 0; --i)
#define INF10 1001001001 
#define INF5 100000
#define EPS 1e-10


int main() {
	int N, X; cin >> N >> X;
	vector<int>L(N);
	REP(i, N)cin >> L[i];
	int cnt = 1;
	int d = 0;
	REP(i, N) {
		d = d + L[i];
		if (d <= X)cnt++;
	}
	print(cnt);


	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<set>
#include<map>
#include<vector>

using namespace std;
const int maxn = 1e4 + 7;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
typedef long long ll;
#define pi 3.1415926535
// luxi

ll n, sum;
int main(){
	cin >> n;
	for(ll i = 1; i <= n; i++){
		if(i % 3 != 0 && i % 5 != 0){
			sum += i;
		}
	}
	cout << sum << endl;
}

Measured memory_bytes: 3600
n,k = map(int,input().split())
v = list(map(int,input().split()))
r = min(n,k)
get = []
M = 0
for i in range(r+1):
  for j in range(i+1):
    get += v[0:j] + v[(n-i+j):n]
    get.sort()
    R = min(i,k-i)
    for cd in range(0,R+1):
      M = max(M,sum(get[cd:i]))
    get = []
print(M)

Measured memory_bytes: 3064
using System;
using System.Collections.Generic;//list用
using System.Text;//StringBuilder用
using System.Collections;
using System.Linq;
class Program
{
static int result;
static List<int> s=new List<int>();
  static List<int> t=new List<int>();
  static int N;
  
    static void Main()
    {
      StringBuilder sb = new StringBuilder();
      N=int.Parse(Console.ReadLine());
      Read();
for(int i=0;i<N;i++){if(i%2==0){result+=s[i];}else{result-=s[i];}}
t.Add(result/2);sb.Append((2*t[0]).ToString() + " ");
      for(int i=0;i<N-1;i++){t.Add(s[i]-t[i]);sb.Append((2*t[i+1]).ToString() + " ");}
      Console.WriteLine(sb);
      
      
                    //Console.WriteLine(result.ToString());
    }

static void Read()
{
  string[] tmp=Console.ReadLine().Split(' ');
for(int i=0;i<N;i++){s.Add(int.Parse(tmp[i]));}
}
}

Measured memory_bytes: 31320
import itertools
N=int(input())
P=list(map(int,input().split()))
Q=list(map(int,input().split()))

Q_list=list(itertools.permutations(sorted(Q)))
for i,q in enumerate(Q_list):
  q=list(q)
  if q==P:
    a=i
  if q==Q:
    b=i
print(abs(a-b))

Measured memory_bytes: 8052
#include <stdio.h>
#include <string.h>

int main(void){
	int a, b, n, i, j, k, x[40], y[40], m[16][16];
	while(1){
		scanf("%d%d",&a,&b);
		if(a == 0 && b == 0) break;
		scanf("%d",&n);
		memset(m,0,sizeof(m));
		m[0][0] = 1;
		for(i = 0;i < n;i++){
			scanf("%d%d",&x[i],&y[i]);
			x[i]--,y[i]--;
		}
		for(i = 0;i < a;i++){
			for(j = 0;j < b;j++){
				if(j != b - 1){
					for(k = 0;k < n;k++)
						if(i == x[k] && j + 1 == y[k]) break;
					if(k == n)
						m[i][j + 1] += m[i][j];
				}
				if(i != a - 1){
					for(k = 0;k < n;k++)
						if(i + 1 == x[k] && j == y[k]) break;
					if(k == n)
						m[i + 1][j] += m[i][j];
				}
			}
		}
		printf("%d\n",m[a - 1][b - 1]);
	}
	return 0;
}

Measured memory_bytes: 1028
#include <stdio.h>

int main(void) {
	int num;
	int count;
	while(1) {
		scanf("%d",&num);
		if(num==0)break;
		for(count=0;num>1;count++)num=num%2?num*3+1:num/2;
		printf("%d\n",count);
	}
	return 0;
}

Measured memory_bytes: 0
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val n = sc.nextInt()
    val k = sc.nextInt()
    val l = (0 until n).map { sc.nextInt() }
    println(answer067bAlt(n, k, l))
}

fun answer067bAlt(n: Int, k: Int, l: List<Int>): Int {
    val sortedL: MutableList<Int> = l.sortedDescending() as MutableList<Int>
    var res = 0
    for (index in 0 until k) {
        res += sortedL[index]
    }
    return res
}

Measured memory_bytes: 35796
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n];
		for(int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
		}
		int ans = a[0];
		for(int i = 1; i < n; i++) {
			ans = gcd(ans, a[i]);
		}
		System.out.println(ans);
	}
	static int gcd (int a, int b) {
		int temp;
		while((temp = a%b)!=0) {
			a = b;
			b = temp;
		}
		return b;
	}
}

Measured memory_bytes: 52416
#include <bits/stdc++.h>
using namespace std;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    vector<int> vi;
    for (int i = 0; i < n; i++)
    {
        int l;
        cin >> l;
        vi.push_back(l);
    }
    sort(vi.begin(), vi.end());
    int ans = accumulate(vi.begin() + (n - k), vi.end(), 0);
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <unordered_map> 
#include <unordered_set>
#include <functional>

using namespace std;

typedef pair<long long int, long long int> P;
typedef tuple<int, int, int> T;

long long int INF = 1e18;
long long int MOD = 1e9 + 7;

long long int GCD(long long int a, long long int b){
	long long int dummy1, dummy2, dummy;
	dummy1 = max(a, b);
	dummy2 = min(a, b);
	while(true){
		dummy = dummy1 % dummy2;
		dummy1 = dummy2;
		dummy2 = dummy;
		if(dummy == 0){
			break;
		}
	}
	return dummy1;
}

int main(){
	long long int A, B;
	cin >> A >> B;
	long long int G = GCD(A, B);
	long long int ans = 1;
	for(int i = 2; i <= 1000100; i++){
		if(G % i == 0){
			ans += 1;
			while(G % i == 0){
				G /= i;
			}
		}
	}
	if(G != 1){
		ans += 1;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<iomanip>
#include<set>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define brep(index,num) for(int index=num-1;index>=0;index--)
#define brep1(index,num) for(int index=num;index>0;index--)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
typedef long long ll;
typedef long double ld;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
int main(){
	int m1,d1,m2,d2;
	scan(m1>>d1>>m2>>d2);
	prin((d2==1));
	return 0;
}


Measured memory_bytes: 256
// ABC141C2.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//

//#include "pch.h"
#include <iostream>
using namespace std;
#include <vector>

int main()
{
	int N, K, Q;
	cin >> N >> K >> Q;
	vector<int>A(Q + 1);
	vector<int>count(N + 1);
	for (int i = 1; i <= Q; i++)
	{
		cin >> A.at(i);
		count.at(A.at(i))++;
	}
	for (int j = 1; j <= N; j++)
	{
		if (K-Q+count.at(j)>0)
		{
			cout << "Yes" << endl;
		}
		else
		{
			cout << "No" << endl;
		}
	}
}


Measured memory_bytes: 1408
var n,d,i,j,k,count,dis:integer;
    X:array[1..30,1..15] of integer;
begin
read(n,d);
for i := 1 to n do
 for j := 1 to d do read(X[i,j]);

for i := 1 to n-1 do
for j := i+1 to n do
begin
dis:=0;
for k := 1 to d do dis:=dis+sqr(X[i,k]-X[j,k]);
if dis=sqr(trunc(sqrt(dis))) then inc(count)
end;
write(count);
end.

Measured memory_bytes: 128
#include<stdio.h>
#include<string.h>
#include<math.h>
#include <stdlib.h>
#include<ctype.h>
typedef long long LL;
#define rep(i,n) for(LL i=0; i<(LL)(n); i++)
//qsort
int compare_int(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;
}

//比較
int max(int a, int b){
	if (a>b) return a;
	else return b;
}

int min(int a,int b) {
	if(a>b) return b;
	else return a;
}


//main関数
int main() {
	int N,X,T;
	scanf("%d %d %d",&N,&X,&T);
	printf("%d",(((N-1)/X)+1)*T);
}







Measured memory_bytes: 1712
import sys
sys.setrecursionlimit(100000000)

def main():
    S = input()
    N = len(S)
    ans = 0
    before = 0
    for i in range(N - 1):
        if S[i] != S[i + 1]:
            ans = max(ans,min(N - before,i + 1))
            before = i + 1
    ans = max(ans,N - before)
    print(ans)
if __name__ == '__main__':
    main()

Measured memory_bytes: 3188
#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <utility>
#include <map>
#include <list>
#include <climits>
#include <set>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>

// #define cerr if(false)cerr
#define watch(x) cerr << "> " << #x << ": " << x << "\n";

using namespace std;

template <typename T>
std::ostream &operator <<(std::ostream &out, vector<T> &v) {
	for (typename vector<T>::size_type i = 0; i < v.size(); ++i)
		out << v[i] << " ";
	out << "\n";
    return out;
}
template <typename T, typename N>
std::ostream &operator <<(std::ostream &out, vector<pair<T, N> > &v) {
	for (size_t i = 0; i < v.size(); ++i)
		out << "(" << v[i].first << ", " << v[i].second << ") ";
	out << "\n";
    return out;
}
template <typename T>
std::ostream &operator <<(std::ostream &out, vector<vector<T> > &v) {
	for (size_t i = 0; i < v.size(); ++i) {
		for (size_t j = 0; j < v[i].size(); ++j) {
			out << v[i][j] << " ";
		}
		out << "\n";
	}
   	return out;
}

constexpr long double PI = 3.14159265;

int main() {

	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	long double a, b, x;
	cin >> a >> b >> x;

	if (x >= a * a * b / 2) {
		long double y = 2 * (a * a * b - x) / (a * a * a);
		cout << setprecision(12) << atan(y) * 180 / PI << "\n";
	} else {
		cout << setprecision(12) << (PI / 2 - atan(2 * x / (a * b * b))) * 180 / PI << "\n";
	}

	return 0;

}

Measured memory_bytes: 256
from itertools import accumulate

def main():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))
    
    nonzeros = [1]
    for a in As:
        ndp = nonzeros[-1]
        if a <= K:
            ndp |= (nonzeros[-1] % (1 << (K-a))) << a
        nonzeros.append(ndp)
    dp = [0] * (K+1)
    dp[0] = 1
    acc = list(accumulate(dp)) + [0]
    ans = 0
    for i in range(N, 0, -1):
        a = As[i-1]
        ndp = []
        for j in range(K+1):
            t = dp[j] if j < a else dp[j] + dp[j-a]
            ndp.append(0 if t == 0 else 1)
        dp = ndp
        if a < K:
            nonzero = nonzeros[i-1]
            for y in range(K+1):
                if nonzero & 1:
                    t = K-y-a-1
                    if acc[K-y-1] > acc[t if t >= 0 else -1]:
                        break
                nonzero >>= 1
            else:
                ans += 1
        acc = list(accumulate(dp)) + [0]
    
    print(ans)

main()


Measured memory_bytes: 145560
n=input()
t,a=input().split()
n=int(n)
t=int(t)
a=int(a)
b=input().split()
min=1000
for i in range(n):
    diff=abs(a-t+0.006*int(b[i]))
    if min>diff:
        id=i+1
        min=diff

print (id)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#define endl '\n'
using namespace std;
typedef long long ll;
int main(){

    int n; cin >> n;
    string s; cin >> s;
    if(n%2==1)cout<<"No";
    else{
    int m = n/2;
    bool flag = true;
    for(int i=0; i<m; i++)
    {
        if(s[i]!=s[m+i]){
            flag = false;
            break;
        }
    }
    if(flag)cout << "Yes";
    else cout << "No";
    }
    return 0;

}


Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef vector<vector<int>> Matrix;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
static const int INF = 2000000000;

int main(){
  int n;
  cin >> n;
  vector<ll> L(200010), R(200010), a(n);
  rep(i, n) cin >> a[i];
  ll ans = 0;
  rep(i, n){
    ll l = i - a[i], r = i + a[i];
    if (l >= 0) L[l]++;
    if (r < n) R[r]++;
  }
  rep(i, n) ans += (ll)L[i] *  R[i];
  cout << ans << endl;
}


Measured memory_bytes: 7984
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i < (n+1); ++i)
using namespace std;
using ll = long long;
const int INF = -100100100;
typedef pair<int,int> P;

int main(){
    ll n, a, b;
    cin >> n >> a >> b;
    vector<ll> v;
    ll ans = 0;
    ans += n/(a+b) * a;
    ll r = n%(a+b);
    if(a<=r)ans+=a;
    else ans+=r;
    cout << ans << endl;
    return 0;
    
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <cstdint>

#include <map>
 
using namespace std;
typedef long long ll;



ll ans,mx,sum,mn=1e8;
int main(){
	ll a,b;
	cin>>a>>b;
	if(a<=b) {
		for(int i=0; i<b; i++) cout<<a;
	}
	else {
		for(int i=0; i<a; i++) cout<<b;
	}
}


Measured memory_bytes: 256
#include<iostream>
#include <string>
#include<algorithm>
#include <set>
#include <cmath>
using namespace std;
typedef long long lint;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rep0(i,n) rep(i,0,n)

int main(void) {
	ios::sync_with_stdio(false);
	int i, j, k, N, result, a, b, c;
	cin >> N;
	double tax = 1.08, X;
	a = (int)((double)(N) / tax);
	if      (int((double)(a)*tax) == N) cout << a;
	else if (int((double)(a+1)*tax) == N) cout << a + 1;
	else if (int((double)(a-1)*tax) == N) cout << a - 1;
	else cout << ":(";
	return 0;
}
//
////sort Ｎ個の配列a
//sort(a, a + N); //昇順
//sort(a, a + N, greater<int>()); //降順
//
////最大公約数（ユークリッドの互除法利用）
//int gcd(int a, int b) {
//	if (a == 0) return b;
//	if (b == 0) return a;
//	int m = max(a, b);
//	int n = min(a, b);
//	if (m%n == 0) return n;
//	else return gcd(n, m%n);
//
//}
//
////最小公倍数
//int lca(int a, int b) {
//	if (a == 0) return 0;
//	if (b == 0) return 0;
//	return a * b / gcm(a, b);
//}
//
////n^k(整数)
//int pow_int(int n, int k) {
//	int re = 1;
//	for (int i = 0; i < k; i++) re *= n;
//	return re;
//}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;

typedef long long lint;
typedef long double louble;

template<typename T1,typename T2> inline T1 max(T1 a,T2 b){return a<b?b:a;}
template<typename T1,typename T2> inline T1 min(T1 a,T2 b){return a<b?a:b;}

namespace ae86
{
	const int bufl = 1<<15;
	
	char buf[bufl],*s=buf,*t=buf;
	
	inline int fetch()
	{
		if(s==t){t=(s=buf)+fread(buf,1,bufl,stdin);if(s==t)return EOF;}
		return *s++;
	}
	
	inline int ty()
	{
		int a=0,b=1,c=fetch();
		while(!isdigit(c))b^=c=='-',c=fetch();
		while(isdigit(c))a=a*10+c-48,c=fetch();
		return b?a:-a;
	}
}
using ae86::ty;

const int _ = 100007 , __ = _<<1;

int to[__],ne[__],ev[__],he[_]={0},ecnt=1;
inline void adde(int a,int b,int c){to[++ecnt]=b,ev[ecnt]=c,ne[ecnt]=he[a],he[a]=ecnt;}

int n,m,col[_],ccnt[3],ef,pf,failed;

void dfs(int x,int now)
{
	col[x]=now,pf++,ccnt[col[x]]++;
	for(int i=he[x];i;i=ne[i])
	{
		int b=to[i],v=(now+ev[i]+3)%3;
		ef+=ev[i]>0;
		if(col[b]<0)dfs(b,v);
		else if(col[b]!=v)failed=1;
	}
}

int main()
{
	n=ty(),m=ty();
	for(int i=1,a,b;i<=m;i++)a=ty(),b=ty(),adde(a,b,1),adde(b,a,-1);

	lint ans=0;
	
	memset(col,-1,sizeof(col));
	for(int i=1;i<=n;i++)
	{
		if(col[i]>=0)continue;
		ccnt[0]=ccnt[1]=ccnt[2]=ef=pf=failed=0,dfs(i,0);
		if(failed)ans+=1ll*pf*pf;
		else if(ccnt[0] && ccnt[1] && ccnt[2])
			ans+=1ll*ccnt[0]*ccnt[2]+1ll*ccnt[1]*ccnt[0]+1ll*ccnt[2]*ccnt[1];
		else ans+=ef;
	}
	printf("%lld\n",ans);

	return 0;
}


Measured memory_bytes: 6528
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String a = sc.next();
		String s = sc.next();
		String c = sc.next();
		String s2 = s.toUpperCase();
		System.out.println(a.charAt(0) +""+ s2.charAt(0) +""+ c.charAt(0) );
	}

}


Measured memory_bytes: 26884
class Node():
   def __init__(self, key):
     self.parent = None
     self.right = None
     self.left = None
     self.key = key

class BST():
  def __init__(self):
    self.T = list()
    self.root = None
    self.res = []

  def insert(self,node:Node):
    y = None
    x = self.root
    while x is not None:
      y = x
      if node.key < x.key:
        x = x.left
      else:
        x = x.right
    node.parent = y
    if y is None:
      self.root = node
    elif node.key < y.key:
      y.left = node
    else:
      y.right = node

  def preorder(self,node:Node):
    if node is None:
      return
    #self.res.append(node.key)
    print(" " + str(node.key), end="")
    self.preorder(node.left)
    self.preorder(node.right)

  def inorder(self, node:Node):
    if node is None:
      return
    self.inorder(node.left)
    print(" " + str(node.key), end="")
    self.res.append(node.key)
    self.inorder(node.right)

  def find(self, key, node:Node ):
    if node is None:
      return False
    if node.key == key:
      return True
    if key < node.key:
      return self.find(key, node.left)
    else:
      return self.find(key, node.right)





def main():
  n = int(input())
  T = BST()
  for _ in range(n):
    cmd = input().split()
    if cmd[0] == "insert":
      key = int(cmd[1])
      T.insert(Node(key))
    elif cmd[0] == "find":
      key = int(cmd[1])
      print ("yes" if T.find(key, T.root) else "no")
    else:
      T.inorder(T.root)
      print()
      T.preorder(T.root)
      print()

if __name__ == "__main__":
  import sys, io

  main()




Measured memory_bytes: 89608
// D - Five, Five Everywhere
#include <bits/stdc++.h>
using namespace std;

// 素数判定
bool isprime(int p){
	if(p <= 1) return false;
	for(int i=2; i*i<=p; ++i) if(p%i == 0) return false;
	return true;
}

int main(){
	int N; cin>>N;
	for(int n=0,p=5*1+2; p<=55555 && n<N; p+=10)
		if(isprime(p) && p%5==2){ cout<<p<<" "; n++; }
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main
{
  public static void main(String[] args)
  {
    try(Scanner sc = new Scanner(System.in))
    {
      final int a = sc.nextInt();
      final int b = sc.nextInt();
      
      if( (a*b)%2 == 0 )
      {
        System.out.println("Even");
      }
      else
      {
        System.out.println("Odd");
      }
    }
  }
}

Measured memory_bytes: 22736
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;

int main(){
	int n,t,a;
	cin >> n;
	cin >> t >> a;
	int h[n];
	for(int i = 0; i < n; i++)cin >> h[i];
	double dif,min = 1e9;
	int res;
	for(int i = 0; i < n; i++){
		dif = abs(t - h[i] * 0.006 - a);
		if(dif < min){
			min = dif;
			res = i + 1;
		}
	}
	cout << res << endl;
}

Measured memory_bytes: 256