akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"

#define rep(i, a) for (int i = 0; i < (int)a; ++i)
#define REP(i, a, b) for (int i = (a); i < (int)b; ++i)

// [debug]

using namespace std;
using ll = long long;
using P = pair<int, int>;

void Main() {
  ll a, b, c;
  cin >> a >> b >> c;
  ll x;
  x = c - a - b;
  if (x < 0) {
     cout << "No" << endl;
     return;
  }
  x = x*x;
  x -= 4 * a * b;
  if (x>0) cout << "Yes" << endl;
  else cout << "No" << endl;
}

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  Main();
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
const int mx = 100005;
int n, m, a[mx], j, k, b[mx];
long long ans;
pair<int, int> pr[mx];
int main(){
    scanf("%d%d", &n, &m);
    rep(i,n) scanf("%d", a+i);
    sort(a, a+n, greater<int>());
    rep(i,m) scanf("%d%d", &pr[i].second, &pr[i].first);
    sort(pr, pr+m, greater<pair<int, int>>());
    rep(i,n){
        b[i] = pr[j].first;
        pr[j].second--;
        if(pr[j].second == 0){
            j++;
            if(j == m) break;
        }
    }
    j = 0;
    rep(i,n){
        if(a[j] > b[k]){
            ans += a[j++];
        }else ans += b[k++];
    }
    printf("%lld\n", ans);
}

Measured memory_bytes: 1792
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=100+10;
int n,a[N],b[N];
int st[N],tp;
void del(int x){
	for(int i=x+1;i<=n;i++)b[i-1]=b[i];n--;
}
int main(){
	//freopen("a.in","r",stdin);
	scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&b[i]);int realn=n;
	while(n){tp=0;int lstn=n;
		for(int i=n;i;i--)if(b[i]==i){st[++tp]=i;break;}
		for(int i=1;i<=tp;i++) a[n-i+1]=st[i];
		for(int i=1;i<=tp;i++)del(st[i]);
		if(n==lstn) break;
	}
	bool flg=1;
	for(int i=1;i<=realn;i++)if(a[i]>i)flg=0;if(n)flg=0;
	if(!flg)puts("-1");
	else for(int i=1;i<=realn;i++)printf("%d\n",a[i]);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<int,int>
using namespace std;
pii pos1[100], pos2[100];

int dist(pii p1, pii p2){
	return abs(p1.x-p2.x) + abs(p1.y-p2.y);
}
int main() {
	// your code goes here
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++) {
		cin>>pos1[i].x>>pos1[i].y;
	}
	for(int i=0;i<m;i++) {
		cin>>pos2[i].x>>pos2[i].y;
	}
	int pos;
	for(int i=0;i<n;i++) {
		int minDist = INT_MAX;
		for(int j=0;j<m;j++){
			int d = dist(pos1[i], pos2[j]); 
			if(d < minDist){
				minDist = d;
				pos = j+1;
			}
		}
		printf("%d\n",pos);
	}
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <string.h>

using namespace std;
typedef long long ll;

int main()
{
	int H, W, N;
	scanf("%d %d %d", &H, &W, &N);
	
	int ans;
	if(H > W){
		ans = N / H;
		if( N % H != 0){
			ans ++;
		}
	}
	else
	{
		ans = N / W;
		if( N % W != 0){
			ans++;
		}
	}
	
	printf("%d\n", ans);
	
	return 0;
}

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

int main(){
  int N;
  cin >> N;
  vector<int> H(N);
  cin >> H.at(0);
  int ans = 1;
  int max = H.at(0);
  for (int i = 1; i < N; i++) {
    cin >> H.at(i);
    if (H.at(i) >= max) {
      ans++;
      max = H.at(i);
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,m,i;
  cin>>n>>m;
  vector<int> x(m);
  vector<int> sa(m-1);
  for(i=0;i<m;i++){
    cin>>x.at(i);
  }
  sort(x.begin(),x.end());
  for(i=1;i<m;i++){
      sa.at(i-1)=abs(x.at(i)-x.at(i-1));
    }
  sort(sa.begin(),sa.end());
  int g=(m-n);
  int ans=0;
  for(i=0;i<g;i++){
    ans+=sa.at(i);
  }
  cout<<ans<<endl;
  
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define FOR(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define FORR(i, n) for(ll i = (ll)n - 1LL; i >= 0LL; i--)
#define rep(i, n) FOR(i, 0, n)
#define ALL(x) begin(x), end(x)
using namespace std;
using ll = long long;
constexpr ll Mod = 998244353;
constexpr ll mod = 1e9 + 7;
constexpr ll inf = 1LL << 60;
const double PI = acos(-1);
template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) {
    return a < b && (a = b, true);
}
template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) {
    return a > b && (a = b, true);
}
/*-------------------------------------------*/

int n;
ll a[200009];
ll k;

bool f(ll x) {
    ll cnt = 0;
    rep(i, n) cnt += (a[i] + x - 1) / x;
    return cnt - n <= k;
}

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

    cin >> n >> k;
    rep(i, n) cin >> a[i];

    ll ng = 0, ok = 1e9 + 1;
    while(ng + 1 < ok)
        (f(ng + ok >> 1) ? ok : ng) = ng + ok >> 1;

    cout << ok << endl;

    return 0;
}

Measured memory_bytes: 5196
#include <iostream>
#include <algorithm>
#include <fstream>
#include <utility>
#include <iomanip>
#include <cstring>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#define IO ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
typedef long long ll;
typedef long double ld;

using namespace std;
const ll INF = 1e18;
const int mod = 1e4, N = 1e5 + 5, inf = 1e9;

int main()
{
    IO
    int n, k, arr[N], mn = inf;
    cin >> n >> k;
    for(int i = 0; i < n; i++)
        cin >> arr[i];
    sort(arr, arr + n);
    for(int i = 0; i <= n - k; i++)
        mn = min(mn, arr[i + k - 1] - arr[i]);
    cout << mn << '\n';
    return 0;
}

Measured memory_bytes: 3984
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //これつけるとA[N]でもいいらしい
//for文のマクロ
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define big 1000000007
#define all(a) sort((a).begin(),(a).end()) //ソートのマクロ
int main(){
  vector<int> a(3);
  cin>>a[0]>>a[1]>>a[2];
  all(a);
  cout<<a[2]-a[0]<<endl;
}

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQG = priority_queue<T, vector<T>, greater<T> >;
const int INF = 100010001;
const ll LINF = (ll)INF*INF*10;
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);}
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);}
template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second;}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << p.first << ' ' << p.second;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int m, n, d;
    cin >> m >> n >> d;
    while(m or n or d) {
        vvi s(n, vi(m));
        rep(i, n) rep(j, m) {
            cin >> s[i][j];
        }

        auto num = [&](int i, int j) {
            return i*m + j;
        };

        vector<bitset<625> > bits(625);
        rep(i, n) rep(j, m) {
            bitset<625> now(0);
            now[num(i, j)] = 1;
            rep(k, n) rep(l, m) if(abs(k-i) + abs(l-j) == d) {
                now[num(k, l)] = 1;
            }
            int x = -1;
            for(int k = 624; k >= 0; k--) {
                if(now.test(k) and bits[k].test(k)) {
                    now ^= bits[k];
                }
                if(now.test(k)) chmax(x, k);
            }
            if(x == -1) continue;
            for(int k = 624; k > x; k--) {
                if(bits[k].test(x)) {
                    bits[k] ^= now;
                }
            }
            bits[x] = now;
        }

        bitset<625> S(0);
        rep(i, n) rep(j, m) {
            if(s[i][j]) {
                S.set(num(i, j));
            }
        }
        //cout << S << endl;
        for(int i = 624; i >= 0; i--) {
            //cout << bits[i] << endl;
            if(S.test(i) and bits[i].test(i)) {
                S ^= bits[i];
            }
        }

        cout << (S == bitset<625>(0)) << '\n';
        cin >> m >> n >> d;
    }
}


Measured memory_bytes: 3120
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author hakamada
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ABC115_c solver = new ABC115_c();
        solver.solve(1, in, out);
        out.close();
    }

    static class ABC115_c {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int N = in.nextInt();
            int K = in.nextInt();
            int h[] = new int[N];
            int diffMin = Integer.MAX_VALUE;

            for (int i = 0; i < N; i++) {
                h[i] = in.nextInt();
            }

            Arrays.sort(h);

            for (int i = 0; i < N - (K - 1); i++) {
                int diff = h[i + (K - 1)] - h[i];
                if (diffMin > diff) {
                    diffMin = diff;
                }
            }
            out.println(diffMin);
        }

    }
}



Measured memory_bytes: 50500
#include <cmath>
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<set>
#include<map>
#include<bitset>
#include<iomanip>
#include<stack>
#include<set>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
ll mod = 1000000007;

vector<P> prime_factorize(long long N) {
    vector<pair<long long, long long> > res;
    for (long long a = 2; a * a <= N; ++a) {
        if (N % a != 0) continue;
        long long ex = 0;
        while (N % a == 0) {
            ++ex;
            N /= a;
        }
        res.push_back({ a, ex });
    }
    if (N != 1) res.push_back({ N, 1 });
    return res;
}

int main() {
	ll n;
	cin >> n;
    
    ll count = 0;
	for (int c = 1; c < n; c++) {
		ll ans = n - c;
        vector<P> p;
        p = prime_factorize(ans);
        ll index = 1;
        for (auto id : p) {
            index *= (id.second + 1);
        }
        
        count += index;
	}
    cout << count << endl;
}

Measured memory_bytes: 3628
#include<iostream>
#include<cstring>
#include<cstdio>
#define lint long long
#define N 100010
using namespace std;
char s[N];int n,ans,cnt[N];
inline bool check(int k)
{
	if(k*2<=n+1) return true;int L=n-k+1,R=k;
	return (cnt[R]-cnt[L-1])%(R-L+1)==0;
}
int main()
{
	scanf("%s",s+1),n=strlen(s+1);
	for(int i=1;i<=n;i++)
		cnt[i]=cnt[i-1]+(s[i]=='1');
	for(int i=1;i<=n;i++)
		if(check(i)) ans=i;
	return !printf("%d\n",ans);
}

Measured memory_bytes: 768
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		try (Scanner sc = new Scanner(System.in)) {
			int N, M;
			N = Integer.parseInt(sc.next());
			M = Integer.parseInt(sc.next());

			int iniMax = 0, endMin = N;

			for (int i = 0; i < M; i++) {
				int ini = Integer.parseInt(sc.next());
				int end = Integer.parseInt(sc.next());
				
				iniMax = Math.max(iniMax, ini);
				endMin = Math.min(endMin, end);
			}
			int ans = endMin - iniMax + 1;
			if (ans > 0) System.out.println(ans);
			else System.out.println("0");		}
		 catch (Exception e) {
			// TODO: handle exception
		}

	}

}


Measured memory_bytes: 49296
X = gets.to_i

rate = case X
       when 400..599
         8
       when 600..799
         7
       when 800..999
         6
       when 1000..1199
         5
       when 1200..1399
         4
       when 1400..1599
         3
       when 1600..1799
         2
       when 1800..1999
         1
       end

puts rate


Measured memory_bytes: 14328
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int a = sc.nextInt();
        int b = sc.nextInt();

        if (a + b >= 24) {
            System.out.println(a + b - 24);
        } else {
            System.out.println(a + b);
        }
    }
}


Measured memory_bytes: 21844
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[] a = new int[n];
		for(int i=1;i<n;i++) {
			a[i] = sc.nextInt() + a[i-1];
		}
		int dist = 0;
		int k = 0;
		for(int i=0;i<m;i++) {
			int b = sc.nextInt();
			dist = (dist + Math.abs(a[k+b] - a[k])) % 100000;
			k+=b;
		}
		System.out.println(dist);
	}

}

Measured memory_bytes: 94544
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define ll long long
#define P pair<ll,ll>
#define all(v) (v).begin(),(v).end()

const ll mod = 1e9+7;
const ll INF = 1e18;
const double pi = acos(-1);


int main(void)
{
    string s;
    cin >> s;
    ll ans=0,b=0,n=s.size();
    rep(i,n){
        if(s[i]=='B') b++;
        else ans += b;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3768
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int INF=1e9;
const long double eps=1e-9;
const int maxn=1e2+10;
int SG[maxn],vis[maxn];
char A[]="Aoki",B[]="Takahashi";
inline int read(){
	int x=0,flag=1;
	char ch=getchar();
	while(!isdigit(ch) && ch!='-')ch=getchar();
	if(ch=='-')flag=-1,ch=getchar();
	while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return x*flag;
}
int Get_SG(int a,int k){
	if(a<k)return 0;
	if(a%k==0)return a/k;
	int val=a/k+1;
	int delta=max((a-(a/k)*k)/val,1);
	return Get_SG(a-1ll*val*delta,k);
}
int main(){
	int i,j,k,m,n,a;
	n=read();
	int val=0;
	for(i=1;i<=n;i++){
		a=read();k=read();
		val^=Get_SG(a,k);
	}
	printf("%s\n",val==0?A:B);
	return 0;
}


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

typedef long long ll;
const ll MOD = 1e9 + 7;
const long long INF = 1LL<<60;
const double PI=3.14159265358979323846;
const int NMAX=100005;
using namespace std;

vector<ll> f;
ll ans[1000001];
ll ans_odd[10000001];

int main(){
    for(ll i = 1; i < 240; i++){
        ll tmp = i*(i+1)*(i+2)/6;
        if(tmp > 1000000) break;
        f.push_back(tmp);
    }
    for(int i = 0; i <= 1000000; i++){
        ans[i] = INF;
        ans_odd[i] = INF;
    }
    ans[0] = 0;
    ans[1] = 1;
    ans_odd[0] = 0;
    ans_odd[1] = 1;
    for(ll i = 0; i <= 1000000; i++){
        for(int j = 0; j < f.size(); j++){
            if(i+f[j] > 1000000) break;
            ans[i+f[j]] = min(ans[i+f[j]], ans[i]+1);
            if((f[j]%2)==1){
                ans_odd[i+f[j]] = min(ans_odd[i+f[j]], ans_odd[i]+1);
            }
        }
    }
    while(true){
        ll n;
        cin >> n;
        if(n == 0) break;
        cout << ans[n] << " " << ans_odd[n] << endl;
    }
}


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

int main()
{
	int N;
	cin >> N;
	cout << N / 3 << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
#define float double
#define endl "\n"
#define debug cout<<"Good uptill here"<<endl<<flush;
#define deb(x) cout<<#x<<":"<<x<<endl<<flush;

using namespace std;

const int inf = 1e17 + 7;
const int MOD = 1e7 + 9;
void mini(int &a, int b){
	a = min(a,b);
}
int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	//CODE FOR SPECIFIED INPUT AND OUTPUT
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int n,wgt;
	cin>>n>>wgt;
	int inp[n][2];
	int sum = 0;
	for(int i=0;i<n;i++){
		cin>>inp[i][0]>>inp[i][1];
		sum += inp[i][1];
	}
	vector<vector<int>> dp(sum+1,vector<int> (n,inf));
	int ans = 0;
	for(int i=0;i<n;i++) dp[inp[i][1]][i] = inp[i][0];
	for(int i=0;i<=sum;i++){
		for(int j=0;j<n;j++){
			int nv = i + inp[j+1][1];
			if(nv<=sum && j<n-1) mini(dp[nv][j+1],dp[i][j]+inp[j+1][0]);
			if(j<n-1) mini(dp[i][j+1],dp[i][j]);
			if(dp[i][j]<=wgt) ans = max(ans,i);
		}
	}
	cout<<ans<<endl;
	return 0;
}



Measured memory_bytes: 82304
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <queue>
using namespace std;
#define FOR(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define FFOR(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
#define rep(i,n) FOR(i,0,n-1)
#define int long long
#define MOD 998244353
#define MAXN  100005
#define P pair<int,int>

int gcd(int a, int b) {return b?gcd(b,a%b):a;}

signed main(){
	
	string s;cin>>s;
	int mn = 123456789;
	rep(i,26)
	{
		int cnt = 0;
		int dai = 0;
		rep(j,s.size())
		{
			if(s[j]-'a' != i)cnt++;
			else cnt = 0;
			dai = max(dai,cnt);
		}
		mn = min(mn,dai);
	}
	
	cout << mn << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(), (c).end());
const long long MOD = 1e9 + 7;
typedef long long ll;

int main(){
	int S;
	cin >> S;
	int MAX = 1000000;
	set<int> M;
	M.insert(S);
	int cnt = 1;
	while(true){
		if(S % 2 == 0){
			S /= 2;
		} else {
			S = S * 3 + 1;
		}
		cnt++;
		if(M.count(S)){
			cout << cnt << endl;
			break;
		} else {
			M.insert(S);
		}
	}
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)


def main():
    N, M = map(int, input().split())
    Q = []
    for _ in range(M):
        a, b = map(int, input().split())
        Q.append((a, b))
    Q.reverse()

    uf = UnionFind(N+1)
    ans = [N*(N-1)//2]
    for a, b in Q:
        if uf.same(a, b):
            ans.append(ans[-1])
        else:
            sa = uf.size(a)
            sb = uf.size(b)
            uf.union(a, b)
            ans.append(ans[-1] - sa*sb)
    ans.pop()

    ans.reverse()
    for a in ans:
        print(a)


if __name__ == '__main__':
    main()


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

using namespace std;

int main(int argc, const char *argv[]) {
  int n, ans = 0;
  cin >> n;
  vector<string> vs(n);
  int a_cnt, b_cnt, ba_cnt;
  a_cnt = b_cnt = ba_cnt = 0;
  for (int i = 0; i < n; i++) {
    cin >> vs[i];
    string &s = vs[i];
    for (int i = 0; i < s.size() - 1; i++) {
      if (s[i] == 'A' && s[i + 1] == 'B') {
        ans++;
      }
    }

    if (s.front() == 'B' && s.back() == 'A') {
      ba_cnt++;
    } else if (s.back() == 'A') {
      a_cnt++;
    } else if (s.front() == 'B') {
      b_cnt++;
    }
  }

  if (ba_cnt > 0) {
    ans += ba_cnt - 1;

    if (b_cnt > 0) {
      ans++;
      b_cnt--;
    }

    if (a_cnt > 0) {
      ans++;
      a_cnt--;
    }
  }

  ans += min(a_cnt, b_cnt);
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 768
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N,K;
  cin>>N>>K;
  
  vector<int>S(N+1);
  vector<bool>dp(K+1, false);
  
  for(int i=0;i<N;i++)
    cin>>S[i];
  
  for(int i=0;i<=K;i++){
  	for(int j=0;j<N;j++){
    	if(i-S[j]>=0 && dp[i-S[j]]==0)
          dp[i]=1;
    }
  }
  
  if(dp[K])
    cout<<"First";
  else
    cout<<"Second";
  
  return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

#include <limits.h>

using namespace std;

typedef long long ll;

template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

/*
 * ref. [Union-Find](https://www.slideshare.net/chokudai/union-find-49066733)
 * ref. [AtCoder ABC 157 - AtCoder Live](https://www.youtube.com/watch?v=TdR816rqc3s)
 */
class UnionFind {
    public:
        UnionFind(int n = 0): d(n, -1) {}

        // 0-index, [0, n) in other words
        // Time complexity: O(a(n)) (a = inverse Achkermann function)
        int find(int x) {
            if (d[x] < 0) return x;
            return d[x] = find(d[x]);
        }

        // Return false if x and y are alreday in the same group, otherwise return true.
        // 0-index, [0, n) in other words
        // Time complexity: O(a(n)) (a = inverse Achkermann function)
        bool unite(int x, int y) {
            x = find(x);
            y = find(y);
            if (x == y) return false;
            if (d[x] > d[y]) swap(x, y);
            d[x] += d[y];
            d[y] = x;
            return true;
        }

        // 0-index, [0, n) in other words
        // Time complexity: O(a(n)) (a = inverse Achkermann function)
        bool same(int x, int y) {
            return find(x) == find(y);
        }

        // 0-index, [0, n) in other words
        // Time complexity: O(1)
        int size(int x) {
            return -d[find(x)];
        }

    private:
        vector<int> d;
};

int main(void) {
    int N, M;
    cin >> N >> M;

    UnionFind uf(N);

    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;

        uf.unite(a, b);
    }

    int ans = 0;
    for (int i = 0; i < N; i++) {
        chmax(ans, uf.size(i));
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 4040
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int a[2010][2010] = {0};
int b[2010][2010] = {0};

int main() {
  int h, w, z;
  cin >> h >> w;
  vector<vector<char> > c(h, vector<char>(w));
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      cin >> c[i][j];
    }
  }

  for (int i = 1; i <= h; i++) {
    for (int j = 1; j <= w; j++) {
      if (c[i - 1][j - 1] == '.') {
        a[i][j] = a[i][j - 1] + 1;
      }
    }
  }

  /*
  for (int i = 1; i <= h; i++) {
    for (int j = 1; j <= w; j++) {
      cout << a[i][j];
    }
    cout << endl;
  }
  */

  for (int i = 1; i <= h; i++) {
    for (int j = w; j >= 1; j--) {
      int tmp;
      tmp = a[i][j];
      if (tmp != 0) {
        for (int k = j; k >= 1; k--){
          //cout << "i:" << i << "j:" << j << "k:" << k << endl;
          if (a[i][k] == 0) {
            j = k;
            //cout << "i:" << i << "j:" << j << endl;
            break;
          }
          else {
            a[i][k] = tmp;
          }
          if (k == 1) {
            j = k;
          }
        }
      }
    }
  }

  /*
  for (int i = 1; i <= h; i++) {
    for (int j = 1; j <= w; j++) {
      cout << a[i][j];
    }
    cout << endl;
  }
  */

  for (int i = 1; i <= w; i++) {
    for (int j = 1; j <= h; j++) {
      if (c[j - 1][i - 1] == '.') {
        b[j][i] = b[j - 1][i] + 1;
      }
    }
  }

  for (int i = 1; i <= w; i++) {
    for (int j = h; j >= 1; j--) {
      int tmp;
      tmp = b[j][i];
      if (tmp != 0) {
        for (int k = j; k >= 1; k--){
          if (b[k][i] == 0) {
            j = k;
            break;
          }
          else {
            b[k][i] = tmp;
          }
          if (k == 1) {
            j = k;
          }
        }
      }
    }
  }

  int ans = -1;
  for (int i = 1; i <= h; i++) {
    for (int j = 1; j <= w; j++) {
      int tmp = 0;
      if (c[i - 1][j - 1] == '.') {
        tmp += a[i][j] + b[i][j] - 1;
      }
      if (tmp > ans) {
        ans = tmp;
      }
    }
  }
  cout << ans << endl;
  return 0;
}

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

#define boost ios_base::sync_with_stdio(false), cin.tie(NULL);

using namespace std;
const int N = 1e6 + 41;
const int mod = 1e9 + 7;
const long long INF = 1e16;
const int inf = 1e9;

map <long long, int> cnt;

int main () {
	boost;
	int n;
	cin >> n;
	cnt[0] = 1;
	long long pref = 0, ans = 0;
	while (n--) {
		long long x;
		cin >> x;
		pref += x;
		ans += cnt[pref];
		cnt[pref]++;
	}
	cout << ans;
}

Measured memory_bytes: 12800
#include <iostream>
#define ll long long
#define Arman_Sykot ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
 
using namespace std;

int main()
{
/*********************/
// Author:
        Arman_Sykot;
/*********************/
    
    string s;
    cin >> s;

    for (int i = 0; i < s.size(); i++) {
        cout << 'x';
    }

    cout << "\n";
    return 0;
}


Measured memory_bytes: 3112
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int day_month[]={0,31,29,31,30,31,30,31,31,30,31,30,31};
char day[10][10]={
  {"Thursday"},
  {"Friday"},
  {"Saturday"},
  {"Sunday"},
  {"Monday"},
  {"Tuesday"},
  {"Wednesday"},
};
int main(){
  int m,d,count;
  while(1){
    cin >> m >> d;
    if(!m && !d)break;
    count = -1;
    for(int i=1;i<=m;i++){
      if(i == m){
	for(int j=1;j<=d;j++){
	  count++;
	}
      }else {
	for(int j=1;j<=day_month[i];j++){
	  count++;
	}
      }
    }
    cout << day[count % 7] << endl;
  }
}

Measured memory_bytes: 1156
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
const ll INF = 1LL << 60;

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
//using P = pair<int,int>;
//pow(x,n)
//cout << fixed << setprecision(桁数);
//string = to_string(数値)
//int = stoi(文字列)
//(int)(char-'0')
//string = itoa(int)
//円周率: M_PI


int main() {
    int N;
    cin >> N;
    N=N%1000;
    if(N==0) cout << 0 << endl;
    else cout << 1000-N << endl;
}

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

// Function Macros:
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define all(v) (v).begin(), (v).end()
#define setpre(n) cout << fixed << setprecision(n)

// Type / Class / Struct Definitions:
using namespace std;

using ll = long long;
using ull = unsigned long long;

// Constants:
const int INF = (1ll << 30) - 1;  // approx 1.07e9
const ll INFLL = 1ll << 60;       // approx 1.15e18
const int MOD = 1e9 + 7;          // 998244353
const long double EPS = 1.0e-14;

// Global Variables:

// Prototype Declarations:
int gcd(int, int);
template <class T>
inline bool chmin(T&, T);
template <class T>
inline bool chmax(T&, T);

// ================ Main Loop ================
int main() {
    int k;
    cin >> k;
    ll ans = 0;
    for(int a = 1; a <= k; a++) {
        for(int b = 1; b <= k; b++) {
            for(int c = 1; c <= k; c++) {
                ans += gcd(gcd(a, b), c);
            }
        }
    }
    cout << ans << endl;
    return 0;
}
// ===========================================

// Functions:
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

template <class T>
inline bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

template <class T>
inline bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}


Measured memory_bytes: 3620
import java.util.*

fun main(args: Array<String>) {
    val (N, K) = readLine()!!.split(" ").map {it.toInt()}
    val A = readLine()!!.split(" ").map {it.toLong()}

    fun divisor(n : Long) : Array<Long> {
        val l = ArrayList<Long>()
        var i = 1L
        while (i * i <= n) {
            if (n % i == 0L) {
                l.add(i)
                if (i * i != n) {
                    l.add(n / i)
                }
            }
            i++
        }
        l.sort()

        return l.toTypedArray()
    }

    val cs = divisor(A.sum())
    var res = 1L

    for (c in cs) {
        val a = A.map { it % c }.sorted().toTypedArray()
        val b = Array(N) { c - a[it] }
        for (i in 1 until a.size) {
            a[i] += a[i - 1]
        }
        for (i in b.size - 2 downTo 0) {
            b[i] += b[i + 1]
        }
        var tmp = -1L
        for (i in 0 until a.size - 1) {
            if (a[i] == b[i + 1]) {
                tmp = a[i]
            }
        }

        if (tmp <= K) {
            res = Math.max(res, c)
        }
    }

    println(res)
}


Measured memory_bytes: 57248
n = int(input())
x = [list(map(int,input().split())) for i in range(n)] + [[11**9]]
x.sort(lambda x:x[0])
a = x[:-2]
y = a + [n]
a += [2,1]
for i in range(n-2,-1,-1):
  y[i] = i+1
  while x[y[i]][0] < sum(x[i]):
    y[i] = y[y[i]]
  a[i] = (a[i+1]+a[y[i]]) % 998244353
print(a[0])

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

int main() {
	int n, m;
	cin >> n >> m;
	vector<pair<int, int>> c;
	for (int i = 0, a, b; i < m; i++) {
		cin >> a >> b;
		c.emplace_back(a, b);
	}

	sort(c.begin(), c.end(), [](auto &x, auto &y) {
		return x.second < y.second;
	});
	int ans = 0;
	for (int i = 0, prev = 0; i < m; i++) {
		if (c[i].first > prev) {
			ans++;
			prev = c[i].second - 1;
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 1528
#include <bits/stdc++.h>
using namespace std;
int n,i;
string s,t;
int main() {
  cin>>n>>s>>t;
  for (i=n; i>0; i--) if (s.substr(n-i,i)==t.substr(0,i)) break;
  printf("%d\n",2*n-i);
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <numeric>
#include <list>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#define rep(i, n) for (int i = 0; i < n; i++)
#define rep1(i, n) for (int i = 1; i <= n; i++)

using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

const int INF = 1 << 30;
const long long INFL = 1LL << 62;
const int MOD = 1000000007;
const int MAX = 100000;
const int N = 100;

int x[MAX];
vector<pii> G[MAX];
bool ans;

void bfs(int i){
	queue<pii> Q;
	Q.push(pii(0,i));
	x[i]=0;
	while(!Q.empty()){
		pii p=Q.front();Q.pop();
		for(auto p2:G[p.second]){
			if(!ans) break;
			if(x[p2.second]==INF){
				x[p2.second]=x[p.second]+p2.first;
				Q.push(pii(p2));
			}
			else if(x[p2.second]!=x[p.second]+p2.first){
				ans=false;
				break;
			}
		}
		if(!ans) break;
	}
}

int main() {
	int n,m;cin>>n>>m;
	rep(i,m) {
		int l,r,d;cin>>l>>r>>d;l--;r--;
		G[l].push_back(pii(d,r));
		G[r].push_back(pii(-d,l));
	}
	rep(i,n) x[i]=INF;
	ans=true;
	rep(i,n) if(x[i]==INF&&ans) bfs(i);
	if(ans) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}


Measured memory_bytes: 9588
using System;
using System.Linq;

namespace MF
{
    class Program
    {
        static void Main(string[] args)
        {
            while (int.Parse(Console.ReadLine()) != 0 )
            {
                var c = Console.ReadLine().Split(' ').Select(int.Parse).ToList();
                var a = c.Average();
                Console.WriteLine("{0}", Math.Sqrt(c.Select(e => Math.Pow(e - a, 2)).Average()));
            }
        }
    }
}

Measured memory_bytes: 9872
#include<iostream>
using namespace std;

int main(){
    int A,B;
    cin >> A >> B;

    int ans = 0;

    for(int i = 0; i < 2 ; i++){
        if(A > B){
            ans += A;
            A--;
        }else{
            ans += B;
            B--;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
N, K = map(int, input().split())
A = list(map(int, input().split()))
m = 10**9
for i in range(1, K):
    count = 1 + (N - i - 1) // (K - 1)
    if (N - i - 1) % (K - 1):
        count += 1
    m = min(m, count)
print(m)


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

int main() {
  int n, m, x, y;
  cin >> n >> m >> x >> y;
  vector<int> xs(n), ys(m); 

  rep(i, n) {
    cin >> xs[i];
  }

   rep(i, m) {
    cin >> ys[i];
  }

  sort(xs.begin(), xs.end()); 
  sort(ys.begin(), ys.end()); 

  int flag = 0;

  if (ys[0] - xs[n-1] > 0) {
    for (int i=xs[n-1]+1; i<= ys[0]; i++){
      if (i > x && i <= y) {
        flag = 1;
      }
    }
  }


  if (flag == 1)
    cout << "No War" << endl;
  else
    cout << "War" << endl;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
  int n,m,k,i,j,x,kotae=0;
  scanf("%d%d",&n,&m);
  int a[m];
  for(i=0;i<m;i++){
    a[i]=0;
  }
  for(i=0;i<n;i++){
    scanf("%d",&k);
    for(j=0;j<k;j++){
      scanf("%d",&x);
      a[x-1]++;
    }
  }
  for(i=0;i<m;i++){
    if(a[i]==n){
      kotae++;
    }
  }
  printf("%d",kotae);
  return 0;
}
      


Measured memory_bytes: 128
import math
N, D = map( int, input().split() )
X = [list(map(int, input().split())) for _ in range(N)]
result = 0

for i in range(N):
    for j in range(i, N):
        if i != j:
            tmp = 0.0
            for k in range(D):
                tmp += abs(X[i][k] - X[j][k]) ** 2
            tmp = math.sqrt(tmp)
            if tmp.is_integer():
                result += 1

print(result)

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

int main() {
	int a,b,c;
	cin>>a>>b>>c;
	int ne=a-b;
	if(ne>=c)
	cout<<"0";
	else
	{
		cout<<c-ne;
	}
	
	return 0;
}

Measured memory_bytes: 256
/*
    Author: isaf27 (Ivan Safonov)
*/

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

//defines
typedef long long ll;
typedef double ld;
#define TIME clock() * 1.0 / CLOCKS_PER_SEC
#define fast_read cin.sync_with_stdio(0)
#define nul point(0, 0)
#define str_to_int(stroka) atoi(stroka.c_str())
#define str_to_ll(stroka) atoll(stroka.c_str())
#define str_to_double(stroka) atof(stroka.c_str())
#define what_is(x) cerr << #x << " is " << x << endl
#define solve_system int number; cin >> number; for (int i = 0; i < number; i++) solve()
#define solve_system_scanf int number; scanf("%d", &number); forn(i, 0, number) solve()

//permanent constants
const ld pi = 3.141592653589793238462643383279;
const ld log23 = 1.58496250072115618145373894394781;
const ld eps = 1e-10;
const ll INF = 1e18 + 239;
const ll prost = 239;
const int two = 2;
const int th = 3;
const ll MOD = 1e9 + 7;
const ll MOD2 = MOD * MOD;
const int BIG = 1e9 + 239;
const int alf = 26;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const int dxo[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dyo[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
const int dig = 10;
const string str_alf = "abcdefghijklmnopqrstuvwxyz";
const string str_alf_big = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const int day[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int digarr[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
const int bt = 31;

//easy functions
template< typename T >
inline T gcd(T a, T b) { return a ? gcd(b % a, a) : b; }
template< typename T >
inline T lcm(T a, T b) { return (a / gcd(a, b)) * b; }
inline bool is_down(char x) { return ('a' <= x && x <= 'z'); }
inline bool is_upper(char x) { return ('A' <= x && x <= 'Z'); }
inline bool is_digit(char x) { return ('0' <= x && x <= '9'); }
ll power(ll a, int k)
{
    ll ans = 1;
    while (k)
    {
        if (k & 1) ans = (ans * a) % MOD;
        ans = (ans * ans) % MOD;
        k >>= 1;
    }
    return ans;
}

//random
mt19937 rnd(239);

//constants
const int M = 3 * 1e5 + 239;
const int N = 2 * 1e3 + 239;
const int L = 20;
const int T = (1 << 19);
const int B = trunc(sqrt(M)) + 1;
const int X = 10;

// Code starts here

int n;
string s;
int pref[two][M];

int main()
{   //*
    #ifdef ONPC
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif /**/
    fast_read;
    cin >> n >> s;
    pref[0][0] = 0;
    pref[1][0] = 0;
    for (int i = 0; i < n; i++)
    {
        pref[0][i + 1] = pref[0][i];
        pref[1][i + 1] = pref[1][i];
        if (s[i] == 'E')
            pref[0][i + 1]++;
        else
            pref[1][i + 1]++;
    }
    int ans = n;
    for (int i = 0; i < n; i++)
        ans = min(ans, pref[1][i] + pref[0][n] - pref[0][i + 1]);
    cout << ans;
    return 0;
}


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

using namespace std;

#define intt long long

const int N = 200005;

intt n;

int main() {

	cin >> n;
	if (n % 2) {
		cout << 0 << '\n';
		return 0;
	}
	n /= 2;
	intt k = 5;
	intt ans = 0;
	while (k <= n) {
		ans += n / k;
		k *= 5;
	}
	cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;

int main(){

int W;
int H;
int x;
int y;
int r;

cin >> W >> H >> x >> y >> r ;

if(x >= r && (W-r) >= x && y >= r && (H-r) >= y ){
cout << "Yes" << endl;
}
else{
cout << "No" << endl;
}
}

Measured memory_bytes: 3088
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Linq.Expressions;
using System.Text;
class Simple {
    int N;
    int[] A, B;
    void Solve() {
        //input
        N = io.Int;
        A = new int[N];
        B = new int[N];
        for (int i = 0; i < N; ++i) {
            A[i] = io.Int;
            B[i] = io.Int;
        }
        //cal
        var worstA = 0;
        var worstB = int.MaxValue;
        for(int i = 0; i < N; ++i) {
            if (worstA < A[i]) {
                worstA = A[i];
                worstB = B[i];
            }
        }
        var ans = worstA + worstB;
        //ret
        Console.WriteLine(ans);
    }
    SimpleIO io = new SimpleIO();
    public static void Main(string[] args) { new Simple().Stream(); }
    void Stream() {
        Solve();
        io.writeFlush();
    }
}
class SimpleIO {
    SimpleIO(bool isAutoFlush = false) { this.isAutoFlush = isAutoFlush; }
    string[] nextBuffer;
    int BufferCnt;
    char[] cs = new char[] { ' ' };
    public bool isAutoFlush;
    StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
    public SimpleIO() {
        nextBuffer = new string[0];
        BufferCnt = 0;
        if(!isAutoFlush)
            Console.SetOut(sw);
    }
    public string Next() {
        if (BufferCnt < nextBuffer.Length)
            return nextBuffer[BufferCnt++];

        string st = Console.ReadLine();
        while (st == "")
            st = Console.ReadLine();
        nextBuffer = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        BufferCnt = 0;
        return nextBuffer[BufferCnt++];
    }
    public string String => Next();
    public char Char => char.Parse(String);
    public int Int => int.Parse(String);
    public long Long => long.Parse(String);
    public double Double => double.Parse(String);
    public void writeFlush() { Console.Out.Flush(); }
}


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

int main()
{
    int N, now,cnt;
    cin >> N;
    now = 0;
    cnt = 0;
    vector<int> Ass(N);
    bool ans = false;
    for (int i = 0; i < N;i++){
        cin >> Ass.at(i);}
    for (int i = 0; i < N+1;i++){
        now = Ass.at(now) - 1;
        cnt++;
        if (now==1){
            ans = true;
            break;
        }
    }
    if (ans)
        cout << cnt << endl;
    else
        cout << -1 << endl;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll x;
  cin>>x;
  for(ll i=1;i*100<=x;i++){
    ll zan=x-100*i;
    if(0<=zan&&zan<=5*i) {
      cout<<1<<endl;
      return 0;
    }
  }
  cout<<0<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define endl '\n'
using namespace std;
int main()
{
    fastio;
    long long n,weight,i,j;
    cin>>n>>weight;
    long long matrix[n+1][weight+1]={0};
    memset(matrix,0,sizeof(matrix));
    long long a[n],w[n];
    for(i=1;i<=n;i++)
    {
        cin>>w[i]>>a[i];
    }
    memset(matrix,0,sizeof(matrix));
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=weight;j++)
        {
            if(w[i]>j)
            {
                matrix[i][j]=matrix[i-1][j];
            }
            else
            {
                matrix[i][j]=max(a[i]+matrix[i-1][j-w[i]],matrix[i-1][j]);
            }
        }
    }
    cout<<matrix[n][weight];
    return 0;
}


Measured memory_bytes: 79104
#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); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define bit(n) (1<<(n))
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1;} return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1;} return 0;}
int const INF = 1001001001;


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

int N,Q;
cin >> N >> Q;

map<int,vi> add;
map<int,vi> era;
map<int,int> mp;

rep(i,N) {
    int s,t,x;
    cin >> s >> t >> x;
    add[max(0,s-x)].push_back(x);
    era[max(1,t-x)].push_back(x);
    mp[max(0,s-x)] = 0;
    mp[max(1,t-x)] = 0;
}
rep(i,Q) {
    int d;
    cin >> d;
    mp[d] = 1;
}

set<int> st;

for(auto x : mp) {

    for(auto erx : era[x.first]) {
        st.erase(erx);
    }
    for(auto adx : add[x.first]) {
        st.insert(adx);
    }
    if(x.second == 1) {
        if(!st.empty()) {
            cout << *st.begin() << endl;
        }
        else {
            cout << -1 << endl;
        }
    }
}

return 0;
}

Measured memory_bytes: 145024
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>

typedef long long ll;
const ll INF = (ll)1e18 + 1;
const ll MOD = 1e9 + 7;

void print(){ std::cout << std::endl; }
template <typename H> void print(H head) { std::cout << head << std::endl; }
template <typename H, typename... T> void print(H head, T... tail){ std::cout << head << " ", print(tail...); }

ll gcd(ll a, ll b)
{
  while (b > 0) {
    a = a % b;
    std::swap(a, b);
  }
  return a;
}

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

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

  ll N;
  std::cin >> N;
  std::vector< ll > vt(N, 0LL);

  ll ans = 1LL;
  for (ll i = 0; i < N; i++) {
    std::cin >> vt[i];
    ans = lcm(ans, vt[i]);
  }

  print(ans);
  return 0;
}


Measured memory_bytes: 256
import sys
def longest_common_subsequence(line1, line2):
    n_rows = len(line2) + 1
    array = [0] * n_rows

    ix_ = [x for x in range(n_rows)]
    ix = [x+1 for x in range(n_rows)]

    for l1_letter in line1:
        prev_array = array[:]
        for i_row_, i_row, l2_letter in zip(ix_, ix, line2):
            if l1_letter == l2_letter:
                array[i_row] = prev_array[i_row_] + 1
            else:
                up = prev_array[i_row]
                left = array[i_row_]
                array[i_row] = up if up > left else left
    return array[-1]

calc_time = False
if calc_time: import time; start = time.time()
def main():
    n = int(input())
    lines = sys.stdin.readlines()
    for i in range(0, 2*n, 2):
        ans = longest_common_subsequence(lines[i].rstrip(), lines[i+1].rstrip())
        print(ans)
    return

main()
if calc_time:print("elapsed:",time.time()-start)


Measured memory_bytes: 5680
// E - Crested Ibis vs Monster
#include <bits/stdc++.h>
using namespace std;
#define rp(i,s,e) for(int i=(s);i<(e);++i)
int A[1000], B[1000], dp[10000+1], INF = INT_MAX>>2;
int H,N;

int main(){
	cin>>H>>N;
	rp(i,0,N) cin>>A[i]>>B[i];
	rp(i,1,H+1) dp[i] = INF;
	dp[0] = 0;
	rp(i,0,N)
		rp(j,1,H+1)
			dp[j] = min(dp[j], (j-A[i]<0? 0:dp[j-A[i]]) + B[i]);
	cout<< dp[H] <<endl;
}

Measured memory_bytes: 256
import math
a,b,h,m=map(int,input().split())
total_m=60*h+m

angle_b=360*m/60
angle_a=360*(total_m/(12*60))

angle=min(abs(angle_a-angle_b),360-abs(angle_a-angle_b))
cosθ=math.cos(math.radians(angle))

c=(a**2+b**2-2*a*b*cosθ)
c=c**(1/2)
print(c)

Measured memory_bytes: 9632
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef pair<int,int>P;
typedef pair<P,int>P1;
#define pb push_back
#define fi first
#define sc second
int n,a[100005],b[100005];
bool ex, two;
vector<P>vec,vec3;
int xx;
struct uf{
    int par[1000005];
    void init(){ rep(i,100005) par[i] = i;;}
    int find(int x){ 
        if(par[x] == x) return x;
        else return par[x] = find(par[x]);
    }
    void unite(int x,int y){
        x = find(x); y = find(y);
        if(x == y) return;
        par[x] = y; xx--;
    }
}kaede;
int main(){
    cin >> n; xx = n;
    rep(i,n) cin >> a[i];
    rep(i,n) cin >> b[i];
    rep(i,n) vec.pb(P(b[i],i));
    rep(i,n) vec3.pb(P(a[i],i));
    sort(vec.begin(),vec.end());
    sort(vec3.begin(),vec3.end());
    int up = 0;
    ex = true; kaede.init();
    rep(i,vec.size()){
        while(up < vec3.size() && vec3[up].fi <= vec[i].fi) up++;
        if(up-i <= 0) ex = false;
        else if(up-i >= 2) two = true;
        kaede.unite(vec3[i].sc,vec[i].sc);
    }
    //cout << ex << two << endl;
    if(!ex){ puts("No"); }
    else if(two){
        puts("Yes");
    }
    else if(xx == 1){
        puts("No");
    }
    else puts("Yes");
}

Measured memory_bytes: 5876
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#define cinf(n,x,y,z) for(int i=0;i<(n);i++) cin >> x[i]>>y[i]>>z[i];
typedef long long int ll;
using namespace std;

int main(){
	int n,a,b; cin >>n>>a>>b;
	string s; cin >>s;
	int cnta=0; int cntb=0;
	for(int i=0;i<n;i++){
		if(s[i]=='c') cout << "No" << endl;
		else if(s[i]=='a'&&cnta+cntb<a+b){
			cout << "Yes" << endl;
			cnta++;
		}
		else if(s[i]=='b'&&a+b>cnta+cntb&&cntb<b){
			cout << "Yes" << endl;
			cntb++;
		}
		else cout << "No" << endl;
	}
}

Measured memory_bytes: 896
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cassert>
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define MAX 10000
using namespace std;
int n,m;
int par[MAX+1];

struct Pox
{
  int from,to,cost;
  Pox(int from = -1,int to = -1,int cost = -1):from(from),to(to),cost(cost){}
};

vector<Pox> G;

bool cmp(const Pox& p1,const Pox& p2){ return p1.cost < p2.cost; }

void init(){ rep(i,MAX)par[i] = i; }

int find(int x)
{
  if(x == par[x])return x;
  return par[x] = find(par[x]);
}

void unit(int x,int y)
{
  x = find(x);
  y = find(y);
  if(x != y) par[x] = y;
}

bool same(int x,int y){ return find(x) == find(y); }

int kruskal(int st)
{
  init();
  int mex = -(1<<29);
  int gsize = G.size();
  int cnt = 0;
  REP(i,st,gsize)
    {
      Pox pox = G[i];
      if(!same(pox.from,pox.to))
	{
	  cnt++;
	  assert(0 <= pox.from && pox.from < MAX);
	  assert(0 <= pox.to   && pox.to   < MAX);
	  unit(pox.from,pox.to);
	  mex = max(mex,pox.cost);
	}
    }
  if(cnt != n-1)return (1<<29);
  return mex-G[st].cost;
}


int main()
{
  while(cin >> n >> m,n|m)
    {
      G.clear();
      if(true)
	{
	  int a,b,w;
	  rep(i,m)
	    {
	      cin >> a >> b >> w;
	      a--,b--;
	      G.push_back(Pox(a,b,w));
	    }
	}
      int ans = (1<<29);
      sort(G.begin(),G.end(),cmp);
      rep(i,G.size()){ ans = min(ans,kruskal(i)); }
      cout << (ans == (1<<29)?-1:ans) << endl;
    }
  return 0;
}

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

int main(){
  string a,b;
  cin >> a;
  cin >> b;
  if(a.size()>b.size()){
    cout << "GREATER" << endl;
  }else if(a.size()<b.size()){
    cout << "LESS" << endl;
  }else{
    if(a>b){
      cout << "GREATER" << endl;
    }else if(a<b){
      cout << "LESS" << endl;
    }else{
    cout << "EQUAL" << endl;
  }
  }
  return 0;
}


Measured memory_bytes: 256