akhauriyash/Code-Regression huggingface dataset:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main{
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

    static  class Item{
        int weight;
        long value;

        public Item(int weight, long value) {
            this.weight = weight;
            this.value = value;
        }
    }

    public static void main(String[] args) {

    FastReader sc = new FastReader();

    int n = sc.nextInt();
    int w = sc.nextInt();

    Item ap[] = new Item[n+1];
    ap[0] = new Item(0,0);
    for(int i=1; i<n+1; i++){
        ap[i] = new Item(sc.nextInt(), sc.nextLong());
    }

    long table[][] = new long[n+1][w+1];

    for(int i=0; i<n+1; i++){
        for(int j=0; j<w+1; j++){
            if(i==0 || j==0){
                table[i][j] = 0;
            }else if(ap[i].weight<=j){
                table[i][j] = Math.max(ap[i].value+table[i-1][j-ap[i].weight],table[i-1][j]);
            }else{
                table[i][j] = table[i-1][j];
            }

        }
    }
    System.out.println(table[n][w]);

    }

}


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

int main(){
  string s;
  cin>>s;
  int n=s.size();
  
  int first;
  int second;


  for(int i=n-1;i>=0;i--){
    if(s[i]=='A'){
      first=i;
    }
  }
  
  for(int i=0;i<n;i++){
    if(s[i]=='Z'){
      second=i;
    }
  }
  
  cout<< second-first+1 <<endl;
  return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#define FAST_IO   ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define Relocate freopen("./in.txt","r",stdin),freopen("./out.txt","w",stdout)
#define up(mi,a,b) for(mi=a;mi<=b;++mi)
#define down(mi,b,a) for(mi=b;mi>=a;--mi)
#define mfill(a,v) memset(a,v,sizeof(a))
#define INF 0x3f3f3f3f
#define MAX 5000010
#define v_n 5005
#define LL long long
#define ULL unsigned long long 
#define e_n 50005
#define eps 0.000000001
#define Blen 31 
const LL MOD = 998244353;
using namespace std;
LL A[MAX];
vector<LL> hh,hh1;
int main(void)
{
	int i, j, k;
	//Relocate;
	FAST_IO;
	int N;
	LL ans = 0;
	LL mn = INF;
	cin >> N;
	up(i, 1, N)
	{
		cin >> A[i];
		ans += abs(A[i]);
		mn = min(mn, abs(A[i]));
		if (A[i] >= 0)
		{
			hh.push_back(A[i]);
		}
		else
		{
			hh1.push_back(A[i]);
		}
	}
	//cout << ans << endl;
	int pa = hh.size();
	int pb = hh1.size();
	if (pb & 1)
	{
		cout << ans - 2 * mn << endl;
	}
	else
	{
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 2296
import numpy as np

N = int(input())
lst=[]
for i in range(N):
    lst.append(list(map(int,input().split())))
AB=np.array(lst).reshape(N,2).T
A = AB[0]
B = AB[1]
ind = B.argsort()
A = A[ind]
B = B[ind]
if np.all(A.cumsum() <= B):
    print("Yes")
else:
    print("No")

Measured memory_bytes: 68944
n, m=map(int, input().split())
x=list(map(int, input().split()))
x=sorted(x)
y=[0]*(m-1)

for i in range(m-1):
    y[i]=x[i+1] - x[i]
z=sorted(y)

if n>=m:
    print(0)
else:
    print(sum(z[0:m-n]))


Measured memory_bytes: 13968
#include<stdio.h>

int main(){
	int N,i,j,n,d,map[201][2],minx,maxx,miny,maxy;
	
	while(0<=scanf("%d",&N)){
		if(0==N) break;
		
		map[0][0]=0;
		map[0][1]=0;
		for(i=1;i<N;i++){
			scanf("%d%d",&n,&d);
			switch (d){
			  case 0:
				map[i][0]=map[n][0]-1;
				map[i][1]=map[n][1];
				break;
			  case 1:
				map[i][0]=map[n][0];
				map[i][1]=map[n][1]-1;
				break;
			  case 2:
				map[i][0]=map[n][0]+1;
				map[i][1]=map[n][1];
				break;			  
			  case 3:
				map[i][0]=map[n][0];
				map[i][1]=map[n][1]+1;
				break;
			}
		}
		
		minx=200;
		miny=200;
		maxx=-200;
		maxy=-200;
		for(i=0;i<=N-1;i++){
			if(minx>map[i][0]) minx=map[i][0];
			if(miny>map[i][1]) miny=map[i][1];
			if(maxx<map[i][0]) maxx=map[i][0];
			if(maxy<map[i][1]) maxy=map[i][1];
		}
		printf("%d %d\n",maxx-minx+1,1+maxy-miny);
	}
	return 0;
}

Measured memory_bytes: 0
using System;

class Practice
{
    public static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        string[] str = Console.ReadLine().Split(' ');
        int[] a = new int[n];
        for (int i = 0; i < n; ++i)
        {
            a[i] = int.Parse(str[i]);
        }
        for (int i = n - 1; i >= 0; --i)
        {
            if (i != n - 1) Console.Write(' ');
            Console.Write(a[i]);
        }
        Console.WriteLine();
    }
}


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

typedef long long ll;

using namespace std;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string n;
    int k;
    cin >> n >> k;
    int len = n.length();
    ll dp[n.length() + 1][k + 1][2];
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i <= len; i++) {
        dp[i][0][0] = 1;
    }
    dp[1][1][0] = n[0] - '1';
    dp[1][1][1] = 1;
    for (int i = 2; i <= len; i++) {
        for (int l = 1; l <= k; l++) {
            ll val0 = dp[i - 1][l][0] + dp[i - 1][l - 1][0] * 9;
            ll val1;
            if (n[i - 1] != '0') {
                val0 += dp[i - 1][l][1] + dp[i - 1][l - 1][1] * (n[i - 1] - '0' - 1);
                val1 = dp[i - 1][l - 1][1];
            } else {
                val1 = dp[i - 1][l][1];
            }
            dp[i][l][0] = val0;
            dp[i][l][1] = val1;
        }
    }
    cout << dp[len][k][0] + dp[len][k][1] << endl;
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cmath>

const double pi = acos(-1);

int main() {
	double a, b, angC;
	scanf("%lf%lf%lf", &a, &b, &angC);
	double p = a * sin(angC / 180 * pi), S = p * b / 2.0, H = S * 2.0 / a;
	double c = sqrt(pow(a, 2) + pow(b, 2) - 2 * a * b * cos(angC / 180 * pi)), L = c + a + b;
	printf("%.8lf\n%.8lf\n%.8lf", S, L, H);
	return 0;
}


Measured memory_bytes: 3092
#include<bits/stdc++.h>
using namespace std;
long long mod=1e9+7,n;
vector<vector<long long>> multiply(vector<vector<long long>>& a,vector<vector<long long>>& b)
{
  vector<vector<long long>> v(n,vector<long long>(n));
  for(int i=0;i<n;i++)
  {
    for(int j=0;j<n;j++)
    {
      for(int k=0;k<n;k++){
        v[i][j]+=a[i][k]*b[k][j];
        v[i][j]=v[i][j]%mod;
    }
    }
  }
  return v;
}
vector<vector<long long>> power(vector<vector<long long>>& v,long long k)
{
  if(k==1)
  return v;

  auto res=power(v,k/2);
  auto z=multiply(res,res);
  if(k&1)
  return multiply(z,v);
  else
  return z;
}
int main()
{
  long long k;
  cin>>n>>k;
  vector<vector<long long>> v(n,vector<long long>(n,0));
  for(int i=0;i<n;i++)
  {
    for(int j=0;j<n;j++)
      cin>>v[i][j];
  }
  auto res=power(v,k);
  long long ans=0;
  for(int i=0;i<n;i++)
  {
    for(int j=0;j<n;j++)
      ans=(ans+res[i][j])%mod;
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 3612
#include <algorithm>
#include <iterator>
#include <iostream>
#include <iomanip>
#include <cassert>
#include <utility>
#include <string>
#include <vector>
#include <limits>
#include <queue>
#include <cmath>
#include <map>
#include <set>

using namespace std;

typedef long long ll;

const int INF = numeric_limits<int>::max();

int main()
{
    int n, k;
    cin >> n >> k;

    vector<int> h(n);

    for(int i = 0; i < n; ++i)
        cin >> h[i];

    vector<int> dp(n, INF);
    dp[0] = 0;

    for(int i = 1; i < n; ++i) {
        for(int kk = 1; kk <= k; ++kk) {
            if(i - kk < 0)
                break;
            dp[i] = min(dp[i], dp[i - kk] + std::abs(h[i - kk] - h[i]));
        }
    }

    // copy(dp.begin(), dp.end(), ostream_iterator<int>(cout, " "));
    // cout << endl;

    cout << dp[n - 1] << endl;

    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define WHOLE(v) (v).begin(), (v).end()
#define REV_WHOLE(v) (v).rbegin(), (v).rend()
using i64 = int64_t;
using namespace std;
int main() {
    int ans = 0;
    int M, D;
    cin >> M >> D;
    for(int m = 1; m <= M; m++) {
        for(int d = 1; d <= D; d++) {
            int d1 = d % 10;
            int d10 = d / 10;
            if(d1 >= 2 && d10 >= 2 && d1 * d10 == m) {
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

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

using ll = long long;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define REP(i, n) FOR(i, 0, n)
#define ALL(c) (c).begin(), (c).end()
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;}
const int MOD = 1000000007;

int main() {
    double w, h, x, y;
    cin >> w >> h >> x >> y;

    if (w / 2 == x && h / 2 == y) {
        cout << fixed << setprecision(10) << (double)h * (double)w / 2.0 << " 1" << endl;
    } else {
        cout << fixed << setprecision(10) << (double)h * (double)w / 2.0 << " 0" << endl;
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>

#define rep(i,n) for(int i=0;i<n;i++)
#define rp(i,c) rep(i,(c).size())
#define fr(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define mp make_pair
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define dbg(x) cerr<<#x<<" = "<<(x)<<endl

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
const int inf=1<<28;
const int MX=1000;

int n,s[MX],t[MX],p[MX];
pair<int,pi> in[MX];
int dp[366][366];

int main()
{
	while(scanf("%d",&n),n)
	{
		rep(i,n)scanf("%d%d%d",&in[i].first,&in[i].second.first,&in[i].second.second);
		sort(in,in+n);
		rep(i,n)s[i]=in[i].first,t[i]=in[i].second.first,p[i]=in[i].second.second;
		
		rep(i,366)rep(j,366)dp[i][j]=0;
		
		rep(i,n)
		{
			for(int k=365;k>=0;k--)for(int j=s[i]-1;j>=0;j--)
			{
				dp[t[i]][k]=max(dp[t[i]][k],dp[j][k]+p[i]);
				dp[k][t[i]]=max(dp[k][t[i]],dp[k][j]+p[i]);
			}
		}
		int ans=0;
		rep(i,366)rep(j,366)ans=max(ans,dp[i][j]);
		printf("%d\n",ans);
	}
	return 0;
}

Measured memory_bytes: 1424
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

int main() {
  int n; cin >> n;
  int ans = 0;
  if (n > 9) {
    ans += 9;
    if (n > 999) {
      ans += 900;
      if (n > 99999) {
        ans += 90000;
      } else {
        ans += max(0, n - 9999);
      }
    } else {
      ans += max(0, n - 99);
    }
  } else {
    ans = n;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
/*************************************************************************
	> File Name: 1.cpp
	> Author: Knowledge_llz
	> Mail: 925538513@qq.com 
	> Blog: https://blog.csdn.net/Pig_cfbsl 
	> Created Time: 2020/5/2 20:10:44
 ************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define LL long long
using namespace std;
int read(){
	char x=getchar(); int u=0,fg=0;
	while(!isdigit(x)){ if(x=='-') fg=1; x=getchar(); }
	while(isdigit(x)){ u=(u<<3)+(u<<1)+(x^48); x=getchar(); }
	return fg?-u:u;
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.in", "r", stdin);
	freopen("output.out", "w", stdout);
#endif
	int k=read(),a=read(),b=read();
	bool flag=0;
	For(i,a,b)
		if(i%k==0){
			flag=1;
			break;
		}
	if(flag) printf("OK\n");
	else printf("NG\n");
	return 0;
}


Measured memory_bytes: 3584
#include<iostream>
#include<string>
#define ll long long int
#define ld long double
#define pi acos(-1)
#define pb push_back
using namespace std;
int main()
{
    ll i,j,k,a,b,c,n,t,m,p,q,d,e,f,x,y,g,z,h;
    ld aa,bb,cc,dd,ee,ff,kk,gg;
//    vector<ll > v,s,vv;
//    vector<string> vs;
//    map<ll,ll> sa,ta,ma;
//    priority_queue<char,vector<ll>,greater<ll> > aq,tq,pq;
    string st,et,ft,pt,ct;
//    deque<ll> de;
//    ios_base::sync_with_stdio(false);
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    cin>>n;
    c = 0;
    d = 0;
    e = 0;
    f = 0;
    for(i=0;i<n;i++){
        cin>>st;
        if(st[0]=='A')c++;
        else if(st[0]=='W')d++;
        else if(st[0]=='T')f++;
        else if(st[0]=='R')e++;
    }
    cout<<"AC x "<<c<<endl<<"WA x "<<d<<endl<<"TLE x "<<f<<endl<<"RE x "<<e<<endl;
}


Measured memory_bytes: 3632
#include<iostream>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef pair<int,int> P;
int main(){
	int N,M,a,b,C[55]={},ans=0;
	vector<int> v[55];
	cin>>N>>M;
	for(int i=0;i<M;++i){
		cin>>a>>b;
		C[a]++;
		C[b]++;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	queue<int> que;
	for(int i=1;i<=N;++i){
		if(C[i]==1){
			++ans;
			que.push(v[i][0]);
		}
	}
	while(!que.empty()){
		int n=que.front();que.pop();
//		cout<<n<<" "<<C[n]<<endl;
		if(C[n]==1)continue;
		C[n]--;
		if(C[n]==1){
			for(int i=0;i<v[n].size();++i){
				que.push(v[n][i]);
				if(C[v[n][i]]>1)ans++;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
a,b,c,k = map(int,input().split())
def max():
  a_0=1
  b_0=-1

  if a>=k:
    print(a_0 * k)
    return
  
  else :
    if k-a<b:
      return

    else:
      d=k-a-b
      print(a_0 * a + b_0 * d)

max()

Measured memory_bytes: 9144
import sys
import numpy as np

n, a, *x = map(int, sys.stdin.read().split())

def main():
    m = 2500
    dp = np.zeros((n + 1, m + 1), dtype=np.int64)
    dp[0, 0] = 1
    for i in range(n):
        ndp = np.copy(dp)
        for j in range(1, n + 1):
            ndp[j][x[i]:] += dp[j-1][:m-x[i]+1]
        dp = ndp
    i = np.arange(1, n + 1)
    print(np.sum(dp[i, i * a]))

if __name__ ==  '__main__':
    main()

Measured memory_bytes: 14424
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		int N = int.Parse(Console.ReadLine());
		int ca = 0;
		int ans = 0;
      	string[] str = Console.ReadLine().Split();
		for(var i=0;i<N;i++){
			int cn = int.Parse(str[i]);
			if(cn>ca){
				ans += cn-ca;
			}
			ca = cn;
		}
		Console.WriteLine(ans);
	}
}

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

int main()
{
	int N;
	int ecnt = 0, wcnt = 0;
	int minv;
	string S;

	cin >> N >> S;
	for ( int i = 0; i < N; i++ ) {
		if ( S[i] == 'E' ) ecnt++;
	}
	minv = N;
	for ( int i = 0; i < N; i++ ) {
		if ( S[i] == 'E' ) ecnt--;
		minv = min(minv, wcnt + ecnt);
		if ( S[i] == 'W' ) wcnt++;
	}
	cout << minv << endl;
	return ( 0 );
}


Measured memory_bytes: 900
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <tuple>
#include <cassert>
#include <functional>
#include <set>
#include <deque>
#include <list>
using namespace std;
typedef long long ll;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
#define LNF __LONG_LONG_MAX__
const ll MOD = 1000000007;
const int MAX = 200000;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
// 法mでのaの逆元を計算
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
//最大公約数
long long gcd(long long x, long long y){
    if(y==0) return x;
    else return gcd(y,x%y);
}
//最小公倍数
long long lcm(long long x, long long y){
    return x / gcd(x, y) * y;
}
// nが大きく,kが10^7程度の時の二項係数
long long com[200005];
void combination(long long n,long long k){
    com[0] = 1;
    for(int i=1;i<=k;i++){
        com[i] = (com[i-1]*(n-i+1)%MOD)*modinv(i,MOD)%MOD;
    }
}

int main(){
    int A,B; cin >> A >> B;
    if(A%3==0 || B%3==0 || (A+B)%3==0){
        cout << "Possible" << endl;
    }else{
        cout << "Impossible" << endl;
    }
    return 0;
}


Measured memory_bytes: 3560
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define SORTR(v,n) sort(v, v+n, greater<int>());
#define ll long long
// #define int long long
#define pb push_back
#define INF 100000000
using namespace std;
typedef pair<int, int> P; // cannot use P as var
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

const int MAX_n = 100000;
int n,a[MAX_n];




signed main(){

    scanf("%d", &n);
    REP(i,n){
        scanf("%d", &a[i]);
    }
    // odd+odd=even, even+even=even
    int count=0;
    REP(i,n){
        if(a[i]%2) count++;
    }
    if(count%2){
        printf("NO\n");
    }else{
        printf("YES\n");
    }


    return 0;
}

Measured memory_bytes: 640
#include<stdio.h>
#define N 10000

int search(int*, int, int);

int main(){
  int i ,S[N+1],n,q,key,count=0;

  scanf("%d",&n);
  for(i=0;i<n;i++)
    {
      scanf("%d",&S[i]);
    }
  scanf("%d",&q);
  for(i=0;i<q;i++)
    {
      scanf("%d",&key);
      if(search(S,n,key)==1)
	{
	  count++;
	}
    }
  printf("%d\n",count);
  return 0;
}
int search(int S[],int n , int k)
{
  int i = 0;
  S[n]=k;
  while(S[i]!=k)
    {
      i++;
    }
  if(i == n)return 0;
  return 1;
}
    

Measured memory_bytes: 640
// 2018/05/28 Tazoe

#include <iostream>
using namespace std;

int gcd(int x, int y)
{
	if(y==0)
		return x;

	return gcd(y, x%y);
}

int main()
{
	int x, y;
	cin >> x >> y;

	int g = gcd(x, y);

	cout << (x+1)+(y+1)-(g+1) << endl;

	return 0;
}



Measured memory_bytes: 3096
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i, s) for (int i = 0; i < s; ++i)
#define ALL(v) (v).begin(), (v).end()
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define DEBUG
#define int long long
#define INF 1e9
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; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }
template<class T>void show(vector<T>v){for (int i = 0; i < v.size(); i++){cerr<<v[i]<<" ";}cerr<<"\n";}
typedef long long ll;

int x[100010],y[100010];
bool ok[100010];
int count_b[100010];
signed main(){
    int n,m;
    cin>>n>>m;
    for (int i = 0; i < m; i++)
    {
        cin>>x[i]>>y[i];
        x[i]--,y[i]--;
    }
    ok[0]=true;
    for (int i = 0; i < n; i++)
    {
        count_b[i]=1;
    }
    
    for (int i = 0; i < m; i++)
    {
        if(ok[x[i]] && count_b[x[i]]==1){
            ok[x[i]]=false;
            count_b[x[i]]--;
            ok[y[i]]=true;
            count_b[y[i]]++;
        }
        else if(ok[x[i]] && count_b[x[i]]>1){
            count_b[x[i]]--;
            ok[y[i]]=true;
            count_b[y[i]]++;
        }
        else if(!ok[x[i]]){
            count_b[x[i]]--;
            count_b[y[i]]++;
        }

    }
    int res=0;
    for (int i = 0; i < n; i++)
    {
        if(ok[i]) res++;
    }
    cout<<res<<endl;
    

    return 0;
}

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

const int MIN = -(int)1e9;
const int MAX = (int)1e9;
const int X = MAX + 1;

int main() {
  int n;
  while (cin >> n, n) {
    vector<int> a(n + 2);
    for (int i = 0; i < n; i++) {
      string s;
      cin >> s;
      a[i + 1] = s.front() == 'x' ? X : stoi(s);
    }
    a[0] = MAX + 3;
    a[n + 1] = (n + 1) % 2 ? MIN - 3 : MAX + 3;
    int bot = MIN - 2, top = MAX + 3;
    for (int i = 0; i < n; i++) {
      if (a[i + 1] == X) {
        if (a[i + 2] == X) {
          bot = top;
        } else {
          if ((i + 1) % 2) {
            top = min(top, min(a[i], a[i + 2]));
          } else {
            bot = max(bot, max(a[i], a[i + 2]) + 1);
          }
        }
      } else {
        if (a[i + 2] != X) {
          if ((i + 1) % 2) {
            if (a[i + 1] >= a[i + 2]) {
              bot = top;
            }
          } else {
            if (a[i + 1] <= a[i + 2]) {
              bot = top;
            }
          }
        }
      }
    }
    if (top - bot == 1) {
      cout << bot << endl;
    } else {
      cout << (top - bot > 1 ? "ambiguous" : "none") << endl;
    }
  }
}



Measured memory_bytes: 3032
#include <iostream>

using namespace std;

int main()
{
    string s;
    cin>>s;
    int cnt=0;
    int MS=0;
    s+='B';
    for(int i=0; i<s.size(); i++)
    {
        if(s[i]=='A' ||s[i]=='T'||s[i]=='G'||s[i]=='C')
        {
            cnt++;
        }
        else
        {
            MS=max(MS,cnt);
            cnt=0;
        }
    }
    cout<<MS<<endl;
    return 0;
}


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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

using ll = long long;
using ld = long double;

const int INF = 1e9;
const ld eps = 1e-9, pi = acos(-1.0);

string s;
int p;

int number() {
  int res = 0;
  while (p < (int)s.size() && isdigit(s[p])) {
    res = res * 10 + (int)(s[p] - '0');
    ++p;
  }
  return (res + 1) / 2;
}

int expr() {
  ++p;
  int res = 0;
  if (isdigit(s[p])) res = number();
  else {
    vector<int> v;
    while (s[p] != ']') {
      v.push_back(expr());
    }
    sort(ALL(v));
    res = accumulate(begin(v), begin(v) + ((int)v.size() + 1) / 2, 0);
  }
  ++p;
  return res;
}

int main() {
  int Q;
  cin >> Q;
  while (Q--) {
    cin >> s;
    p = 0;
    cout << expr() << endl;
  }
  return 0;
}

Measured memory_bytes: 3196
n = int(input())

def divisor(x):
  i = 1
  L = []
  while i*i <= n:
    if n%i == 0:
      L.append(i)
      L.append(n//i)
    i += 1
  L = list(set(L))
  return L

R = divisor(n)
S = []
for i in range(len(R)):
  S.append(R[i] + n//R[i] - 2)
  
print(min(S))  

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

using namespace std;

typedef long long ll;

const int MOD = 1e9 + 7;
const int N = 1e6 + 34;

int main()
{
    int a, b, c, k;
    cin >> a >> b >> c >> k;
    while (a >= b) b *= 2, k--;
    while (b >= c) c *= 2, k--;
    if (k >= 0) cout << "Yes";
    else cout << "No";
}


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

#define int long long
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

signed main(){
	int n;
	cin >> n;
	int memo[100010] = {};
	int a[100010];
	for(int i = 0;i < n;i++){
		cin >> a[i];
		a[i]--;
	}
	int now = 0;
	int cnt = 0;
	while(1){
		if(memo[now]) break;
		if(now == 1){
			cout << cnt << endl;
			return 0;
		}
		memo[now] = 1;
		now = a[now];
		cnt++;
	}
	cout << -1 << endl;
	return 0;
}


Measured memory_bytes: 5148
// Problem : C - One Quadrillion and One Dalmatians
// Contest : AtCoder - AtCoder Beginner Contest 171
// URL : https://atcoder.jp/contests/abc171/tasks/abc171_c
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
#define debug(x) cerr << #x << " = " << x << '\n'
#define debug_arr(a , n) for(int i = 0 ; i < n ; i++)cerr << a[i] << " "
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define vi vector<int>
#define vll vector<ll> 
#define all(x) (x).begin() , (x).end()
#define inf 1000000000
#define mod 1000000007

const int max_n = 1e5 + 9;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
ll power(ll a , ll b)
{
    ll prod = 1;
    while(b)
    {
        if(b&1)
        prod = (prod*a)%mod;
        a = (a*a)%mod;
        b >>= 1;
    }
    return prod;
}
int main()
{
  	ll n;
  	cin >> n;
  	
  	string s;
  	while(n > 0){
  		ll num = n % 26;
  		if(num == 0)num = 26;
  		
  		s += (char)(num + 'a' - 1);
  		n -= num;
  		n /= 26;
  		// if(num == 26)n -= 26;
  	}  
  	
  	reverse(s.begin() , s.end());
  	cout << s<< endl;
   	return 0;
}

Measured memory_bytes: 3640
#include <cmath>
#include <cstdio>

#include <stack>
#include <queue>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <numeric>
#include <string>
#include <array>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(x) x.begin(), x.end()

using namespace std;
typedef long long int ll;

int main() {
  ll n;
  cin >> n;
  vector<ll> x(n), v(n);
  rep(i, n) cin >> x.at(i);
  v = x;
  sort(all(v));
  size_t mid_h = x.size()/2;
  for (auto i:x){
    if(v.at(mid_h-1)>=i) cout << v.at(mid_h) << endl;
    else cout << v.at(mid_h -1) << endl;
  }

  return 0;
}

Measured memory_bytes: 5376
li = []

for i in range(5):
    tmp = int(input())
    li.append(tmp)

k = int(input())

flag = True
for i in range(4):
    for j in range(i,5):
        if abs(li[i] - li[j]) > k:
            flag = False
            break
    if flag is False:
        break
    
if flag is True:
    print("Yay!")
else:
    print(":(")

Measured memory_bytes: 3060
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
#define chmin(a, b) ((a) = min((a), (b)))
#define chmax(a, b) ((a) = max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;

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

const ll MOD = 1e9 + 7;
const ll INF = 1e18;
const double pi = acos(-1);
const double eps = 1e-10;

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

int main(){
    int n, l; cin>>n>>l;
    vector<int> v(n);
    for(int i=0; i<n; i++){
        v[i] = l + i;
    }

    int base = 0;
    for(int i=0; i<n; i++){
        base += v[i];
    }

    int ans;
    int gap = 1e9;
    for(int i=0; i<n; i++){
        int sum = 0;
        for(int j=0; j<n; j++){
            if(i == j) continue;

            sum += v[j];
        }

        if(abs(base - sum) < gap){
            gap = abs(base - sum);
            ans = sum;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(){
    char w[1000];
    int i,j;
    scanf("%s",w);
    for(i=0;w[i]!='\0';++i){
        printf ("%c",w[i]);
    }
    j=i-1;
    if (w[j] == 's'){
        printf("es");
    }else{
        printf("s");
    }
    return 0;
}

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


int main() {
  long long int a,b;
  cin >>a >> b ;
  
  if(a % 2 == 0){
 for(int i=1;i<=b;i++){
   
   if( a / (a+1-2*i) < 2){
   cout << i << " " << a+1-i << endl;
   }
     else{
       cout << i << " " << a-i << endl;
       
     }
   
 }
  }
  
  else{
    
  for(int i=1;i<=b;i++){
   
   
   cout << i << " " << a+1-i << endl; 
  
}
    
  }
}

Measured memory_bytes: 3616
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
using namespace std;
void solve(){
    int n;
    cin >> n;
    vector <int> C(n);
    vector <int> h(n);
    for (int i = 0; i < n; ++i) {
        cin >> h[i];
    }
    C[0] = 0;
    C[1] = abs(h[1] - h[0]);
    for (int j = 2; j < n; ++j) {
        C[j] = min(C[j - 1] + abs(h[j] - h[j - 1]), C[j - 2] + abs(h[j] - h[j - 2]));
    }
    cout << C[n - 1];
}

int main(){
    int t = 1;
    while(t--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 1024
//~ while (clock()<=69*CLOCKS_PER_SEC)
//~ #pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
//~ #pragma GCC optimize("Ofast")
//~ #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//~ #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

#define shandom_ruffle random_shuffle

using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vll=vector<ll>;
const int nax=1000*1007;
const ll mod=1000*1000*1000+7;

int n;
char wcz[nax];

ll ile[nax];

ll wyn=1;

int main()
{
	scanf("%d", &n);
	scanf("%s", wcz+1);
	for (int i=1; wcz[i]; i++)
	{
		ile[wcz[i]]++;
	}
	for (int i='a'; i<='z'; i++)
	{
		wyn=(wyn*(ile[i]+1))%mod;
	}
	wyn=(wyn+mod-1)%mod;
	printf("%lld\n", wyn);
	return 0;
}


Measured memory_bytes: 2304
n,a,b=map(int,input().split())
mod=10**9+7
ans=pow(2,n,mod)-1
p=1
for i in range(a):
    p*=n-i
    p*=pow(i+1,mod-2,mod)
    p%=mod
p2=1
for i in range(b):
    p2*=n-i
    p2*=pow(i+1,mod-2,mod)
    p2%=mod
print((ans-p-p2)%mod)


Measured memory_bytes: 40880
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int> v;
    for(int i=0;i<n;i++)
    {
        int tmp;
        cin>>tmp;
        v.push_back(tmp);
    }
    int T;
    cin>>T;
    while(T--)
    {
        int c,begin,end;
        cin>>c>>begin>>end;
        if(c==1)
        {
            cout<<*max_element(v.begin()+begin,v.begin()+end)<<endl;
        }
        else
        {
             cout<<*min_element(v.begin()+begin,v.begin()+end)<<endl;
        }
    }
}


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

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<pdd> vdd;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define mem(a,b) memset(a, b, sizeof(a) )
#define all(x) (x).begin(),(x).end()
#define INF 1e18
#define MOD 1000000007
#define PB push_back
#define MP make_pair
#define F first
#define S second

inline void normal(ll &a) { a %= MOD; (a < 0) && (a += MOD); }
inline ll modMul(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a*b)%MOD; }
inline ll modAdd(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a+b)%MOD; }
inline ll modSub(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); a -= b; normal(a); return a; }
inline ll modPow(ll b, ll p) { ll r = 1; while(p) { if(p&1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
inline ll modInverse(ll a) { return modPow(a, MOD-2); }
inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }

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

using edge = pair<ll, pll>;
int n,m;
ll s;
vector<vector<pair<ll,pll>>>g;
vl c,d;

void solve(){
    if(s>2500)s=2500;
    vvl dp(n,vl(2501,INF));
    priority_queue<pair<ll,pll>,vector<pair<ll,pll>>,greater<pair<ll,pll>>>q;
    dp[0][s]=0;
    q.push(MP(0,MP(0,s)));
    while(!q.empty()){
        pair<ll,pll>p=q.top();
        q.pop();
        ll t=p.F,v=p.S.F,s2=p.S.S;
        if(t>dp[v][s2])continue;
        if(s2+c[v]<=2500){
            ll ns=s2+c[v],nt=t+d[v];
            if(dp[v][ns]>nt){
                dp[v][ns]=nt;
                q.push(MP(nt,MP(v,ns)));
            }
        }
        for(auto x:g[v]){
            if(s2<x.S.F)continue;
            ll nv=x.F,ns=s2-x.S.F,nt=t+x.S.S;
            if(dp[nv][ns]>nt){
                dp[nv][ns]=nt;
                q.push(MP(nt,MP(nv,ns)));
            }
        }
    }
    for(int i=1;i<n;++i){
        ll ans=INF;
        rep(j,2501){
            if(ans>dp[i][j]){
                ans=dp[i][j];
            }
        }
        cout<<ans<<endl;
    }
}

int main(){
    cin>>n>>m>>s;
    g.resize(n+1);
    rep(i,m){
        ll u,v,a,b;
        cin>>u>>v>>a>>b;
        u--;v--;
        g[u].PB(MP(v,MP(a,b)));
        g[v].PB(MP(u,MP(a,b)));
    }
    c.resize(n);
    d.resize(n);
    rep(i,n)cin>>c[i]>>d[i];
    solve();
}


Measured memory_bytes: 7320
#include <stdio.h>
#include <stdlib.h>

int main()
{ int a,b,c;
    while(~scanf("%d %d %d",&a,&b,&c))
    {
        if(c>=a&&c<=b)
            printf("Yes\n");
            else
            printf("No\n");
    }
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using ll = long long;
#define int long long
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; }
const long long INF = 1LL << 60;
signed main(void){
    int n; cin>>n;
    vector <int> a(3*n); 
    rep(i,3*n) cin>>a[i];
    vector <int> d(3*n+10); 
    vector <int> rd(3*n+10); 
    priority_queue <int, vector <int>, greater<int>> q;
    d[0] = 0;
    rep(i, 3*n){
        if(i<n){
            d[i+1] = d[i] + a[i];
            q.push(a[i]);
        }else{
            int tmp = q.top();
            q.pop();
            if(tmp < a[i]){
                d[i+1] = d[i] + a[i] - tmp;
                q.push(a[i]);
            }else{
                d[i+1] = d[i];
                q.push(tmp);
            }
        }
        //cout<<d[i+1]<<endl;
    }
    rd[3*n-1] = 0;
    priority_queue <int> lq;
    for(int i=3*n-1; i>0;i--){
        if(i>= 3*n-n){
            rd[i-1] = rd[i] + a[i];
            lq.push(a[i]);
        }else{
            int tmp = lq.top();
            lq.pop();
            if(tmp > a[i]){
                rd[i-1] = rd[i] + a[i] - tmp;
                lq.push(a[i]);
            }else{
                rd[i-1] = rd[i];
                lq.push(tmp);
            }
        }
        //cout<<lq.size()<<endl;
        //cout<<rd[i-1]<<endl;
    }
    int ans = -INF;
    for(int i = n;i<=2*n; i++){
        //cout<<d[i]<<' '<<rd[i]<<endl;
        ans = max(ans, d[i] - rd[i-1]);
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 9588
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
  int n,m;
  int a,b,c,d;
  int x;
  int p,q,r;
  int cost[111][111];
  int time[111][111];
  while(1){
    cin >> n >> m;
    if(n==0 && m==0)break;
    for(int i=0;i<111;i++){
      for(int j=0;j<111;j++){
	cost[i][j]=9999999;
	time[i][j]=9999999;
      }
    }
    for(int i=0;i<n;i++){
      cin >> a >> b >> c >> d;
      cost[a-1][b-1]=cost[b-1][a-1]=c;
      time[a-1][b-1]=time[b-1][a-1]=d;
    }
    for(int k=0;k<m;k++){
      for(int i=0;i<m;i++){
	for(int j=0;j<m;j++){
	  cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j]);
	  time[i][j]=min(time[i][j],time[i][k]+time[k][j]);
	}
      }
    }
    cin >> x;
    for(int i=0;i<x;i++){
      cin >> p >> q >> r;
      cout << (r==0 ? cost[p-1][q-1] : time[p-1][q-1]) << endl;
    }
  }
}

Measured memory_bytes: 1252
# ABC044C - 高橋君とカード / Tak and Cards (ARC060C)
from collections import defaultdict


def main():
    N, A, *X = map(int, open(0).read().split())
    X, D = [i - A for i in X], defaultdict(int)
    D[0] = 1
    for i in X:
        for j, k in list(D.items()):
            D[i + j] += k
    ans = D[0] - 1
    print(ans)
    


if __name__ == "__main__":
    main()

Measured memory_bytes: 3572
#include <iostream>

using namespace std;

void showArray(int A[], int N){
	for (int p = 0; p < N - 1; p++){
		cout << A[p] << " ";
	}
	cout << A[N - 1] << endl;
}

void bubbleSort(int A[], int N){
	int counter = 0;

	for (int i = 0; i < N; i++){
		for (int j = N - 1; j > 0; j--){
			if (A[j] < A[j - 1]){
				int temp = A[j - 1];
				A[j - 1] = A[j];
				A[j] = temp;
				counter++;
			}
		}
	}
	showArray(A, N);
	cout << counter << endl;
}

int main(){
	int N;
	int A[100];

	cin >> N;

	for (int i = 0; i < N; i++){
		cin >> A[i];
	}

	bubbleSort(A, N);

	return 0;
}

Measured memory_bytes: 1164
using System;
using System.Linq;
using System.Collections.Generic;

namespace program{
  class Program{
    static void Main(){
      int[] input = Input.ScanIntArray();
      int N = input[0];
      int W = input[1];
      long[] MaxValue = new long[W+1];
      for(int i = 0; i < N; i++)
      {
        input = Input.ScanIntArray();
        for(int k = W; k>=input[0]; k--)
          MaxValue[k] = Math.Max(MaxValue[k], MaxValue[k-input[0]]+input[1]);
      }
      Console.WriteLine($"{MaxValue[W]}");
    }
  }

    static class Input
    {
        static public int ScanInt() { return int.Parse(Console.ReadLine()); }
        static public uint ScanUint() { return uint.Parse(Console.ReadLine()); }
        static public long ScanLong() { return long.Parse(Console.ReadLine()); }
        static public ulong ScanUlong() { return ulong.Parse(Console.ReadLine()); }
        static public int[] ScanIntArray() { return Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray(); }
        static public uint[] ScanUintArray() { return Console.ReadLine().Split(' ').Select(x => uint.Parse(x)).ToArray(); }
        static public long[] ScanLongArray() { return Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToArray(); }
        static public ulong[] ScanUlongArray() { return Console.ReadLine().Split(' ').Select(x => ulong.Parse(x)).ToArray(); }

        static public string ScanStr() { return Console.ReadLine(); }
        static public string[] ScanStrArray() { return ScanStr().Split(' '); }
    }
}


Measured memory_bytes: 13920
#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

int main () {
  int N;
  cin >> N;
  map<long long, long long> A;
  long long sub;
  for (int i = 0; i < N; i++) {
    cin >> sub;
    A[sub]++;    
  }  
  long long max = -1;
  long long sax = -1;
  vector<pair<long long, long long> > ans;
  for (auto x = A.begin(); x != A.end(); ++x) {
    if (x->second >= 2)
      ans.push_back(make_pair(x->first, x->second));
  }
  sort(ans.begin(), ans.end());
  if (ans.size() == 0) {
    cout << 0 << endl;
    return 0;  
  }
  if (ans.size() == 1 && ans[0].second < 4) {
    cout << 0 << endl;
    return 0;    
  }
  if (ans[ans.size() - 1].second >= 4) {
    cout << ans[ans.size() - 1].first * ans[ans.size() - 1].first << endl;  
  }
  else {
    cout << ans[ans.size() - 1].first * ans[ans.size() - 2].first << endl;  
  }
}

Measured memory_bytes: 6528
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
#define REPI(i, a, n)	for(ll (i)=(a);(i)<(int)(n);(i++))
#define REP(i,n) REPI(i,0,n)
#define REP1(i,n) for(ll (i)=1;(i)<=(n);(i++))
#define ALL(x) x.begin(), x.end()
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
 
struct ProconInit {
	static constexpr int IOS_PREC = 15;
	static constexpr bool AUTOFLUSH = false;
 
	ProconInit() {
		cin.tie(nullptr);
		ios::sync_with_stdio(false);
		cout << fixed << setprecision(IOS_PREC);
		if (AUTOFLUSH)
			cout << unitbuf;
	}
} PROCON_INIT;
 
template<typename T>
int contains(std::vector<T> vec, int number) {
	auto itr = std::find(vec.begin(), vec.end(), number);
	size_t index = std::distance(vec.begin(), itr);
	if (index != vec.size()) { // 発見できたとき
		return 1;
	}
	else { // 発見できなかったとき
		return 0;
	}
}
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (a % b == 0)return b;
	return gcd(a % b, b);
}
ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}
ll fact(ll n) {
	ll m;
	if (n == 0) {
		return 1;
	}
	m = fact(n - 1);
	return n * m;
}
 
ll Combination(unsigned long long n, unsigned long long r) {
	if (r * 2 > n) r = n - r;
	uintmax_t dividend = 1;
	uintmax_t divisor = 1;
	for (unsigned int i = 1; i <= r; ++i) {
		dividend *= (n - i + 1);
		divisor *= i;
	}
	return dividend / divisor;
}
 
struct vec {
	ll x, y;
 
	bool operator == (const vec &v) const{
		return x == v.x && y == v.y;
	}
 
};
 
namespace std {
	template<>
	class hash<vec> {
	public:
		size_t operator () (const vec& p) const { return p.x%SIZE_MAX; }
	};
}

int main() {
	int S, W;
	cin >> S >> W;
	cout << (S <= W ? ("unsafe") : ("safe")) << endl;

	return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using Int = long long;  // clang-format off
#define REP_(i, a_, b_, a, b, ...) for (Int i = (a), lim##i = (b); i < lim##i; i++)
#define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
struct SetupIO { SetupIO() { std::cin.tie(nullptr), std::ios::sync_with_stdio(false), std::cout << std::fixed << std::setprecision(13); } } setup_io;
#ifndef dump
#define dump(...)
#endif  // clang-format on

/**
 *    author:  knshnb
 *    created: Sat Jul 11 21:04:49 JST 2020
 **/

signed main() {
    Int n;
    std::cin >> n;
    std::vector<Int> cnt(n + 1);
    REP(x, 1, n) {
        Int acc1 = x * x;
        if (acc1 > n) break;
        REP(y, 1, n) {
            Int acc2 = acc1 + y * y + x * y;
            if (acc2 > n) break;
            REP(z, 1, n) {
                Int acc3 = acc2 + z * z + z * x + z * y;
                if (acc3 > n) break;
                cnt[acc3]++;
            }
        }
    }
    REP(i, 1, n + 1) std::cout << cnt[i] << "\n";
}


Measured memory_bytes: 3660
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC_Training
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            var h = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            if (n == 1)
            {
                Console.WriteLine("0");
                return;
            }
            List<bool> vs = new List<bool>();
            for (int i = 0; i < n - 1; i++)
            {
                if (h[i] >= h[i + 1])
                {
                    vs.Add(true);
                }
                else
                {
                    vs.Add(false);
                }
            }
            vs.Add(false);
            int mx = 0;
            int count = 0;
            foreach (var tmp in vs)
            {
                if (tmp)
                {
                    count++;
                }
                else
                {
                    mx = Math.Max(mx, count);
                    count = 0;
                }
            }
            Console.WriteLine(mx);
        }

    }
}


Measured memory_bytes: 30556
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	double t,a;
	cin>>n>>t>>a;
	double h[n+1];
	double minv=10000;
	int d;
	for(int i=1;i<=n;i++)
	{
		cin>>h[i];
		h[i]=t-h[i]*0.006;
		double cha=abs(h[i]-a);
		if(cha<minv)
		{
		   minv=cha;
		   d=i;
		}   
	}
	cout<<d<<endl;
	return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair <ll, ll > pll;

bool comp(const pll &a, const pll &b) {
	return a.first < b.first;
}
std::vector<int> enum_div(int n)//nの約数を列挙
{
	std::vector<int> ret;
	for (int i = 1; i*i <= n; ++i)
	{
		if (n%i == 0)
		{
			ret.push_back(i);
			if (i != 1 && i*i != n)
			{
				ret.push_back(n / i);
			}
		}
	}
	return ret;
}


template<int N>
int factorial() {
	return factorial<N - 1>() * N;
}

template<>  /// 特殊化：factorial<N=”1”>だったら，値を返す
int factorial<1>() {
	return 1;
}
int main()
{
	//priority_queue<int> q;
	string s = {};
	string s1 = {};
	ll h = 0, w = 0, k = 0, a = 0, b = 0, c = 0, d = 0, e = 0, f = 0, g = 0, ans = 0;
	//ll x[300005] = {};
	ll y[300005] = {};
	ll z[302][302] = {};
	cin >> s;
	for (int i = 0; i < s.length(); i++)
	{
		cout << "x";
	}
	cout << endl;
	//cout << ans << endl;



	//return 0;

	/*cout << c << endl;
	cout << b << endl;*/
	//cout << fixed << setprecision(10) <<tmp << endl;
	//cout<<factorial<10><<endl;
	return 0;
}
//2つの組の数をソートしたりするやつ
//vector<pair<ll, ll> > hoges(a);
//for (int i = 1; i <= a; i++)
//{
//	cin >> h;
//	hoges[i - 1] = make_pair(h, i);
//}
//sort(hoges.begin(), hoges.end(), comp);
//for (int i = 0; i < a; i++)
//{
//	cout << hoges[i].second << endl;
//}


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

int main () {
	int A,B,C;
	cin>>A>>B>>C;
	
	if(A==B){
		cout<<C<<endl;
	}
	else if(A==C){
		cout<<B<<endl;
	}
	else if(B==C){
		cout<<A<<endl;
	}
}

Measured memory_bytes: 256
#include <stdio.h>

int main() {
  long x;
  scanf("%ld",&x);

  for(int a = 0; a <= 200; a++) {
    for(int b =- 200; b <= 200; b++) {
      if(a * a * a * a * a - b * b * b * b * b == x) {
          printf("%d %d",a, b);
          return 0;
        }
    }
  }
}


Measured memory_bytes: 1696
n , k = map(int, input().split())
nusukes = list(range(1, n+1))
for _ in range(k) :
    d = int(input())
    lst = list(map(int, input().split()))
    for i in lst :
        if i in nusukes :
            nusukes.remove(i)
print(len(nusukes))

Measured memory_bytes: 9180