akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>

int main(void)
{
	int m,f,r,i;
	char s[100];
	
	i = 0;
	do{
		scanf("%d %d %d",&m,&f,&r);
		if(m != -1 && f != -1)
		{
			if( (m+f) < 80)
			{
				if( (m+f) < 65 )
				{
					if( (m+f) < 50 )
					{
						if( (m+f) < 30)
						{
							s[i++] = 'F';
						}
						else if( r < 50)
							s[i++] = 'D';
						else
							s[i++] = 'C';
					}
					else
						s[i++] = 'C';
				}
				else
					s[i++] = 'B';
			}
			else
				s[i++] = 'A'; 
		}
		else if(m != -1 || f != -1)
			s[i++] = 'F';
		
	}while(m != -1 || f != -1 || r != -1);

	s[i]='\0';
	
	i=0;
	while(s[i]!='\0')
		printf("%c\n",s[i++]);
	
	
	return 0;
}

Measured memory_bytes: 600
#include<bits/stdc++.h>
using namespace std;
int main(){
  cin.tie(NULL);
  ios::sync_with_stdio(false);
  int x,y;
  cin>>x>>y;
  if(x==1 || x==3 || x==5 || x==7 || x==8 || x==10 || x==12){
      if(y==1 || y==3 || y==5 || y==7 || y==8 || y==10 || y==12){
	cout<<"Yes"<<'\n';
	return 0;
      }
  }
  if(x==4 || x==6 || x==9 || x==11){
    if(y==4 || y==6 || y==9 || y==11){
      cout<<"Yes"<<'\n';
      return 0;
    }
  }
  if(x==2 && y==2){
    cout<<"Yes"<<'\n';
    return 0;
  }
  cout<<"No"<<'\n';
  return 0;
}


Measured memory_bytes: 256
using System;

	class Program
    {
        static void Main(string[] args)
        {
			string input = Console.ReadLine();
			int n = int.Parse(input);
			bool isSingleProduct = false;
			for (int i = 1; i < 10; i++)
			{
				if (isSingleProduct = n % i == 0 && n / i < 10) break;
			}
			Console.WriteLine(isSingleProduct ? "Yes" : "No");
        }
    }


Measured memory_bytes: 13140
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for (ll i=0; i<n; ++i)
#define all(c) begin(c),end(c)
template<typename T1, typename T2>
bool chmax(T1 &a,T2 b){if(a<b){a=b;return true;}else return false;}
template<typename T1, typename T2>
bool chmin(T1 &a,T2 b){if(a>b){a=b;return true;}else return false;}
/*

*/
int main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  
  ll N,A,B,C; cin>>N>>A>>B>>C;
  vector<char> ans(0, 0);
  vector<string> IN(N, "");
  rep(i, N) cin>>IN[i];
  rep(i, N){
    string S = IN[i];
    if (S == "AB"){
      if (A == 0 && B == 0){
        cout<<"No"<<endl;
        return 0;
      }
      else if (A > B){
        ans.push_back('B');
        B++;
        A--;
      }
      else if (A == B && i < N-1){
        if (IN[i+1] == "AC" || IN[i+1] == "AB"){
          ans.push_back('A');
          A++;
          B--;
        }
        if (IN[i+1] == "BC"){
          ans.push_back('B');
          B++;
          A--;
        }
      }
      else{
        ans.push_back('A');
        A++;
        B--;
      }
    }

    if (S == "BC"){
      if (B == 0 && C == 0){
        cout<<"No"<<endl;
        return 0;
      }
      else if (B > C){
        ans.push_back('C');
        C++;
        B--;
      }
      else if (B == C && i < N-1){
        if (IN[i+1] == "AC" || IN[i+1] == "BC"){
          ans.push_back('C');
          C++;
          B--;
        }
        if (IN[i+1] == "AB"){
          ans.push_back('B');
          B++;
          C--;
        }
      }
      else{
        ans.push_back('B');
        B++;
        C--;
      }
    }

    if (S == "AC"){
      if (C == 0 && A == 0){
        cout<<"No"<<endl;
        return 0;
      }
      else if (C > A){
        ans.push_back('A');
        A++;
        C--;
      }
      else if (A == C && i < N-1){
        if (IN[i+1] == "AB" || IN[i+1] == "AC"){
          ans.push_back('A');
          A++;
          C--;
        }
        if (IN[i+1] == "BC"){
          ans.push_back('C');
          C++;
          A--;
        }
      }
      else{
        ans.push_back('C');
        C++;
        A--;
      }
    }
    
  }
  cout<<"Yes"<<endl;
  rep(i, N) cout<< ans[i] << endl;
}


Measured memory_bytes: 6604
#include <bits/stdc++.h>
#include <unordered_map>
#define mem(ara, a) memset(ara, a, sizeof(ara))
#define fo freopen("output.txt", "w", stdout)
#define fi freopen("bruh.txt", "r", stdin)
#define int long long
#define sp " "
#define pb push_back
#define ff first
#define sz(x) x.size();
#define len(x) x.length();
#define ss second
#define vi vector<int>
#define double long double
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define pii pair<int, int>


long long inf = 2e18;
long long minf = -inf;
int ans = 0;
using namespace std;

signed main() {
int a,b;
cin>>a>>b;
if (a<10){
    cout << b+(100*(10-a)) << endl;
}
else cout << b << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
int a[maxn],b[maxn];
int main()
{

	int n,x;
	scanf("%d%d",&n,&x);
	int k = 0;
	a[k++] = x;
	for(int i = 0;i < n;i ++)
	{
		scanf("%d",&x);
		a[k++] = x;
	}
	sort(a,a+k);
	int z = 0;
	for(int i = 0;i < k-1;i ++)
	{
		int temp = a[i+1] - a[i];
		b[z++] = temp;
	}
	int q = b[0];
	for(int i = 1;i < z;i ++)
	{
		q = __gcd(q,b[i]);
		if(q == 1)
			break;
	}
	printf("%d",q);
	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define reps(i,s,n) for(int (i)=(s);(i)<(n);++(i))
#define rep(i,n) reps(i,0,n)
#define reptr(i,n) for(int (i)=(n);(i)>=0;--(i))
#define All(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
const ll MOD=1e9+7;
using namespace std;

int main(){
  ll N;
  string s;
  cin >> N >> s;
  ll b=0,w=0;
  vector<ll> sa(N+1), rsa(N+1);
  sa[0] = 0;
  for(ll i=0;i<N;i++){
    if(s[i]=='#') b++;
    else w++;
    sa[i+1] = w-b;
  }

  b=0,w=0;
  for(ll i=0;i<N;i++){
    if(s[N-1-i]=='#') b++;
    else w++;
    rsa[i+1] = b-w;
  }

  vector<pair<ll,ll> > ans(N+1);
  for(ll i=0;i<=N;i++){
    ans[i] = make_pair(sa[i]+rsa[N-i], i);
    //cout << sa[i] << " " << rsa[N-i] << endl;
  }
  sort(All(ans));
  //cout << ans[N].second << endl;
  ll cnt = 0;
  for(ll i=0;i<ans[N].second;i++){
    if(s[i]!='.') cnt++;
  }
  for(ll i=ans[N].second;i<N;i++){
    if(s[i]!='#') cnt++;
  }
  cout << cnt << endl;
}


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

using namespace std;

typedef pair<int, int> PII;
typedef long long ll;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pct __builtin_popcount

#define N 100010
#define INF 1000000007

int R, C;
int n;
vector<PII> A[N];
ll cm[N];

int f[N]; ll g[N];

int fa(int x) {
	if (f[x] == x) return x;
	int y = fa(f[x]);
	g[x] += g[f[x]];
	f[x] = y;
	return y;
}

int main () {
	cin >> R >> C >> n;
	for (int i = 0; i < C; i ++) cm[i] = INF;
	for (int i = 0; i < n; i ++) {
		int x, y, z;
		cin >> x >> y >> z;
		x--, y--;
		A[x].pb(mp(y, z));
		cm[y] = min(cm[y], (ll)z);
	}
	for (int i = 0; i < C; i++) f[i] = i;
	for (int i = 0; i < R; i ++) {
		for (int j = 0; j < (int) A[i].size()-1; j ++) {
			int u = A[i][j].fi;
			int v = A[i][j+1].fi;
			int x = fa(u);
			int y = fa(v);
			int dif = A[i][j+1].se - A[i][j].se;
			if (x == y) {
				if (g[v] - g[u] != dif) {
					puts ("No"); return 0;
				}
			} else {
				f[y] = x;
				g[y] = dif - g[v] + g[u];
			}
		}
	}
	for (int i = 0; i < C; i ++) {
		int y = fa(i);
		cm[y] = min(cm[y], cm[i] - g[i]);
	}
	for (int i = 0; i < C; i ++) {
		int y = fa(i);
		cm[i] = min(cm[i], cm[y] + g[i]);
		if (cm[i] < 0) {
			puts ("No"); return 0;
		}
	}
	puts ("Yes");
	return 0;
}

Measured memory_bytes: 6912
N = int(input())
K = list(map(int,input().split()))
A = [0]*N
for i in range(N):
    A[K[i]-1] += 1
r = 0
for k in range(N):
    r += 0.5*(A[k]*(A[k]-1))
An =[]
for j in range(N):
    D = A[K[j]-1]-1
    An.append(int(r-(0.5*(D+1)*(D))+(0.5*D*(D-1))))
for i in range(len(An)):
    print(An[i])

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

#define int long long int

signed main()
{
    int n,i,k,g,j;
    cin>>n;
    int a[n+1];
    for(i=1;i<=n;i++) cin>>a[i];
    int sum[n+1]={0};
    for(i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];
    int dp[n+1][n+1];
    for(i=1;i<=n;i++) for(j=1;j<=n;j++) dp[i][j]=1e17;
    for(i=1;i<=n;i++) dp[i][i]=0;
    for(g=2;g<=n;g++)
    {
        for(i=1,j=i+g-1;j<=n;i++,j++)
        {
            for(k=i;k<j;k++)
            {
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
            }
        }
    }
    cout<<dp[1][n];
}


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

#define REP(i, n) for(int (i) = 0; (i) < (int)(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 ALL(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define INF 1e9

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; }

typedef long long ll;

using namespace std;

int main(int argc, char const *argv[])
{
    int X ,Y;
    cin >> X >> Y;

    cout << X + Y /2 << endl;

    return 0;
}


Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<set>
#include<map>
#include<string>
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define rep2(i,s,n) for(int i=s;i< (int)n; i++)
#define ll long long 
#define all(v) v.begin(),v.end()
using namespace std;
int main(){
  ll n,k; cin>>n>>k;
  vector<ll> a(n);
  rep(i,n) cin >>a[i];
  map<ll,ll> mp;
  mp[0]++;
  ll key=0;
  ll time=0;
  ll loop=0;
  vector<ll> vec;
  vector<ll> vec0;
  vec0.push_back(0);
  rep(i,2*n+10){
    mp[a[key]-1]++;
    if(mp[a[key]-1]==1){
    time++;
    vec0.push_back(a[key]);
    }
    if(mp[a[key]-1]==2) {
    loop++;
    vec.push_back(a[key]);
    }
    key=a[key]-1;
  }
  if(k>time&&(k-time)%loop!=0)cout <<vec[(k-time)%loop-1]<<endl;
  else if(k>time&&(k-time)%loop==0)cout <<vec[loop-1]<<endl;
  else cout <<vec0[k]<<endl;
}


Measured memory_bytes: 20656
N,K = map(int, input().split())
if N == 0:
    print(0)
else:
    for i in range(18):
        while True:
            if N > K*10**(18-i):
                N = N-(K*10**(18-i))
            else:
                break

    x0 = N #7
    x1 = abs(x0-K) #3
    while True:
        if x0 < x1:
            print(x0)
            break
        else:
            x0,x1 = x1,abs(x0-K)
            continue

Measured memory_bytes: 38256
from math import gcd as g
#####segfunc#####
def segfunc(x, y):
    return g(x,y)
#################

#####ide_ele#####
ide_ele =0
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

n=int(input())
a=list(map(int,input().split()))
seg=SegTree(a,segfunc,ide_ele)
ans=1
for i in range(n):
    p=seg.query(0,i)
    q=seg.query(i+1,n)
    ans=max(ans,g(p,q))
print(ans)








Measured memory_bytes: 20564
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11Z
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<int, pii>
#define puu pair<ULL, ULL>
#define MOD(a, b) (a >= b ? a%b+b : a%b)
#define pdd pair<long double, long double>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head

const int N = 1e5 + 5;
const int MOD = 1e9 + 7;
int n, k, l[N], r[N], cnt = 0;
int dp[105][N];
int main() {
    scanf("%d %d", &n, &k);
    for (int x = 1, y; x <= n; x = y+1) {
        y = n/(n/x);
        l[++cnt] = x;
        r[cnt] = y;
    }
    for (int i = 1; i <= cnt; ++i) dp[1][i] = (dp[1][i-1] + r[i]-l[i]+1)%MOD;
    for (int i = 2; i <= k; ++i) {
        for (int j = 1; j <= cnt; ++j) {
            dp[i][j] = (dp[i][j-1] + (dp[i-1][cnt-j+1])*1LL*(r[j]-l[j]+1)%MOD)%MOD;
        }
    }
    printf("%d\n", dp[k][cnt]);
    return 0;
}


Measured memory_bytes: 40704
def dfs(adjlist,v):
    global d,f,t
    d[v-1]=t
    t+=1
    for node in adjlist[v-1]:
        if d[node-1]<0 and node>0:
            dfs(adjlist,node)
    f[v-1]=t
    t+=1

n=int(input())
adjlist=[list(map(int,input().split()))[2:] for _ in range(n)]
d=[-1]*n
f=[-1]*n
t=1
for i in range(1,n):
    if d[i-1]<0:
       dfs(adjlist,i)
for i in range(n):
    print("{} {} {}".format(i+1,d[i],f[i]))


Measured memory_bytes: 5624
using System;
using System.Linq;
using System.Text;

namespace _163_b
{
    internal class Homework
    {
        private static void Main(string[] args)
        {
            var nm = Console.ReadLine()?.Split(' ').Select(int.Parse).ToArray();
            if (nm == null) return;
            var n = nm[0];
            var m = nm[1];

            var sb = new StringBuilder();
            while (true)
            {
                var ch = Convert.ToChar(Console.Read());
                sb.Append(ch);
                if (ch == '\n') break;
            }

            var a = sb.ToString().Split(" ").Select(int.Parse).ToArray();

            n -= a.Sum();
            Console.WriteLine(n < 0 ? -1 : n);

        }
    }
}


Measured memory_bytes: 29128
#include<stdio.h>
#include<string.h>
int main(void)
{
	int a,s[1002],d[1002],f[1002],g[1002],h[1001],i,j;
	scanf("%d",&a);
	while(a!=0){
		j=0;
		for(i=0;i<=a;i++){
			scanf("%d %d %d %d",&s[i],&d[i],&f[i],&g[i]);
			h[i]=d[i]*4+f[i]*9+g[i]*4;
		}
		for(i=0;i<a;i++){
		//	printf("%d %d %d %d\n",d[i],f[i],g[i],h[i]);
			if(d[i]<=s[a]&&f[i]<=d[a]&&g[i]<=f[a]&&h[i]<=g[a]){
				printf("%d\n",s[i]);
				j=1;
			}
		}
		if(j==0){
			printf("NA\n");
		}
		scanf("%d",&a);
	}
	return 0;
}

Measured memory_bytes: 1060
#include<bits/stdc++.h>
#include<string>
#include<cmath>

using namespace std;

#define ll long long int
#define ld long double
#define loop(i, n) for (int i = 0; i < n; i++)
#define loops(i, s, n) for (int i = s; i < n; i++)
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
#define deb(x) cout<< #x << '=' << x <<endl
#define MOD 1000000007

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ld d , s, t;
    cin>>d>>s>>t;
    if(d / s <= t){
        cout<<"Yes\n";
    }else{
        cout<<"No\n";
    }
}

Measured memory_bytes: 3752
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
s = 0
for i in set(a):
    s += c[i] * (c[i] - 1)
dp = [-1] * (n + 1)
for i in a:
    if dp[i] == -1:
        dp[i] = (s - c[i] * (c[i] - 1) + (c[i] - 1) * (c[i] - 2)) // 2
        print(dp[i])
    else:
        print(dp[i])


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


using namespace std;

#define endl '\n'
#define PB push_back
#define MP make_pair
#define LL long long
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define RE(i,n) FOR(i,1,n)
#define REP(i,n) FOR(i,0,(int)(n)-1)
#define R(i,n) REP(i,n)
#define VI vector<int>
#define PII pair<int,int>
#define LD long double
#define FI first
#define SE second
#define st FI
#define nd SE
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())

typedef long long ll;

bool file=0,rt=1;
clock_t tStart ;
void FAST_IO();
////////////////////////

int main() {

    //FAST_IO();
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout << setprecision(5);
    cout << fixed;

    string s;
    cin >> s;
    int ans1 = 0;
    int ans2 = 0;
    char ch;

    int n = s.size();

    if(n < 2) {

        cout << 0 << endl;
        return 0;
    }

    ch = s[0];


    for(int i = 0; i < n; i++) {

        if(i % 2 == 0) {

            if(s[i] != ch) ans1++;
        }
        else {

            if(s[i] == ch) ans1++;
        }
    }

    if(s[0] == '1') ch = '0';
    else ch = '1';



    for(int i = 0; i < n; i++) {

        if(i % 2 == 0) {

            if(s[i] != ch) ans2++;
        }
        else {

            if(s[i] == ch) ans2++;
        }
    }

    cout << min(ans1, ans2) << endl;






    return 0;
}

void FAST_IO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    //cout.tie(NULL);
    //cout.setf(ios::fixed);
    //cout.precision(2);
    if(rt && file){ tStart = clock(); }
    if(file){
    #ifndef _offline
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    }
}





Measured memory_bytes: 512
import java.util.Scanner;
import java.util.ArrayList;

class Main {

	public static void main(String[] args) {
	
		ArrayList<Integer> x = new ArrayList<Integer>();
		int y = 1;
		int i;
		Scanner sc = new Scanner(System.in);
		
		while(true){
			int temp = sc.nextInt();
			if(temp == 0)
				break;
			x.add(temp);
		}
			
		for(i = 0; i < x.size(); i++){	
			
			int val = x.get(i);
			
			System.out.println("Case " + y + ": " + val);
			y++;
		}
		

	}

}

Measured memory_bytes: 44748
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cassert>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repd(i, n) for (int i = n; i >= 1; i--)
#define mod 1000000007
#define MOD 998244353
#define inf 1e20
typedef long long int ll;
typedef pair<ll, ll> p;


int main() {
	int a, b;
	cin >> a >> b;
	if (a + b >= 10) {
		cout << "error";
	}
	else {
		cout << a + b;
	}
	return 0;
}

//Ctrl+Aを使わない

Measured memory_bytes: 256
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

# 個数制限なしナップサック問題
W,N = map(int,readline().split())

dp = [INF]*(W+1)
dp[0] = 0

for i in range(N):
    w,v = map(int,readline().split())
    # dp[j] = 重さj以下でつくれる最大の価値
    for j in range(W+1):
        dp[j] = min(dp[j],dp[max(j-w,0)] + v)

print(dp[W])


Measured memory_bytes: 73944
import std.algorithm, std.conv, std.range, std.stdio, std.string;
import std.container, std.typecons;

void main()
{
  auto rd1 = readln.split, n = rd1[0].to!size_t, q = rd1[1].to!int;
  auto qu = DList!process();
  foreach (_; 0..n) {
    auto rd2 = readln.split;
    qu.insertBack(process(rd2[0], rd2[1].to!int));
  }

  auto t = 0;
  while (!qu.empty) {
    auto p = qu.front; qu.removeFront;
    if (p.time > q) {
      t += q;
      qu.insertBack(process(p.name, p.time - q));
    } else {
      t += p.time;
      writefln("%s %d", p.name, t);
    }
  }
}

alias Tuple!(string, "name", int, "time") process;

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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
template<typename T> using v = vector<T>;
template<typename T> using pq = priority_queue<T>;
template<typename T> using minpq = priority_queue<T, vector<T>, greater<T>>;
template<typename T, typename K> using ump = unordered_map<T, K>;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll e5 = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = n - 1; i >= 0; i--)
#define repone(i, n) for(ll i = 1; i <= (ll)(n); i++)
#define each(i, mp) for(auto& i:mp)
#define eb emplace_back
#define F first
#define S second
#define all(obj) (obj).begin(), (obj).end()

template<class T>
void dump_debug(T list) {
#ifdef MY_DEBUG
    each(e, list) cout << e << " ";
    printf("\n");
#endif
}

inline ll inl() {
    ll x;
    cin >> x;
    return x;
}

inline string ins() {
    string x;
    cin >> x;
    return x;
}

/* ------------- ANSWER ------------- */
/* ---------------------------------- */

int main() {
#ifdef MY_DEBUG
    while (true) {
#endif
        ll n = inl();
        vl a(n);

        rep(i, n) cin >> a[i];
        multiset<ll> s; // 最小のもの

        for (ll i = 0; i < n; ++i) {
            ll now = a[i];
            auto itr = s.lower_bound(now);
            if (itr != s.begin()) s.erase(--itr);
            s.insert(now);
        }
        cout << s.size() << endl;

#ifdef MY_DEBUG
    }
#endif
    return 0;
}

Measured memory_bytes: 5760
import heapq as hq

def get_num():
    return list(map(int,input().split(' ')))

def main():
    n,m = get_num()
    card = get_num()
    card_sum=sum(card)
    hq.heapify(card)
    d_set=[]
    d=[]
    for i in range(m):
        b,c=get_num()
        hq.heappush(d_set,(-c,b))
    for i in range(m):
        if len(d) ==n:
            break
        cnt = hq.heappop(d_set)
        for i in range(cnt[1]):
            d.append(-cnt[0])
            if len(d)==n:
                break
    for i in range(len(d)):
        c_min=hq.heappop(card)
        d_max=d[i]
        if c_min>=d_max:
            break
        else:
            card_sum += (d_max-c_min)
    print(card_sum)
main()

Measured memory_bytes: 25032
n, p = [int(i) for i in input().split()]
s = input()

if p == 2 or p == 5:
    ans = 0
    for i, j in enumerate(s):
        if int(j) % p == 0:
            ans += i + 1
    print(ans)
    exit()


a = [0]
j = n-1
for i in s:
    a.append((a[-1] + int(i) * pow(10, j, p))%p)
    j -= 1

b = {}
for i in a:
    if i in b:
        b[i] += 1
    else:
        b[i] = 1
ans = 0
for i in b:
    ans += b[i] * (b[i] - 1) // 2
print(ans)

Measured memory_bytes: 48588
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner scn = new Scanner(System.in);
    int N = scn.nextInt();
    int M = scn.nextInt();

    ArrayList<CityInfo> city = new ArrayList<>();
    for (int i = 0; i < M; i++) {
      int P = scn.nextInt();
      int Y = scn.nextInt();

      city.add(new CityInfo(P, Y, i));
    }

    Collections.sort(city, new Comparator<CityInfo>() {
      public int compare(CityInfo c1, CityInfo c2) {
        return (c1.year > c2.year) ? 1 : -1;
      }
    });

    HashMap<Integer, Integer> serialNo = new HashMap<>();
    String[] IDlist = new String[M];
    for (CityInfo info : city) {
      if (!serialNo.containsKey(info.prefNo)) {
        serialNo.put(info.prefNo, 1);
      } else {
        serialNo.put(info.prefNo, serialNo.get(info.prefNo) + 1);
      }
      IDlist[info.order] = String.format("%06d%06d", info.prefNo, serialNo.get(info.prefNo));

    }

    for (String id : IDlist) {
      System.out.println(id);
    }

  }

  private static class CityInfo {
    private int prefNo;
    private int year;
    private int order;

    CityInfo(int P, int Y, int i) {
      this.prefNo = P;
      this.year = Y;
      this.order = i;
    }
  }

}


Measured memory_bytes: 167000
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <map>
#include <set>

using namespace std;

const int MAXN = 300005;

struct Edge
{
	int to;
	int w;
	int nxt;
}edge[MAXN << 2];

int n,m,T,st,ed,id;
int cur[MAXN];
int u[MAXN];
int v[MAXN];
int first[MAXN];
int cnt[MAXN];

bool vis[MAXN];
bool ans[MAXN];

bitset<50001> mask[150005];

void addE(int u,int v,int w)
{
	edge[++id] = (Edge){v,w,first[u]};
	first[u] = id;
}

void dfs(int u)
{
	vis[u] = 1;
	for (int i = first[u];i;i = edge[i].nxt)
		if (!vis[edge[i].to])
		{
			if (edge[i].w)
				ans[edge[i].w] = edge[i].to < u;
			dfs(edge[i].to);
		}
}

int main()
{
	scanf("%d%d%d",&n,&m,&T);
	for (int i = 1;i <= m;i++)
		scanf("%d%d",&u[i],&v[i]);
	if (T == 1)
	{
		for (int i = 1;i <= n;i++)
			cur[i] = i,mask[i][i] = 1;
		for (int i = 1;i <= m;i++)
		{
			mask[n + i] = mask[cur[u[i]]] | mask[cur[v[i]]];
			cur[u[i]] = cur[v[i]] = n + i;
			if (mask[n + i].count() == n)
			{
				ed = i;
				st = u[i];
				break;
			}
		}
		if (!st)
		{
			puts("-1");
			return 0;
		}
		for (int i = 1;i <= n;i++)
			cur[i] = i;
		int nd = n;
		for (int i = 1;i <= ed;i++)
		{
			addE(++nd,cur[u[i]],0);
			cur[u[i]] = nd;
			addE(++nd,cur[v[i]],0);
			cur[v[i]] = nd;
			addE(nd - 1,nd,i);
			addE(nd,nd - 1,i);
		}
		memset(vis,0,sizeof(vis));
		dfs(cur[st]);
		for (int i = 1;i <= m;i++)
			putchar(ans[i] ? 'v' : '^');
		putchar('\n');
	}
	else
	{
		if (n == 2)
		{
			puts("-1");
			return 0;
		}
		for (int i = 1;i <= n;i++)
			cnt[cur[i] = i] = 1;
		for (int i = m;i >= 1;i--)
		{
			if (cnt[cur[u[i]]] > 1)
			{
				ans[i] = 1;
				cnt[cur[u[i]]]--;
				cur[u[i]] = cur[v[i]];
				cnt[cur[v[i]]]++;
			}
			else
			{
				ans[i] = 0;
				cnt[cur[v[i]]]--;
				cur[v[i]] = cur[u[i]];
				cnt[cur[u[i]]]++;
			}
		}
		for (int i = 1;i <= m;i++)
			putchar(ans[i] ? 'v' : '^');
		putchar('\n');
	}
	return 0;
}


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


#define M 1000000007
#define pb push_back
#define mp make_pair
#define s second
#define f first
#define mod 998244353
#define sz(v) (int)(v).size()

#define pii pair<int, int>
#define vi vector<int>
#define ll long long
#define fastio ios_base::sync_with_stdio(false);cin.tie(0)

ll add(ll a,ll b)
{
	a%=M;
	b%=M;
	ll p = (a+b)%M;
	return (p+M)%M;
}

ll mul(ll a,ll b)
{
	a%=M;
	b%=M;
	ll p = (a*b)%M;
	return (p+M)%M;
}


int main()
{
	fastio;
	ll i,j,k,x,y,a,b,c;
	ll p[100010],q[100010],r[100010];
	cin>>x>>y>>a>>b>>c;
	for(i=0;i<a;i++)
		cin>>p[i];
	for(i=0;i<b;i++)
		cin>>q[i];
	for(i=0;i<c;i++)
		cin>>r[i];
	sort(p,p+a);
	sort(q,q+b);
	sort(r,r+c);
	// ll sum=0;
	// set<ll> S;
	// for(i=a-1;i>a-1-x && i>=0;i--)
	// {
	// 	S.insert(p[i]);
	// 	sum += p[i];
	// }
	// for(j=b-1; j>b-1-y && j>=0;j--)
	// {
	// 	S.insert(q[j]);
	// 	sum += q[j];
	// }
	// for(i=c-1;i>=0;i--)
	// {
	// 	ll val = *S.begin();
	// 	if(val<r[i])
	// 	{
	// 		sum+=r[i]-val;
	// 		S.erase(S.begin());
	// 		// S.insert(r[i]);
	// 	}
	// }
	ll sum=0;
	vector<ll> v;
	for(i=a-1;i>a-1-x && i>=0;i--)
		v.pb(p[i]);
	for(j=b-1;j>b-1-y && j>=0;j--)
		v.pb(q[j]);
	for(i=0;i<c;i++)
		v.pb(r[i]);
	sort(v.begin(),v.end());
	ll cnt=0;
	for(i=sz(v)-1;i>=0;i--)
	{
		sum+=v[i];
		cnt++;
		if(cnt==x+y)
			break;
	}
	cout<<sum<<endl;
    return 0;
}





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

namespace D
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = Int32.Parse(Console.ReadLine());
            Job[] jobs = new Job[N];
            for (int i = 0; i < N; i++)
            {
                string[] input = Console.ReadLine().Split();
                jobs[i] = new Job(Int64.Parse(input[0]), Int64.Parse(input[1]));
            }
            jobs = jobs.OrderBy(job => job.B).ToArray();

            long currentTime = 0L;
            foreach (Job job in jobs)
            {
                currentTime += job.A;
                if (currentTime > job.B)
                {
                    Console.WriteLine("No");
                    return;
                }
            }
            Console.WriteLine("Yes");
        }
    }

    class Job
    {
        public long A
        {get;}
        public long B
        {get;}
        public Job(long a, long b)
        {
            this.A = a;
            this.B = b;
        }
    }
}


Measured memory_bytes: 34352
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <fstream>
#include <numeric>
using namespace std;
typedef long long int ll;

#define EPS (1e-7)
#define INF 1e18
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define PI (acos(-1))

#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define rep(i, init, n) for(int i = init; i <(int)(n); i++)

int main() {
    int x, a, b;
    cin >> x >> a >> b;
    string ans = abs(a - x) < abs(b - x) ? "A" : "B";
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 888
#include<iostream>
#include<string>
#include<algorithm>
#define REP(i, n) for(int i = 0; i < n; ++i)
using namespace std;

int main()
{
    int N;
    cin >> N;
    int A[110];
    REP(i, N) cin >> A[i];
    int min = 1000000001, max = 0;
    REP(i, N){
        if (min > A[i]){
            min = A[i];
        }
        if (max < A[i]){
            max = A[i];
        }
    }
    cout << max - min << endl;
    return 0;
}

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

using namespace std;

#define rep(i, a, b) for(auto (i)=a;i<b;i++)
#define list(i, N) for(auto (i)=0;i<N;i++)

typedef long long ll;
typedef vector <ll> vi;
typedef pair <ll, ll> pi;
#define mp make_pair
#define pb push_back
#define eb emplace_back

#define int ll
#define INF 1e18+5
#define mod 1000000007

template<class T>
T max(T a, T b, T c) {
    return max(a, max(b, c));
}

int32_t main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int l, r; cin >> l >> r;
    if(r-l > 2019){
        cout << "0\n"; return 0;
    }
    int ans = INF;
    rep(i,l,r){
        rep(j,i+1,r+1){
            ans = min(ans,(i%2019 * j%2019) % 2019);
        }
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 256
Imports System.Collections.Generic
Imports System.Console

Module Program
    Sub Main()
        Dim N As Integer = NextInt()
        Dim K As Integer = NextInt()
        Dim a, b As Integer

        For i As Integer = 0 To N - 1
            Dim x_i As Integer = NextInt()

            If x_i <= K \ 2 Then
                a += x_i
            Else
                b += K - x_i
            End If
        Next

        WriteLine((a + b) * 2)
    End Sub

    Function NextInt() As Integer
        Return CInt(NextString())
    End Function

    Function NextString() As String
        Dim result As New List(Of Char)
        Do
            Dim tmp As Integer = Read()
            If tmp < 0 Then Exit Do
            Dim nextChar As Char = Chr(tmp)

            If Not Char.IsWhiteSpace(nextChar) Then
                result.Add(nextChar)
            ElseIf nextChar <> vbCr Then
                Exit Do
            End If
        Loop
        Return New String(result.ToArray())
    End Function

End Module


Measured memory_bytes: 19920
#include<iostream>
#include<cstdint>
#include<algorithm>
#include<numeric>
#include<string>

int A[1000];

int main() {
  int N, M; std::cin >> N >> M;
  int sum = 0;
  for(int i = 0; i < N; ++i) {
    std::cin >> A[i];
    sum += A[i];
  }
  std::sort(A, A+N, [](int x, int y){ return x > y; });
  if(A[M-1]*4*M >= sum){
    std::cout << "Yes" << std::endl;
  } else {
    std::cout << "No" << std::endl;
  }

  return 0;
}


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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(a)      (a).begin(),(a).end()
#define rall(a)     (a).rbegin(),(a).rend()

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef vector<vector<int>> vvi;
typedef unordered_map<int,int> uoii;
typedef unordered_map<string,int> uosi;

const int MOD = 1e9+7;

const int INF = 1e10;




int32_t main()
{
    
    IOS
    int  n,m;
    cin>>n>>m;

    int ans=(n*(n-1))/2;
    ans+=(m*(m-1))/2;
    cout<<ans;


    return 0;
}


Measured memory_bytes: 256
#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 ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
using namespace std;
 
int main(){
    int a,b;
    cin>>a>>b;
    cout<<6-a-b<<endl;
    return 0;
}

Measured memory_bytes: 256
package main

import "fmt"

func main(){

	var N, K, X, Y int
	fmt.Scan(&N)
	fmt.Scan(&K)
	fmt.Scan(&X)
	fmt.Scan(&Y)

	var sum int
	for i := 1; i <= N; i++ {
		if i <= K {
			sum += X
		} else {
			sum += Y
		}
	}
	fmt.Print(sum)
}


Measured memory_bytes: 512
#include <iostream>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
const long long INF = 1e9 + 7;
using namespace std;
typedef long long ll;

map<int, int> mp;
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	sort(a.begin(), a.end());
	if (n == 2) {
		for (int i = 1; i <= a[0]; i++) {
			if (a[0] % i == 0 && a[1] % i == 0) cout << i << endl;
		}
	}
	else {
		for (int i = 1; i <= a[0]; i++) {
			if (a[0] % i == 0 && a[1] % i == 0 && a[2] % i == 0) cout << i << endl;
		}
	}
	return 0;
}


Measured memory_bytes: 3176
#include <bits/stdc++.h>
typedef long long ll;
#define rep(k,i,n) for(ll i=k;i<n;++i)
using namespace std;
int main(void){
    // Your code here!
    ll n,m;
    cin>>n>>m;
    ll ac=0,wa=0;
    ll WA[n];
    bool flag[n];
    rep(0,i,n){
        WA[i]=0;
        flag[i]=false;
    }
    rep(0,i,m){
        ll p;
        string S;
        cin>>p>>S;
        if(flag[p-1])continue;
        if(S=="AC"){
            ++ac;
            wa+=WA[p-1];
            flag[p-1]=true;
        }
        else if(S=="WA")++WA[p-1];
    }
    cout<<ac<<" "<<wa<<endl;
    
}

Measured memory_bytes: 1152
#include<stdio.h>
int main()
{
	int i, n, a[101], flag=1;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(i=0;i<n;i++)
	{
		if(a[i]%2==0)
		{
			if(a[i]%3==0||a[i]%5==0)
			flag=1;
			else
			{
				flag=0;
				break;
			}
			
		}
	}
	if(flag==1)
	printf("APPROVED");
	else
	printf("DENIED");
	

	return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <bitset>
#include <set>
#include <unordered_set>
#include <cmath>
#include <complex>
#include <deque>
#include <iterator>
#include <numeric>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <limits>
#include <iomanip>
#include <functional>
#include <cassert>
using namespace std;

using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define rep(i, k, n) for (ll i=k; i<(ll)n; ++i)
#define REP(i, n) rep(i, 0, n)
#define ALL(v) v.begin(),v.end()
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; }
#define DEBUG_VLL(vec) REP(sz, vec.size()) std::cerr<<vec[sz]<<(sz==vec.size()-1?'\n':' ');

const long long MOD = 1000000007;
const long long HIGHINF = (long long)1e18;
const int INF = (int)1e9;

ll n, m, d;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> m >> d;
    double ans;
    if (d == 0) {
        ans = (double)(n * (m - 1)) / (double)(n * n);
    } else {
        ans = (double)(2 * (n - d) * (m - 1)) / (double)(n * n);
    }
    cout << fixed << setprecision(12) << ans << '\n';
    return 0;
}


Measured memory_bytes: 256
class Stack(object):
    def __init__(self):
        self.container = []
    
    def __len__(self):
        return len(self.container)
    
    def push(self, elem):
        self.container.append(elem)
    
    def pop(self):
        idx = len(self.container) -1
        if idx < 0:
            return None
        ret = self.container[idx]
        del self.container[-1]
        return ret
    
    def compare(self, val):
        return self.container[-1] == val

if __name__ == '__main__':
    string = [int(i) for i in input()]
    ret = 0
    stack = Stack()
    stack.push(string[0])
    for s in string[1:]:
        if stack.__len__() == 0:
            stack.push(s)
            continue
        if stack.compare(s):
            stack.push(s)
        else:
            ret += 2
            stack.pop()

    print(ret)

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

int main(){
	int n;
	cin>>n;
	vector<pair<int,int>> a(n);
	for (int i = 0; i < n; i++) {
		cin>>a[i].first;
		a[i].second=i+1;
	}
	sort(a.begin(),a.end());
	for (int i = 0; i < n; i++) {
		cout<<a[i].second<<" ";
	}
	cout<<endl;
}

Measured memory_bytes: 1664
#include <stdio.h>

int main(void) {
  int H, W, i, j;

  while(1) {
    scanf("%d %d",&H,&W);
    if(H==0 && W==0) break;

    for(i=0;i<H;i++) {
      for(j=0;j<W;j++) {
        if((i+j)%2 == 0) {
          printf("#");
        } else {
          printf(".");
        }
      }
      printf("\n");
    }
    printf("\n");
  }
  return 0;
}


Measured memory_bytes: 2040
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
long long noOfWays(vector<int>v,int s){
    int n = v.size();
    // long long dp[n+1][s+1];
    // for(int i=0;i<=n;i++){
    //     for(int j=0;j<=s;j++){
    //         if( (i == 0 && j == 0) || j == 0 ){
    //             dp[i][j] = 1;
    //         }else if(i == 0){
    //             dp[i][j] = 0;
    //         }else{
    //             if(j >= v[i-1]){
    //                 dp[i][j] = dp[i-1][j] + dp[i-1][j-v[i-1]];
    //             }else {
    //                 dp[i][j] = dp[i-1][j];
    //             }
    //         }
    //     }
    // }
    // return dp[n][s];
    long long dp[s+1];
    memset(dp,0,sizeof(dp));
    dp[0] = 1;
    for(int j=0;j<=s;j++){
        for(int i=0;i<n;i++){
            if(j >= v[i]){
                dp[j] += (dp[j-v[i]])%MOD;
                dp[j] = (dp[j])%MOD;
            }
        }
    }
    return dp[s];
}
int main(){
    int s;
    cin >> s;
    vector<int>v;
    for(int i=3;i<=s;i++){
      v.push_back(i);
    }
    vector<vector<int>>ans;
    int n = v.size();
    cout << noOfWays(v,s);
}

Measured memory_bytes: 3576
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
int main()
{
	long n,w;
	cin>>n>>w;
	long value[n], weight[n];
	long sum = 0;
	for(long i=0;i<n;i++)
		cin>>weight[i]>>value[i],sum+=value[i];
	vector<long> dp(sum+1,INF);
	dp[0] = 0;
	for(long item=0;item<n;item++)
	{
		for(long already_value = sum - value[item]; already_value>=0; --already_value)
		{
			dp[already_value + value[item]] = min(dp[already_value + value[item]], dp[already_value] + weight[item]);
		}
	}
	long result = 0;
	for(long i=0;i<=sum;i++)
	{
		if(dp[i]<=w)
			result = max(result,i);
	}
	printf("%ld\n",result);
}

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

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

#define p_ary(ary,a,b,i) do { cout << "["; for (int (i) = (a);(i) < (b);++(i)) cout << ary[(i)] << ((b)-1 == (i) ? "" : ", "); cout << "]\n"; } while(0)
#define p_map(map,it) do {cout << "{";for (auto (it) = map.begin();;++(it)) {if ((it) == map.end()) {cout << "}\n";break;}else cout << "" << (it)->first << "=>" << (it)->second << ", ";}}while(0)

void dfs(int i,int p,vector<vector<int>>& edges,vector<P>& val,vector<bool>& c) {
    if (p != -1) {
        val[i].first = max(val[i].first,val[p].first-1);
        val[i].second = min(val[i].second,val[p].second+1);
        if (val[i].first < val[p].first-1 && val[i].second > val[p].second+1) return;
    }
    for (int j : edges[i]) if (j != p) {
        if (!c[j]) dfs(j,i,edges,val,c);
        else if (val[i].first-1 > val[j].first || val[i].second+1 < val[j].second || val[i].first%2 == val[j].first%2) {
            cout << "No" << endl;
            exit(0);
        }
    }
}

int main() {
    int n;
    cin >> n;
    vector<bool> c(n,false);
    vector<int> sup(n,1e7),inf(n,-1e7);
    vector<vector<int>> edges(n);
    for (int i = 0;i < n-1;++i) {
        int u,v;
        scanf("%d%d", &u, &v);
        u--;v--;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    int k;
    cin >> k;
    vector<P> ls(k);
    for (int i = 0;i < k;++i) {
        int v,p;
        cin >> v >> p;
        v--;
        c[v] = true;
        sup[v] = inf[v] = p;
        ls[i] = P(p,v);
    }
    priority_queue<P> q;
    for (int i = 0;i < k;++i) q.push(ls[i]);
    while (!q.empty()) {
        P p = q.top();
        q.pop();
        for (int i : edges[p.second]) {
            if (!c[i] && p.first-1 > inf[i]) {
                q.push(P(p.first-1,i));
                inf[i] = p.first-1;
            }
            if (c[i] && (p.first-1 > inf[i] || p.first%2 == inf[i]%2)) {
                cout << "No" << endl;
                exit(0);
            }
        }
    }
    cout << "Yes" << endl;
    for (int i = 0;i < n;++i) cout << inf[i] << endl;
    return 0;
}

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

namespace ARC82_C
{
    class Program
    {
        static void Main(string[] args)
        {

            var n = int.Parse(Console.ReadLine());

            var a = Console.ReadLine().Split().Select(int.Parse).ToArray();
            var x = new Dictionary<int, int>();

            for (int i = 0; i < n; i++)
            {
                if (!x.ContainsKey(a[i])) x[a[i]] = 0;
                if (!x.ContainsKey(a[i] + 1)) x[a[i] + 1] = 0;
                if (!x.ContainsKey(a[i] - 1)) x[a[i] - 1] = 0;

                x[a[i]]++;
                x[a[i]-1]++;
                x[a[i]+1]++;

            }


            Console.WriteLine(x.Values.Max());
        }
    }
}


Measured memory_bytes: 24160
h,w=map(int,input().split())
s=["$"*(w+2)]+["$"+input()+"$" for _ in range(h)]+["$"*(w+2)]

ans=[[0]*w for i in range(h)]


for i in range(1,h+1):
    for g in range(1,w+1):
        b=0
        for l in [-1,0,1]:
            for m in [-1,0,1]:
                if not(l==0 and m==0) and s[i+l][g+m]=="#":
                    b+=1
        if s[i][g]==".":
            ans[i-1][g-1]=b
        else:
            ans[i-1][g-1]="#"

for i in range(h):
    st=""
    for g in range(w):
        st+=str(ans[i][g])
    print(st)

Measured memory_bytes: 3064
import java.util.*;

public class Main {
    //C - Many Medians/
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        long[] X = new long[200000];
        //ArrayList<Long> X = new ArrayList();
        for(int i = 0; i < N; i++) {
            X[i] = scanner.nextLong();
        }

        long[] sortedX = Arrays.copyOfRange(X, 0, N);
        Arrays.sort(sortedX);
        long medianPrev = sortedX[sortedX.length / 2 - 1];
        long median = sortedX[sortedX.length / 2];

        for (int i = 0; i < N; i++) {
            if(X[i] <= medianPrev) {
                System.out.println(median);
            }
            else {
                System.out.println(medianPrev);
            }
        }
    }
}


Measured memory_bytes: 94796
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,l;
	cin>>n>>l;
	vector< string > s(n);
	for(int i=0;i<n;i++)
		cin>>s.at(i);
	sort(s.begin(),s.end());
	for(int i=1;i<n;i++)
		s.at(0)=s.at(0)+s.at(i);
	cout<<s.at(0)<<endl;

}

Measured memory_bytes: 256
N, M = map(int, input().split())
S = []
for _ in range(M):
    arr = list(map(int, input().split()))
    bit = 0
    for i in arr[1:]:
        # print(i)
        bit = bit | (1 << (i - 1))
    # print('bit', bit, bin(bit))
    S.append(bit)
    # S.append(arr[1:])
P = list(map(int, input().split()))
# print('S')
# print(S)
# print('P', P)
ans = 0
for bit in range(1 << N):
    cnt = 0
    for i in range(M):
        # print('S[i], bit', bin(S[i]), bin(bit))
        p = S[i] & bit
        # print('p', bin(p))
        on = 0
        for j in range(N):
            # print('judge', 1 << j, p & (1 << j))
            if p & (1 << j):
                on += 1
            # if p & (1 << j):
            #     on += 1
        # print('P[i], i, on', P[i], i, on)
        # print('on', on)
        if (on % 2) != P[i]:
            break
    else:
        ans += 1
print(ans)


Measured memory_bytes: 3064
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

typedef pair <long long, long long> pii;

const long long MAX_N = 3e3 + 9, inf = 1000000LL * 1000000LL * 1000000LL;
long long n, m;
string s, t, ans;
long long dp[MAX_N][MAX_N];
pair <pii, char> par[MAX_N][MAX_N];

int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> s >> t;
	n = s.size();
	m = t.size();
	s = '#' + s;
	t = '#' + t;
	for (long long i = 1; i <= n; i++)
		for (long long j = 1; j <= m; j++) {
			if (dp[i - 1][j] < dp[i][j - 1]) {
				dp[i][j] = dp[i][j - 1];
				par[i][j] = {{i, j - 1}, '#'};
			}
			else {
				dp[i][j] = dp[i - 1][j];
				par[i][j] = {{i - 1, j}, '#'};
			}

			if (s[i] == t[j] && dp[i][j] < 1 + dp[i - 1][j - 1]) {
				dp[i][j] = 1 + dp[i - 1][j - 1];
				par[i][j] = {{i - 1, j - 1}, s[i]};
			}
		}

	while (n && m) {
		if (par[n][m].second != '#')
			ans = par[n][m].second + ans;

		pii tmp = par[n][m].first;
		n = tmp.first;
		m = tmp.second;
	}

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

Measured memory_bytes: 283008
a, b = map(int, input().split())

e = 0
squ = 0
for i in range(0, 16, 2):
    #for j in range(b)
    #s[i] = 1
    #s[i+1] = 0
    e += 1
    squ += 1

if e>=a and squ>=b:
    print("Yay!")
else:
    print(":(")


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<n; i++)
#define ll long long

using namespace std;

int main() {
    string S;
    cin >> S;
    ll size = S.size()+1;
    vector<int> left(size);
    vector<int> right(size);

    ll num;
    
    num = 0;
    for (int i = 0; i < size; i++) {
        left[i] = num;
        if (i < size-1 && S[i] == '<')
            num++;
        else
            num = 0;
    }

    num = 0;
    for (int i = size-1; i >= 0; i--) {
        right[i] = num;
        if (i > 0 && S[i-1] == '>')
            num++;
        else
            num = 0;
    }

    ll ans = 0;
    rep(i, size) {
        ans += max(left[i], right[i]);
    }

    cout << ans << endl;
}


Measured memory_bytes: 7716