akhauriyash/Code-Regression huggingface dataset:
void main()
{
    string n = rdStr;
    long k = rdElem;

    long len = n.length;
    long[][][] dp = new long[][][](len+1, k+2, 2);
    dp[0][0][0] = 1;
    foreach (i, x; n)
    {
        long d = x - '0';
        foreach (j; 0 .. k+1)
        {
            foreach (u; 0 .. 2)
            {
                foreach (v; 0 .. (u?10:d+1))
                {
                    dp[i+1][v?j+1:j][u|(v<d)] += dp[i][j][u];
                }
            }
        }
    }

    dp[len][k].sum.writeln;
}

enum long mod = 10^^9 + 7;
enum long inf = 1L << 60;

T rdElem(T = long)()
if (!is(T == struct))
{
    return readln.chomp.to!T;
}

alias rdStr = rdElem!string;
alias rdDchar = rdElem!(dchar[]);

T rdElem(T)()
if (is(T == struct))
{
    T result;
    string[] input = rdRow!string;
    assert(T.tupleof.length == input.length);
    foreach (i, ref x; result.tupleof)
    {
        x = input[i].to!(typeof(x));
    }
    return result;
}

T[] rdRow(T = long)()
{
    return readln.split.to!(T[]);
}

T[] rdCol(T = long)(long col)
{
    return iota(col).map!(x => rdElem!T).array;
}

T[][] rdMat(T = long)(long col)
{
    return iota(col).map!(x => rdRow!T).array;
}

void rdVals(T...)(ref T data)
{
    string[] input = rdRow!string;
    assert(data.length == input.length);
    foreach (i, ref x; data)
    {
        x = input[i].to!(typeof(x));
    }
}

void wrMat(T = long)(T[][] mat)
{
    foreach (row; mat)
    {
        foreach (j, compo; row)
        {
            compo.write;
            if (j == row.length - 1) writeln;
            else " ".write;
        }
    }
}

import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;
import std.range;
import std.math;
import std.numeric;
import std.mathspecial;
import std.traits;
import std.container;
import std.functional;
import std.typecons;
import std.ascii;
import std.uni;
import core.bitop;

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

int main() {
    int a, b, d, r;
    double f;
    cin >> a >> b;
    
    d = a / b;
    r = a % b;
    f = (double)a / b;
    
    cout << d << " " << r << " " << fixed << f << endl;
}


Measured memory_bytes: 3292
n,k,s=map(int,input().split())
answer=[]
if s==1000000000 and k!=n:
    for i in range(k+1):
        answer.append((10**9)//2)
    for i in range(n-k-1):
        answer.append(1)
else:
    for i in range(k):
        answer.append(s)
    for i in range(n-k):
        answer.append(10**9)
for i in range(n):
    print(answer[i],end=" ")

Measured memory_bytes: 5144
#include<bits/stdc++.h>
using namespace std;
int a,b,c;
int main()
{
	scanf("%d%d%d",&a,&b,&c);
	if(a==b&&b==c)
	{
		puts("No");
		return 0;
	}
	if(a==b||a==c||b==c)
	{
		puts("Yes");
		return 0;
	}
	puts("No");
	return 0;
}


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

using namespace std;
using ll = long long;

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

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

  string ans = "";
  if (a > b) {
    rep(i, a) ans += b + '0';
  } else {
    rep(i, b) ans += a + '0';
  }

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


Measured memory_bytes: 256
X, Y = (int(i) for i in input().split())

def power(a, b):
	if b == 0:
		return 1
	elif b == 1:
		return a % 1000000007
	elif b % 2 == 0:
		return (power(a, b//2) ** 2) % 1000000007
	else:
		return (power(a, b//2) ** 2 * a) % 1000000007

def divide(a, b):
	return (a * power(b, 1000000005)) % 1000000007


#階乗の逆元を求める
fac_lim = 1000000
fac = [None]*(fac_lim+1)
fac[0] = 1
for i in range(fac_lim):
    fac[i+1] = fac[i] * (i+1)
    fac[i+1] = fac[i + 1] % 1000000007

fac_inv = [None]*(fac_lim+1)
fac_inv[fac_lim] = power(fac[fac_lim], 1000000005)
for i in range(fac_lim, 0, -1):
    fac_inv[i-1] = (fac_inv[i] * i)  % 1000000007

def conv(a, b):
    return (fac[a] * fac_inv[a-b] * fac_inv[b]) % 1000000007


MOD = 10**9 + 7
if (X+Y)%3 != 0:
    ans = 0
else:
    N = (X+Y)//3
    M = X - Y
    if (N+M)%2 !=0:
        ans = 0
    else:
        a = (N+M)//2
        if 0 <= a <= N:
            ans = conv(N, a)
        else:
            ans = 0
print(ans%MOD)

Measured memory_bytes: 149276
//AUTHOR:- Avinash//
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
#define ll long long int
#define lll long long
#define fo(i,n) for(int i=0;i<n;i++)
#define take(a,i,n) for(int i=0;i<n;i++) cin>>a[i]
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ld long long double
#define d1(x) cout<<(x)<<endl
#define T int t;cin>>t;while(t--)
#define hell 1000000007
#define ex endl;
#define F first
#define maxn 200001
#define pi 3.14159265
#define S second
#define P pair<int,int>
#define PP pair<int,pair<int,int>>
#define pb push_back
#define in insert
#define vec vector<ll>
#define vec2 vector<vector<int>>
#define s(a,n) sort(a,a+n);
#define sv(a) sort(a.begin(),a.end());   
#define MAX 1000
//Author:-Avinash//

ll power(ll x, ll y, ll m) 
{ 
    if (y == 0) 
        return 1; 
    ll p = power(x, y/2, m) % m; 
    p = (p * p) % m; 
    return (y%2 == 0)? p : (x * p) % m; 
} 
 
ll modInverse(ll a, ll m) 
{  
    return power(a, m-2, m);  
}

int main()
{
  FAST
  float d,t,s;
  float tt = 0;
  cin>>d>>t>>s;
  tt = d/s;
  //cout<<tt;
  if(tt<=t){
    cout<<"Yes";
  } 
  else{
    cout<<"No";
  }
}
  




Measured memory_bytes: 3724
import bisect

n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))

counter = 0

for t in T:
    a = bisect.bisect_left(S, t)
    if a < n:
        if S[a] == t:
            counter += 1

print(counter)


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

int main(){
    int n; cin >> n;
    for(int i = 1; i <= 9; i++){
        for(int j = 1; j <= 9; j++){
            if(i * j == n){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
n, k = [int(_) for _ in input().split()]
s = input()
x = []

cnt = 0
c0 = '1'
for c in s:
    if c == c0:
        cnt += 1
    else:
        x.append(cnt)
        c0 = c
        cnt = 1
else:
    if cnt != 0:
        x.append(cnt)

if s[-1] == '0':
        x.append(0)

if len(x) <= k*2+1:
    print(sum(x))
else:
    y = sum(x[0:k*2+1])
    ans = y
    for i in range(2,len(x)-k*2,2):
        y = y - sum(x[i-2:i]) + sum(x[i+2*k-1:i+2*k+1])
        if ans < y:
            ans = y
    print(ans)


Measured memory_bytes: 4596
# include <bits/stdc++.h>
using namespace std;
bool IsOdd(long long n) { return n & 1; }
bool IsEven(long long n) { return !(n & 1); }
long long read() {long long a;cin >> a;return a;}

long long F(long long b)
{
    if (IsOdd(b))
        return (long long)IsOdd((b+1)/2);
    else
        return b == 0 ? 0 : b ^ F(b-1);
}

int main()
{
    cout << (F(read()-1) ^ F(read())) << endl;
    return 0;
}



Measured memory_bytes: 3640
// includes
#include <cstdio>
#include <cstdint>
#include <iostream>
#include <iomanip>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <utility>
#include <functional>
#include <cmath>
#include <climits>
#include <bitset>

// macros
#define ll long long int
#define pb push_back
#define mk make_pair
#define pq priority_queue
#define FOR(i, a, b) for(int i=(a); i<(b);++i)
#define rep(i, n) FOR(i, 0, n)

using namespace std;

//  types
typedef pair<int, int> P;
typedef pair<ll, int> Pl;
typedef pair<ll, ll> Pll;
 
// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double EPS = 1e-10;

// solve

int main(int argc, char const* argv[])
{
  ll a[7];
  rep(i, 7){
    cin >> a[i];
  }
  ll res = 0;
  res += 2 * a[1];
  if(a[0] == 0){
    res += 4 * (a[3] / 2);
    res += 4 * (a[4] / 2);
  }else if(a[3] == 0){
    res += 4 * (a[0] / 2);
    res += 4 * (a[4] / 2);
  }else if(a[4] == 0){
    res += 4 * (a[0] / 2);
    res += 42 * (a[3] / 2);
  }else{
    res += 4 * ((a[0] - 1) / 2);
    res += 4 * ((a[3] - 1) / 2);
    res += 4 * ((a[4] - 1) / 2);
    int num = (a[0] % 2) + (a[3] % 2) + (a[4] % 2);
    if(num == 3 || num == 2)res += 6;
    else if(num == 1)res += 8;
    else res += 12;
  }
  cout << res / 2 << endl;
	return 0;
}


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

#define ll long long
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define debug(x) cerr<<#x<<": "<<x<<'\n'

using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

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

template<class T=int>
T in(){T x;cin>>x;return (x);}
template<class T>
void print(T& x){cout<<x<<'\n';}

const int MOD =(int)1e9+7;
const int MAX =510000;

ll fac[MAX],finv[MAX],inv[MAX];
void COMint(){
    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;
    }
}
ll 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;
}

ll gcd(ll a,ll b){
    if(b==0)return a;
    if(a>b){
        swap(a,b);
    }
    return gcd(a,b%a);
}
ll lcm(ll a,ll b){
    ll g;g=gcd(a,b);
    return a*b/g;
}
int main() {
    //COMint();
    int N=in();
    int D=in();
    int X[N][D];
    REP(i,N){
        REP(j,D){
            cin>>X[i][j];
        }
    }
    int ans;ans=0;
    double temp;
    REP(i,N-1){
        for(int j=i+1;j<N;j++){
            temp=0;
            REP(k,D){
                temp=temp+(pow(X[i][k]-X[j][k],2));
            }
            temp=sqrt(temp);
            if(temp==floor(temp)){
                ans++;
            }
        }
    }
    print(ans);
}

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

#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, n, m) for (int i = n; i < m; i++)
#define ll long long int

using namespace std;

int main()
{
  string s;
  cin >> s;
  REP(i, s.length()) {
    if(s[i] == '1') {
      cout << 9;
    } else {
      cout << 1;
    }
  }
  cout << endl;
}


Measured memory_bytes: 256
n=int(input())
aa=[]
aa=list(map(int,input().split()))
# a=[[aa[i],i] for i in range(n)]

a=sorted(aa)
sum=0
mae=0
index=[0 for i in range(n)]
for i in range(n-1):
    if a[i]!=a[i+1]:
        index[a[i]-1]=i-mae+1
        sum+=(i-mae+1)*(i-mae)/2
        mae=i+1
index[a[n-1]-1]=n-mae
sum+=(n-mae)*(n-mae-1)/2

for ii in aa:
    ans=sum-index[ii-1]+1
    print(int(ans))

Measured memory_bytes: 26140
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

S = input()
T = input()

pos = -1
for i in range(len(S) - len(T) + 1):
    for j in range(len(T)):
        if S[i + j] != T[j] and S[i + j] != '?':
            break
    else:
        pos = max(pos, i)

if pos == -1:
    print('UNRESTORABLE')
else:
    ans = list(S)
    ans[pos:pos + len(T)] = list(T)
    for i in range(len(ans)):
        if ans[i] == '?':
            ans[i] = 'a'
    print(''.join(ans))


Measured memory_bytes: 3064
#include<bits/stdc++.h> 
using namespace std; 
// Binary indexed tree supporting binary search.
 
 
#define x first
#define y second
 
#define forn(i, n) for(int i = 0; i < int(n); ++i)
 
typedef pair<int, int> pii;
//#define forn(i, a,b) for (int i = (int) a; i <= (int) b; ++i)
struct query{
	int a,b,c,d;
};
int main(){
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int N,M,Q;
    cin>>N>>M>>Q;
    vector<query> mevan(Q);
    forn(i,Q){
    	cin>>mevan[i].a>>mevan[i].b>>mevan[i].c>>mevan[i].d;
	}
	vector<vector<vector<int> > > numbers(M+1);
	for(int i = 1;i<=M;i++){
		vector<int> start;
		start.push_back(i);
		numbers[i].push_back(start);
	}
	for(int j =2 ;j<=N;j++){
		vector<vector<vector<int> > > numb_new(M+1);
		for(int i = 1;i<=M;i++){
			for(int z = 1 ; z<=i;z++){
				for(int yy = 0 ;yy<numbers[z].size();yy++){
					vector<int> mode = numbers[z][yy];
					mode.push_back(i);
					numb_new[i].push_back(mode);
				}
			}
		}
		numbers = numb_new;
	}
	int maxa =0 ;
	for(int j = 1; j <=M;j++){
		for(int yy = 0;yy<numbers[j].size();yy++){
			vector<int> numm = numbers[j][yy];
			int tot =0;
			for(int u = 0;u<Q;u++){
				if(numm[mevan[u].b-1] - numm[mevan[u].a-1] == mevan[u].c){
					tot+= mevan[u].d;
				}
			}
			maxa = max(maxa,tot);
		}
	}
//	for(int j = 1;j<=M;j++){
//		for(int jj = 0;jj<numbers[j].size();jj++){
//			forn(i , N){
//				cout<<numbers[j][jj][i]<<" ";
//			}
//			cout<<endl;
//		}
//	}
	cout<<maxa<<endl;
	return 0;	
}

Measured memory_bytes: 18116
#include<bits/stdc++.h>
using namespace std;
struct nd{int x,y;friend bool operator < (nd a,nd b){if(a.x==b.x)return a.y<b.y;return a.x<b.x;}};
const int N=5100;
int a[N],n,m,c[N][N],dfn[N],fir[N],nxt[N],to[N],cnt,in[N];
map<int,int>l;
void add(int u,int v)
{
	to[++cnt]=v,nxt[cnt]=fir[u],fir[u]=cnt;
}
void dfs(int x)
{
	dfn[x]=1;
	for(int i=1;i<=n;i++)
	{
		if(!c[x][i])continue;
		if(dfn[i])continue;
		dfn[i]=1;
		dfs(i);add(x,i);in[i]++;
	}
}
int main()
{//freopen("rearranging.in","r",stdin);
	//freopen("rearranging.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		if(__gcd(a[i],a[j])!=1)
		c[i][j]=c[j][i]=1;l[a[i]]=i;
	}
	for(int i=1;i<=n;i++)
	if(!dfn[i])dfs(i);
	priority_queue<nd>q;
	for(int i=1;i<=n;i++)
	{
		if(!in[i])q.push({a[i],i});
	}
	while(!q.empty())
	{
		int x=q.top().y;q.pop();
		for(int i=fir[x];i;i=nxt[i])
		{
			in[to[i]]--;if(in[to[i]]==0)q.push({a[to[i]],to[i]});
		}printf("%d ",a[x]);
	}
}

Measured memory_bytes: 40576
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=5e2+5;
int n,k,tot,nxt[N],mat[N][N];

int main() {
	scanf("%d",&k),printf("%d\n",min(k,500));
	if(k<=500) for(int i=1;i<=k;++i,puts("")) for(int j=1;j<=k;++j) printf("%d ",i);
	else {
		n=500,k-=n,tot=0;
		for(int i=1;i<n;++i) nxt[i]=i+1;nxt[n]=1;
		for(int i=1;i<=n;++i,k-=(bool)(k)) {
			int a=++tot,b=k?++tot:tot;
			for(int x=1,y=i;x<=n;++x,y=nxt[y]) mat[x][y]=(x&1)?a:b;
		}
		for(int i=1;i<=n;++i,puts("")) for(int j=1;j<=n;++j) printf("%d ",mat[i][j]);
	}
	return 0;
}

Measured memory_bytes: 2176
n, k = gets.split.map(&:to_i)
w = n - k
part1 = 1
part2 = w + 1

puts part1 * part2 % (10 ** 9 + 7)

(1..k-1).each do |i|
  if k - i > 0
    part1 = part1 * (k - i) / i
  else
    part1 = 0
  end

  if w + 1 - i > 0
    part2 = part2 * (w + 1 - i) / (i + 1)
  else
    part2 = 0
  end

  puts part1 * part2 % (10 ** 9 + 7)
end

Measured memory_bytes: 2172
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>

typedef long long ll;

int compare_asc(const void * a,  const void * b){
    return *(ll*)a - *(ll*)b;
}
ll max(ll a, ll b){ return (a > b)? a : b;}


ll A[100001];

int main(void){
    int N;
    scanf("%d",&N);
    
    for(int i = 1; i <= N; i++){
        scanf("%lld", A+i);
    }
    A[0] = 0;
    qsort(A,N+1,sizeof(ll),compare_asc);
    
    
    //for(int i = 0; i <= N; i++){ printf("%lld ", A[i]); } puts("");
    

    ll n,r;

    ll * l = std::lower_bound(A+1,A+N+1,A[N]/2);
    n = A[N];
    
    ll r_1 = ((*l)*2 >= n)? n-(*l): *l;
    ll r_2 = ( (*(l-1)) * 2 >= n)? n - *(l-1) : *(l-1);
    
    
    r = (r_1 > r_2)? *l: *(l-1);

    printf("%lld %lld",n,r);
}

Measured memory_bytes: 1788
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <cmath>
#include <complex> // complex<double> a(1.2 , 2.3);// real(): 1.2, imag()2.3
using namespace std;

#define MOD 1000000007
#define ll long long
#define ld long double
#define FOR(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rmsame(a) sort(all(a)),a.erase(unique(all(a)), a.end())
#define rmvector(a,b) rep(i,a.size())rep(j,b.size())if(a[i]==b[j]){a.erase(a.begin()+i);i--;break;}
template<typename X> bool exist(vector<X> vec, X item){return find(all(vec), item)!=vec.end();}

string itob(int a){
  string ret = "";
  while(a!=0){
    if(a%2 == 1) ret+='1';
    else ret+='0';
    a/=2;
  }

  while(ret.size() <= 2){
    ret+='0';
  }
  reverse(ret.begin(), ret.end());
   return ret;
}

bool cal(string num, string op){
  int ans = num[0]-'0';
  rep(i,3){
    if(op[i]=='1')ans += num[i+1]-'0';
    else ans -= num[i+1]-'0';
  }
  if(ans == 7) return true;
  else
    return false;
}

void outp(string num, string op){
  cout << num[0];
  rep(i,3){
    if(op[i]=='1')cout << '+' << num[i+1];
    else cout << '-' << num[i+1];
  }
  cout << "=7" << endl;
}

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

  ll i = 0;
  while (i<= 100){
    string a = itob(i);
    if(cal(str,a)){
      outp(str,a);
      return 0;
    }
 
    i++;
  }
  
  //cout << fixed << setprecision(16) << ans << endl;
  return 0;
}


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

using namespace std;

#define MAX_V 1001
#define MAX_N 100
#define MAX_M 100

struct P{
  int u,v;
  double cost;
  P(int u,int v,double cost) :
    u(u),v(v),cost(cost) {}

  bool operator < (const P &p)const{
    return cost < p.cost;
  }
};

int V,match[MAX_V],M;
vector<int> G[MAX_V];
vector<P> vec;
bool used[MAX_V];

void add_edge(int u,int v){
  G[u].push_back(v);
  G[v].push_back(u);
}

bool dfs(int v){
  used[v] = true;
  for(int i = 0 ; i < (int)G[v].size() ; i++){
    int u = G[v][i],w = match[u];
    if(w < 0 || (!used[w] && dfs(w))){
      match[v] = u;
      match[u] = v;
      return true;
    }
  }
  return false;
}

int bipartite_matching(){
  int res = 0;
  memset(match,-1,sizeof(match));
  for(int v = 0 ; v < V ; v++){
    if(match[v] < 0){
      memset(used,false,sizeof(used));
      if(dfs(v)){ res++; }
    }
  }
  return res;
}

double getDist(double x1,double y1,double x2,double y2){
  return sqrt(pow(x1-x2,2)+pow(y1-y2,2));
}

bool c(int x){
  for(int i = 0 ; i < MAX_V ; i++){ G[i].clear(); }
  for(int i = 0 ; i < x ; i++){
    add_edge(vec[i].u,vec[i].v);
  }
  return (bipartite_matching() == M);
}

void solve(){
  int l = 0, r = vec.size();
  while(r - l > 0){
    int mid = (l + r) / 2;
    if(c(mid)){
      r = mid;
    }else{
      l = mid+1;
    }
  }
  printf("%.10f\n",vec[r-1].cost);
}

int main(){
  int N;
  double x[MAX_N],y[MAX_N],v[MAX_N];
  while(cin >> N >> M, N){
    for(int i = 0 ; i < N ; i++){
      cin >> x[i] >> y[i] >> v[i];
    }
    vec.clear();
    for(int i = 0 ; i < M ; i++){
      int X,Y;
      cin >> X >> Y;
      for(int j = 0 ; j < N ; j++){
        vec.push_back(P(j,i+N,getDist(x[j],y[j],X,Y)/v[j]));
      }
    }
    V = N + M;
    sort(vec.begin(),vec.end());
    solve();
  }
  return 0;
}

Measured memory_bytes: 1548
#include <stdio.h>
#include <string.h>
#define LEN 100005

typedef struct pp {
    char name[100];
    int t;
} P;

P Q[LEN];
int head, tail, n;

void enqueue(P x){
    Q[tail] = x;
    tail = (tail + 1) % LEN;
}

P dequeue(){
    P x = Q[head];
    head = (head + 1) % LEN;
    return x;
}

int min(int a, int b){ return a < b ? a: b; }

int main(void){
    // Your code here!
    int elaps = 0, c;
    int i, q;
    P u;
    scanf("%d %d", &n, &q);
    for(i = 1; i <= n; i++){
        scanf("%s", Q[i].name);
        scanf("%d", &Q[i].t);
    }
    head = 1; tail = n + 1;
    
    while(head != tail){
        u = dequeue();
        c = min(q, u.t);
        u.t -= c;
        elaps += c;
        if(u.t > 0) enqueue(u);
        else{
            printf("%s %d\n", u.name, elaps);
        }
    }
    
    return 0;
}



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

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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int x;
  cin >> x;
  
  while(!isPrime(x)) x++;
  
  cout << x << '\n';
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define mod 1000000007
#define MAX 1000000000000000
#define all(v) v.begin(),v.end()
#define rep(i,a,b) for(i=(ll)a;i<(ll)b;i++)
#define revrep(i,a,b) for(i=(ll)a;i>=(ll)b;i--)
#define ii pair<ll,ll>
#define MP make_pair
#define pb push_back
#define f first
#define se second
#define ll long long int
#define vi vector<ll>
ll modexp(ll a,ll b){ ll res = 1; while(b > 0){  if(b & 1) res = (res * a)%mod;  a = (a * a)%mod;  b/=2;  }  return res; }
#define rs resize
typedef tree< ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update > OST;
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <typename Arg1>
    void __f(const char* name, Arg1&& arg1){
        cout << name << " : " << arg1 << endl;
    }
    template <typename Arg1, typename... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args){
        const char* comma = strchr(names + 1, ','); cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
    }
#else
#define trace(...)
#endif

const ll N = 10009,M = 402;
ll n,h,w;
int main()
{
    std::ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin>>n>>h>>w;
    cout<<(n - h + 1) * (n - w + 1);
    return 0;
}

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

int main(){
	int N;
	cin >> N;
	vector<string> s(N);
	vector<int> t(N);
	for(int i=0;i<N;i++)	cin >> s.at(i) >> t.at(i);
	string X;
	cin >> X;

	int ans=0;
	for(int i=N-1;i>=0;i--){
		if(s.at(i)==X)	break;
		ans+=t.at(i);
	}
	cout << ans << endl;

	return 0;
}


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

using namespace std;

using ll = long long;
using ld = long double;
using P = pair<int, int>;
constexpr int inf = numeric_limits<int>::max() / 2;
constexpr int mod = 998244353;

template <typename T>
void printv(const vector<T> &v) {
  int sz = v.size();
  for (int i = 0; i < sz; i++) {
    cout << v[i] << " \n"[i == sz - 1];
  }
}

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

  int n;
  cin >> n;
  const int MAX_N = 100010;
  vector<ll> cnt(MAX_N, 0), d(n);
  for (int i = 0; i < n; i++) {
    cin >> d[i];
    cnt[d[i]]++;
  }
  if (d[0] != 0) {
    cout << 0 << endl;
    return 0;
  }
  if (cnt[0] != 1) {
    cout << 0 << endl;
    return 0;
  }
  ll ret = 1;
  for (int i = 1; i <= n - 1; i++) {
    if (cnt[i] == 0) continue;
    if (cnt[i - 1] == 0) {
      ret = 0;
      break;
    }
    for (int j = 0; j < cnt[i]; j++) {
      ret = ret * cnt[i - 1] % mod;
    }
  }
  cout << ret << endl;
}


Measured memory_bytes: 1792
#include <stdio.h>
#include <iostream>
#include <string>
//#include <cmath>
#include <vector>
// #include <algorithm>
// #include <bits/stdc++.h>
using namespace std;

int main() {
  string T, S;
  cin >> T >> S;

  if (T == S.substr(0, T.length())) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  
  return 0;
}


Measured memory_bytes: 3628
# Q4
import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
from functools import lru_cache

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

N = I()
C = S()

rest_R = C.count("R")
index = 0
operation = 0

while True:
    if rest_R == 0:
        break
    current = C[index]
    if current == "R":
        rest_R -= 1
        index += 1
    else:
        operation += 1
        rest_R -= 1
        index += 1

print(operation)

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

using namespace std;

int main() {
#ifndef ONLINE_JUDGE
    //freopen("input.txt", "r", stdin);
#endif

    int n, l;
    scanf("%d %d", &n, &l);
    int pie = 0;
    for(int i=0; i <n; i++)
        pie += l + i;

    
    int res = -1e9;
    for(int i=0; i<n; i++){
        int npie = pie - (l + i);
        if(abs(pie - npie) < abs(pie - res)){
            res = npie;
        }
    }
    printf("%d\n", res);
    return 0;
}

Measured memory_bytes: 256
from collections import deque

N = int(input())
L = []
dic = {}
E = [[] for _ in range(N)]
e = [0]*(N)
for i in range(N-1):
    a,b = map(int, input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
    e[a-1] += 1
    e[b-1] += 1
    L.append((a-1, b-1))
    
K = max(e)
print(K)

q = deque()
q.append((0, -1))
used = [0]*N
used[0] = 1
while q:
    t = q.popleft()
    num = 1
    for v in E[t[0]]:
        if used[v] == 0:
            used[v] = 1
            q.append((v, (t[1]+num)%K))
            if t[0] < v:
                dic[(t[0], v)] = (t[1]+num)%K+1
            else:
                dic[(v, t[0])] = (t[1]+num)%K+1
            num += 1
                
for i in range(N-1):
    print(dic[L[i]])

Measured memory_bytes: 91424
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef vector<ll> VLL;
typedef vector<vector<ll>> VVLL;
typedef pair<ll, ll> Pair;
template <class T> T input() {T t; cin>>t; return t;}
#define FOR(i,a,b) for (ll i = a; i < b; i++)
#define REP(i,b) FOR(i,0,b)
#define RFOR(i,a,b) for (ll i = a-1; i >= b; i--)
#define RREP(i,a) RFOR(i,a,0)
#define REPALL(i,x) for (ll i = 0; i < x.size(); i++)
#define RREPALL(i,x) for (ll i = x.size()-1; i >= 0; i--)
#define REPITR(itr,x) for (auto itr = (x).begin(); itr != (x).end(); itr++)
#define ALL(x) (x).begin(), (x).end()
#define SORT(x) sort(ALL(x))
#define MIN_ELEMENT(x) min_element(ALL(x))
#define MAX_ELEMENT(x) max_element(ALL(x))
#define COUNT(x,num) count(ALL(x), num)
#define MEMSET(x,val) memset(x, val, sizeof(x))
#define CHMAX(a,b) a = max(a,b)
#define CHMIN(a,b) a = min(a,b)
#define FIND(x,key) x.find(key) != x.end()
#define IN_RANGE_V2(v,k,x,y) (0<=x+dx[k]&&x+dx[k]<v[y].size()&&0<=y+dy[k]&&y+dy[k]<v.size())
#define debug(x) cerr<<__LINE__<<": "<<(#x)<<" = "<<(x)<<endl;
void YES(bool flag) {cout<<(flag ? "YES" : "NO")<<endl;}
void Yes(bool flag) {cout<<(flag ? "Yes" : "No")<<endl;}
void yes(bool flag) {cout<<(flag ? "yes" : "no")<<endl;}
#define PRINT_ARRAY_H(a) REPALL(__i,a) {cout<<a[__i]<<(__i != a.size()-1 ? " " : "");} newline;
#define PRINT_ARRAY_V(a) REPALL(__i,a) {cout<<a[__i]<<endl;}
#define e1 first
#define e2 second
#define newline putchar('\n')
#define cspace ' '
#define sspace " "
const int INF = 1e7;
const ll MOD = 1e9 + 7;
const double pi = 3.141592653589793;
const VI dx = {1, 0, -1, 0};
const VI dy = {0, 1, 0, -1};
//const VI dx = {1, 1, 0, -1, -1, -1, 0, 1};
//const VI dy = {0, 1, 1, 1, 0, -1, -1, -1};

void solve()
{
    ll a, b, c, d, n, m, l, r, k, x, y, z, ans = 0ll;
    string s, t;
    cin>>n;
    l = 0, r = n;
    ll mid = (l + r) / 2;;
    string s0;
    cout<<0<<endl;
    cin>>s0;
    if (s0 == "Vacant") {
        return;
    }

    while (true) {
        mid = (l + r) / 2;
        cout<<mid<<endl;
        cin>>s;
        
        if (s == "Vacant") {
            break;
        } else if (s == s0) {
            if (l % 2 == mid % 2) {
                l = mid;
                s0 = s;
            } else {
                r = mid;
            }
        } else {
            if (l % 2 == mid % 2) {
                r = mid;
            } else {
                l = mid;
                s0 = s;
            }
        }
    }
}

int main()
{
    cout<<fixed<<setprecision(20);
    int __t = 1;
    //cin>>__t;
    REP(i,__t) {
        solve();
    }
    return 0;
}

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

using namespace std;

typedef long long ll;

#define sz(x) ((int)(x).size())
#define in(x) int x;cin>>x
#define bit(n) (1<<(n))

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

int main(){
	char b, c;
	cin >> b;
	if(b == 'A')
		c = 'T';

	if(b == 'T')
		c = 'A';

	if(b == 'C')
		c = 'G';

	if(b == 'G')
		c = 'C';


	cout << c << endl;

	return 0;
}


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

#define int long long

using namespace std;

signed main()
{
    int N;
    
    cin >> N;
  
  	int A[N];

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

    sort(A, A + N);

    int b = A[N / 2];

    int ans = 0;

    for (int i = 0; i < N; i++) { ans += abs(A[i] - b); }
    cout << ans << endl;

    return 0;
}

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

int main(){
  string s;
  cin >> s;
  for(int i=0;i<s.size();i++){
    if(s.at(i)==','){
      s.at(i)=' ';
    }
  }
  cout << s << endl;
  return 0;
}


Measured memory_bytes: 256
import numpy as np
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect

MAX_LIM = 10**9
N = (input())
keta = len(N)
N = int(N)

# print(pow(3, 9))
keta_lis = {1: [3, 5, 7], 2: [], 3: [],
            4: [], 5: [], 6: [], 7: [], 8: [], 9: []}
for i in range(1, keta):
    times = pow(10, i)
    for tmp in keta_lis[i]:
        for num in [3, 5, 7]:
            keta_lis[i+1].append(tmp + times*num)
ans = []
for keta in keta_lis.keys():
    ans.extend(keta_lis[keta])
ans = np.array(sorted(ans))
ans = ans[357 <= ans]
ans = ans[ans <= N]
count = 0
for ans_ in ans:
    if (('3' in str(ans_)) and ('5' in str(ans_)) and ('7' in str(ans_))):
        # print(ans_)
        count += 1
print(count)

# print(ans[357 <= ans])


Measured memory_bytes: 13928
#include <bits/stdc++.h>
using namespace std;
#define repr(i, a, b) for (int i = a; i < b; i++)
#define rep(i, n) for (int i = 0; i < n; i++)
typedef long long ll;
#define mod 1000000007

ll gcd(ll x,ll y) {return y ? gcd(y,x%y) : x;} 
ll lcm(ll x,ll y) {return x/gcd(x,y)*y;}


int main(){
    int x,n;
    cin >> x >> n;
    vector<int> a(n);
    bool flag=false;
    rep(i,n){
        cin >>a[i];
        if(a[i]==x) flag=true;
    } 
    
    if(!flag){
        cout << x << endl;
        return 0;
    }
    
    
    int now=1;
    while(1){
        flag=false;
        for(int i=0;i<n;i++){
            if(x-now==a[i]){
                flag=true;
            }
        }
        if(!flag){
            cout << x-now << endl;
            return 0;
        }
        
        
        flag=false;
        for(int i=0;i<n;i++){
            if(x+now==a[i]){
                flag=true;
            }
        }
        if(!flag){
            cout << x+now << endl;
            return 0;
        }
        now++;
    }

    return 0;
}











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

typedef long long int ll;

int main()
{
	ios::sync_with_stdio(0);
	ll n,m;
	cin >> n >> m;
	ll mo = 1e9+7;
	char a[n][m];
	ll i,j;
	for(i=0;i<n;i++)
	{
		for(j=0;j<m;j++)
			cin >> a[i][j];
	}	
	ll dp[n][m];
	for(i=0;i<m;i++)
	{
		if(a[0][i]=='.')
			dp[0][i]=1;
		else
		{
			while(i<m)
			{
				dp[0][i++]=0;
			}
		}
	}
	for(i=0;i<n;i++)
	{
		if(a[i][0]=='.')
			dp[i][0]=1;
		else
		{
			while(i<n)
			{
				dp[i++][0]=0;
			}
		}
	}
	for(i=1;i<n;i++)
	{
		for(j=1;j<m;j++)
		{
			if(a[i][j]=='.')
			{
				dp[i][j] = (dp[i-1][j]%mo+dp[i][j-1]%mo)%mo;
			}
			else
				dp[i][j]=0;
		}
	}
	cout << dp[n-1][m-1] << "\n";
	return 0;
}

Measured memory_bytes: 9088
N, M = map(int, input().split())
like = [0 for i in range(M+1)]
for i in range(N):
    A = list(map(int, input().split()))
    for j in range(A[0]):
        like[A[j+1]] += 1
ans = 0
for i in range(M):
    if like[i+1] == N:
        ans += 1
print(ans)


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

using namespace std;
typedef long long int ll;

ll arr[1000006];
int main()
{
    ll k,n;
    cin>>k>>n;
    for(ll i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    sort(arr,arr+n);
    ll ans=0;
    for(ll i=1;i<n;i++)
    {
        ans=max(ans,(arr[i]-arr[i-1]));
    }
    ans=max(ans,(k-arr[n-1]+arr[0]));
    cout<<k-ans<<endl;

    return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <utility>
using namespace std;

void maxHeapify(vector<int>& heap, int i)
{
    while (i <= (heap.size() - 1) / 2) {
        int largest = i;
        if (heap[largest] < heap[i * 2]) {
            largest = i * 2;
        }
        if (i * 2 + 1 < heap.size() && heap[largest] < heap[i * 2 + 1]) {
            largest = i * 2 + 1;
        }
        if (largest != i) {
            swap(heap[i], heap[largest]);
        } else {
            break;
        }
        i = largest;
    }
}

void insert(vector<int>& heap, int key)
{
    heap.push_back(key);
    int i = heap.size() - 1;
    while (i > 1) {
        int p = i / 2;
        if (heap[p] < heap[i]) {
            swap(heap[p], heap[i]);
        } else {
            break;
        }
        i = p;
    }
}

int extract(vector<int>& heap)
{
    int key = heap[1];
    heap[1] = heap[heap.size() - 1];
    heap.resize(heap.size() - 1);
    maxHeapify(heap, 1);
    return key;
}

int main()
{
    vector<int> heap(1);

    // Input
    string s;
    int key;
    while (true) {
        cin >> s;
        if (s == "insert") {
            cin >> key;
            insert(heap, key);
        } else if (s == "extract") {
            cout << extract(heap) << endl;
        } else if (s == "end") {
            break;
        }
    }
    return 0;
}


Measured memory_bytes: 7040
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#pragma warning(disable : 4996) //_CRT_SECURE_NO_WARNINGS

int main(void) {
	double a, b;/*消費税(円)*/
	double i = 0;
	int res = 0;
	scanf("%lf%lf", &a, &b);
	for (;;i++) {
		if ((int)(i * 0.08) == a && (int)(i * 0.1) == b) {
			res = 1;
			break;
		}
		if ((int)(i * 0.08) > a || (int)(i * 0.1) > b) {
			break;
		}
	}
	if (res == 1) printf("%d", (int)i);
	if (res == 0) printf("%d", -1);
	return 0;
}

Measured memory_bytes: 128
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		while(true){
			int dataNum = Integer.parseInt(br.readLine());
			if(dataNum == 0) break;
			
			int[] nums = new int[dataNum];
			
			for(int i = 0 ; i < dataNum ; i++){
				nums[i] = Integer.parseInt(br.readLine());
			}
			
			Arrays.sort(nums);
			
			long totalWaitTime = 0;
			long beforWaitTime = 0;
			for(int i = 0 ; i < dataNum - 1 ; i++){
				totalWaitTime += beforWaitTime + nums[i];
				beforWaitTime += nums[i];
			}
			System.out.println(totalWaitTime);
		}
	}

}

Measured memory_bytes: 29228
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <string.h>
using namespace std;

const int nmax=40, abmax=10, inf = 1000000;
int a[nmax], b[nmax], c[nmax];
int dp[nmax+1][nmax*abmax+1][nmax*abmax+1];

int main(){
  int n,ma,mb;
  cin >> n >> ma >> mb;
  for(int i=0;i<n;++i){
    cin >> a[i] >> b[i] >> c[i];
  }

  for(int i = 0; i <= n; ++i){
    for(int ca = 0; ca <= nmax*abmax; ++ca){
      for(int cb = 0; cb <= nmax*abmax; ++cb){
       dp[i][ca][cb]=inf;
      }
    }
  }

  dp[0][0][0]=0;
  for(int i = 0; i < n; ++i){
    for(int ca = 0; ca <= nmax*abmax; ++ca){
      for(int cb = 0; cb <= nmax*abmax; ++cb){
      if(dp[i][ca][cb]==inf) continue;
        dp[i+1][ca][cb]=min(dp[i+1][ca][cb],dp[i][ca][cb]);
        dp[i+1][ca+a[i]][cb+b[i]]=min(dp[i+1][ca+a[i]][cb+b[i]],dp[i][ca][cb]+c[i]);
      }
    }
  }

  int ans=inf;
  for(int ca = 1; ca <= nmax*abmax; ++ca){
    for(int cb = 1; cb <= nmax*abmax; ++cb){
      if(ca*mb==cb*ma) ans=min(ans,dp[n][ca][cb]);
    }
  }

  if(ans==inf) ans=-1;
  cout << ans << endl;
}

Measured memory_bytes: 25984
#!/usr/bin/env python3

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, a, b = map(int, input().split())

MOD = 10**9 + 7
# 二項展開より 2**n - 1 - nCa - nCb を MOD 10**9 + 7 で求めればよい


def combination(n, a):
    # nCk = n! / k! (n-k)! のうち、 n!/(n-k)! を計算する
    res = 1
    div = 1
    for i in range(a):
        res *= n-i
        res %= MOD
        div *= a - i
        div %= MOD

    # print(f'n {n}, a {a}, res {res}, div {div}')
    res = (res * pow(div, MOD-2, MOD)) % MOD
    return res


count = (pow(2, n, MOD) - 1 - combination(n, a) - combination(n, b)) % MOD
print(count)


Measured memory_bytes: 9104
loop {
    s, type = gets.chomp.split
    break if type == ?X
    a = s.split(/_|(?=[A-Z])/).map(&:downcase)
    case type
    when ?L
        puts a[0] + a[1..a.size-1].map(&:capitalize).join
    when ?U
        puts a.map(&:capitalize).join
    when ?D
        puts a.join("_")
    end 
}

Measured memory_bytes: 8648
from itertools import accumulate
from collections import Counter

N, P = map(int, input().split())
S = list(map(int, list(input())))

if P == 2 or P == 5:
    s_can = [1 if i % P == 0 else 0 for i in S]
    # s_cant = [0 if i == 1 else 0 for i in s_can]
    # s_acc = list(accumulate(s_can[::-1]))[::-1]
    answer = 0
    for idx, i in enumerate(s_can[::-1]):
        if i:
            answer += N - idx
    print(answer)
else:
    s = []
    t = 1
    for i in S[::-1]:
        r = i % P
        s.append(r * t % P)
        t = t * 10 % P

    s = list(accumulate([0] + s))
    s = [i % P for i in s]
    c = Counter(s)
    answer = 0
    for i in c.values():
        answer += i * (i - 1) // 2

    print(answer)


Measured memory_bytes: 23540
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
a = LIST()

lim = 3001
dp = [[0]*lim for _ in range(lim)]
cnt = 0
for i in range(1, N+1):
	for l in range(N-i+1):
		cnt += 1
		r = l+i
		if (N-i)%2: #後手
			dp[l][r] = min(dp[l+1][r]-a[l], dp[l][r-1]-a[r-1])
		else: #先手
			dp[l][r] = max(dp[l+1][r]+a[l], dp[l][r-1]+a[r-1])

print(dp[0][N])


Measured memory_bytes: 149740
<?php
fscanf(STDIN, '%s', $tap_s);
$splited_tap_s = str_split($tap_s);

$odd_tap = ['R', 'U', 'D'];
$even_tap = ['L', 'U', 'D'];

foreach ($splited_tap_s as $key => $tap) {
  if ($key % 2 == 0) {
    $searched_tap = array_search($tap, $odd_tap);
  } else {
    $searched_tap = array_search($tap, $even_tap);
  }
  if ($searched_tap === false) {
    echo 'No';
    exit;
  }
}
echo 'Yes';

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

int main() {
  int n, k, x, y;
  cin >> n >> k >> x >> y;
  
  int sum = 0;
  for (int i=1; i<=n; i++) {
    if (i<=k) sum += x;
    else sum += y;
  }
  cout << sum << endl;
  return 0;
}

Measured memory_bytes: 3628
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.sum = [1] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.sum[y] += self.sum[x]
        else:
            self.par[y] = x
            self.sum[x] += self.sum[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


N, M = map(int,input().split())
A = [0] * M
B = [0] * M

uni = UnionFind(N)

for i in range(M):
    A[i], B[i] = map(int,input().split())
    uni.union(A[i],B[i])


print(max(uni.sum))
















"""
N, M = map(int, input().split())

par = list(range(N))
rank = [1] * N
size = [1] * N


def find(x):
    if par[x] == x:
        return x
    else:
        return find(par[x])


def unite(x, y):
    x = find(x)
    y = find(y)

    if x == y:
        return
    if rank[x] < rank[y]:
        x, y = y, x
    par[y] = x
    size[x] += size[y]
    if rank[x] == rank[y]:
        rank[x] += 1


for i in range(M):
    a, b = [int(i) - 1 for i in input().split()]
    unite(a, b)

print(max(size))"""



Measured memory_bytes: 29684
#include <bits/stdc++.h>
using namespace std;
#define N 100001
int n,ans;
int a[N];
int main()
{
	scanf("%d",&n);
	int now=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		if(a[i]==i)now++;
		else if(now)ans+=(now+1)/2,now=0;
	}
	if(now)ans+=(now+1)/2;
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 640
MOD=10**9+7
MAXN=4*(10**5)

two_power=[1 for _ in range(MAXN+10)]
for i in range(1, MAXN+10):
    two_power[i]=(two_power[i-1]*2)%MOD

n=int(input())
c=list(map(int, input().split()))
c.sort(reverse=True)
ans=0
x=two_power[2*n-1]
d=two_power[2*n-2]
for i in range(n):
    ans+=(x+i*d)*c[i]
print(ans%MOD)

Measured memory_bytes: 95316
#include "bits/stdc++.h"
using namespace std;

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

    bool flag = false;
    int res = 0;
    for (int i = 0; i < S.size(); i++) {
        if (S.at(i) == '-') {
            if (i == A) {
                flag = true;
            }
            res++;
        }
    }

    if (res == 1 && flag) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
#include <chrono>
#include <random>
#include <tuple>
#include <utility>
#include <fstream>
#include <complex>

const long INF = (1l << 30);
const long LINF = (1l << 60);

int main(){
    double n;
    scanf("%lf", &n);
    for(long i = 0; i <= n; i++){
        double y = (double)i * 1.08;
        if(n <= y && y < n+1){
            //printf("%lf\n", y);
            printf("%ld\n", i);
            return 0;
        }
    }
    printf(":(\n");
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
  long long n,d[100010],k,i,m=1000;
  scanf("%lld",&n);
  for(i=0;i<n;i++)scanf("%lld",&d[i]);
  for(i=1;i<n;i++){
    if(d[i-1]<d[i]){
      k=m/d[i-1];
      m=m-k*d[i-1];
      m+=d[i]*k;
    }
  }
  printf("%lld\n",m);
  return 0;
}
      


Measured memory_bytes: 1744
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
using namespace std;
#define int long long
#define all(arr) arr.begin(),arr.end()
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define vi vector<int>
#define vstr vector<string>
#define vbool vector<bool>
#define vvi vector<vector<int> >
#define mii map<int,int>
#define pb push_back
#define pii pair<int,int>
#define vpair vector<pii > 
#define mkp make_pair
#define scan(a,n) for(int i =0 ; i<n ; i++) cin>>a[i]
#define print(a,n) for(int i = 0 ; i < n ; i++) {cout<<a[i]<<' ';}cout<<'\n'
#define mem(a,v) memset(a,v,sizeof(a))
#define loop(i,a,b) for (int i = a; i < b; i++)
#define loope(i,a,b) for (int i = a; i <= b; i++)
#define FastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define PRECISION std::cout.unsetf ( std::ios::fixed );std::cout.precision(9)
#define PI 3.14159265
#define S second
#define F first
#define CHECK cout<<"CHEDEDWB"<<endl
#define br '\n'
/*int mod = 1e9+7;
int inf = 1e18;
int m_inf = INT_MIN;
int MOD = 100001;*/
#define MAX  100001
int check[MAX] = {0};

void solve()
{
	int n;
	cin>>n;
	int temp;
	int sum = 0;
	loop(i,0,n)
	{
		cin>>temp;
		check[temp]++;
		sum += temp;
	}
	int q;
	cin>>q;
	int b,c;
	while(q--)
	{
		cin>>b>>c;
		sum -= b*check[b];
		sum += c*check[b];
		if(check[b])
		{
			check[c] += check[b];
			check[b] = 0;
		}
		cout<<sum<<endl;
	}
}

int32_t main()
{
	FastIO; PRECISION;
	int t = 1;
	//cin>>t;
	while(t--)
		solve();
	return 0;
}

Measured memory_bytes: 3940
n,k = map(int,input().split())

max_k = (n-1)*(n-2)//2
if(max_k < k):
    print(-1)
    exit()

m = (n-1) + (max_k - k)
print(m)

for i in range(2,n+1):
    print(' '.join(map(str,[1,i])))

now = max_k
for i in range(2,n):
    for j in range(i+1,n+1):
        if(now == k):
            exit()
        print(' '.join(map(str,[i,j])))
        now -= 1

Measured memory_bytes: 41328
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<array>
#include<vector>
using namespace std;
long conv(int a,int b,int c,int d){return 1000000000L*a+1000000L*b+1000L*c+d;}
long rotate(long a){return a%1000000000L*1000+a/1000000000L;}
bool same(long a,long b)
{
	if(a==b)return true;
	a=rotate(a);
	if(a==b)return true;
	a=rotate(a);
	if(a==b)return true;
	a=rotate(a);
	if(a==b)return true;
	return false;
}
int N;
map<long,array<array<long,15>,4> >M;
int a[400],b[400],c[400],d[400];
map<long,int>COUNT[400];
set<long>S;
main()
{
	cin>>N;
	for(int i=0;i<N;i++)
	{
		cin>>a[i]>>b[i]>>c[i]>>d[i];
		long C=conv(a[i],b[i],c[i],d[i]);
		for(int r=0;r<4;r++)
		{
			COUNT[i][C]++;
			S.insert(C);
			C=rotate(C);
		}
	}
	for(long it:S)
	{
		array<array<long,15>,4>&A=M[it];
		long sum=0;
		int ct[5]={};
		for(int i=0;i<N;i++)
		{
			int c=COUNT[i][it];
			sum+=c;
			ct[c]++;
		}
		for(int j=0;j<5;j++)for(int k=0;k<=j;k++)
		{
			if(j&&ct[j]==0||k&&ct[k]==0)continue;
			ct[j]--;
			ct[k]--;
			A[0][j*(j+1)/2+k]=sum-j-k;
			A[1][j*(j+1)/2+k]=(sum-j-k)*(sum-j-k-1)-ct[2]*2-ct[3]*6-ct[4]*12;
			A[2][j*(j+1)/2+k]=(sum-j-k)*(sum-j-k-1)*(sum-j-k-2)
				-(sum-j-k-2)*ct[2]*6
				-(sum-j-k-3)*ct[3]*3*6-ct[3]*6
				-(sum-j-k-4)*ct[4]*6*6-ct[4]*24;
			A[3][j*(j+1)/2+k]=(sum-j-k)*(sum-j-k-1)*(sum-j-k-2)*(sum-j-k-3)
				-(sum-j-k-2)*(sum-j-k-2-1)/2*ct[2]*24
				-(sum-j-k-3)*(sum-j-k-3-1)/2*ct[3]*3*24-(sum-j-k-3)*ct[3]*24
				-(sum-j-k-4)*(sum-j-k-4-1)/2*ct[4]*6*24-(sum-j-k-4)*ct[4]*4*24-ct[4]*24
				+ct[2]*(ct[2]-1)/2*24
				+ct[2]*ct[3]*3*24
				+ct[2]*ct[4]*6*24
				+ct[3]*3*(ct[3]-1)*3/2*24
				+ct[3]*3*ct[4]*6*24
				+ct[4]*6*(ct[4]-1)*6/2*24;
			ct[j]++;
			ct[k]++;
		}
	}
	long ans=0;
	for(int i=0;i<N;i++)
	{
		for(int j=i+1;j<N;j++)
		{
			for(int ccc=0;ccc<4;ccc++)
			{
				int tmp=a[j];
				a[j]=b[j];
				b[j]=c[j];
				c[j]=d[j];
				d[j]=tmp;
				long t[4]={
					conv(b[i],a[i],b[j],a[j]),
					conv(a[i],d[i],c[j],b[j]),
					conv(d[i],c[i],d[j],c[j]),
					conv(c[i],b[i],a[j],d[j]),
				};
				int cc[4]={1,1,1,1};
				for(int I=0;I<4;I++)for(int J=I+1;J<4;J++)
				{
					if(cc[J]==0)continue;
					if(same(t[I],t[J]))cc[I]+=cc[J],cc[J]=0;
				}
				long now=1;
				for(int k=0;k<4;k++)
				{
					if(cc[k]==0)continue;
					int a=COUNT[i][t[k]];
					int b=COUNT[j][t[k]];
					if(a<b)a^=b^=a^=b;
					now*=M.find(t[k])==M.end()?0:M[t[k]][cc[k]-1][a*(a+1)/2+b];
				}
				ans+=now;
			}
		}
	}
	cout<<ans/3<<endl;
}

Measured memory_bytes: 200832