akhauriyash/Code-Regression huggingface dataset:
typedef long long ll;
#include <bits/stdc++.h>
using namespace std;
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

bool pairCompare(const pair<string,ll>& firstElof, const pair<string,ll>& secondElof)
{
    if(firstElof.first != secondElof.first){
        return firstElof.first < secondElof.first;
    }else{
        return firstElof.second >= secondElof.second;
    }
    
}
 

int main(){
    ll n;
    std::map<pair<string,ll>, ll> m;
    pair<string,ll> sp[110];
    std::cin >> n;
    for (int i = 0; i < n; i++) {
        string s;
        ll p;
        std::cin >> s>>p;
        m[{s,p}] = i+1;
        sp[i] = {s,p};
    }
    sort(sp,sp+n,pairCompare);
    for (int i = 0; i < n; i++) {
        std::cout << m[{sp[i]}] << std::endl;
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

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

    vector<long long> vec[3];

    for(int i=0; i < N; i++) {
        for(int j=0; j < 3; j++) {
            long long num; cin >> num;
            vec[j].push_back(num);
        }
    }

    long long ans = 0;

    for(int bit=0; bit < (1<<3); bit++) {
        vector<long long> b;
        for(int i=0; i < N; i++) {
            long long tmp = 0;
            for(int j=0; j < 3; j++) {
                if(bit & (1<<j)) tmp += vec[j][i];
                else tmp -= vec[j][i];
            }
            b.push_back(tmp);
        }
        sort(b.begin(), b.end(), greater<long long>());
        long long sum = 0;
        for (int i=0; i < M; i++) {
            sum += b[i];
        }
        ans = max(ans, sum);
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
   int c[200005];
int main()
{
    int n,k,i,nn;

    cin>>n;
   nn=n;
    n=n-1;

    while(n--)
    {
        cin>>k;
        c[k]++;
    }
    for(i=1;i<=nn;i++)
        cout<<c[i]<<endl;
}



Measured memory_bytes: 4344
n=int(input())
s=input()
list=["" for _ in range(1000)]
ans=0
for i in range(1000):
  t=str(i)
  u="0"*(3-len(t))+t
  j=0
  exi=0
  p=u[0]
  for x in s:
    if x==p:
      j+=1
      if j==3:
        ans+=1
        break
      p=u[j]
    
print(ans)


Measured memory_bytes: 3064
#include<iostream>
#include<vector>
#define lli long long int
#include<climits>
#include<unordered_map>
#include<algorithm>
#include<bitset>
#include<map>
#define pb push_back
using namespace std;

int main()
{
    lli n;
    cin>>n;
    if(n<2 or n%2!=0)
    {
        cout<<0<<endl;
        return 0;
    }
    n = n/2;
    lli count = 0;
    lli t = 5;
    while(1)
    {
        if(n/t<1) break;
        count = count + n/t;
        t = t * 5;
    }
    
    cout<<count<<endl;
   
}


Measured memory_bytes: 3596
from bisect import bisect_left
import random
import time
import math

time_s = time.perf_counter()

#入力
D = int(input())
C = [int(c) for c in input().split()]
S = []
for _ in range(D):
    s = [int(x) for x in input().split()]
    S.append(s)
#初期解
T = []
for _ in range(D):
    t = random.randrange(26)
    T.append(t)


last_day = [[-1] for _ in range(26)]
for d in range(D):
    test = T[d]
    last_day[test].append(d)
for i in range(26):
    last_day[i].append(D)


T0 = 4000
time_start = time.perf_counter()
time_limit = 1.835 - (time_start - time_s)
while True:
    time_now = time.perf_counter()
    if time_now - time_start > time_limit:
        break
    #時間を正規化して温度を設定
    time_n = (time_now - time_start) / time_limit
    T1 = T0 ** (1 - time_n)
    #ランダムな日のテストをランダムに入れ替え
    d = random.randrange(365)
    q = random.randrange(26)
    old = T[d]
    T[d] = q
    #日程dでの元のテストold
    l = last_day[old]
    ind_old = l.index(d)
    dd_left = l[ind_old] - l[ind_old-1] - 1
    dd_right = l[ind_old+1] - l[ind_old] - 1
    dd = l[ind_old+1] - l[ind_old-1] - 1
    dif_old = C[old] * (((dd_left * (dd_left + 1)) // 2) + ((dd_right * (dd_right + 1)) // 2) - ((dd * (dd + 1)) // 2))
    #日程dでのテストq
    l = last_day[q]
    ind_q = bisect_left(last_day[q],d)
    dd_left = d - l[ind_q-1] - 1
    dd_right = l[ind_q] - d - 1
    dd = l[ind_q] - l[ind_q-1] - 1
    dif_q = C[q] * (((dd * (dd + 1)) // 2) - ((dd_left * (dd_left + 1)) // 2) - ((dd_right * (dd_right + 1)) // 2))
    #変更による差
    dif_s = dif_old + dif_q - S[d][old] + S[d][q]
    if (dif_s > 0) or (math.exp(dif_s / T1) > random.random()):
        del last_day[old][ind_old]
        last_day[q].insert(ind_q,d)
    else:
        T[d] = old
for d in range(365):
    print(T[d] + 1)



Measured memory_bytes: 87984
import sys
from itertools import permutations

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())
    tree = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        tree[a - 1].append(b - 1)
        tree[b - 1].append(a - 1)

    res = 0
    for pattern in permutations(range(n)):
        if pattern[0] == 0:
            for i in range(n - 1):
                if pattern[i + 1] not in tree[pattern[i]]:
                    break
            else:
                res += 1
    print(res)



if __name__ == '__main__':
    resolve()


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


int main(){

  int N;
  scanf("%d",&N);

/*
  char A[];
  scanf("%s",A);
  */

  /*
  int A[N];
  int i;
  for(i=0;i<N;i++){
   scanf("%d",&A[i]);
   }
  */
  int A,B,C;
  long long int D;
  A = 0;
  B = 0;
  C = 0;
  D = 0;
  int i,j,k;
  for(i=1;i<=N;i++){
  for(j=1;j<=N;j++){
  for(k=1;k<=N;k++){
    A=i;
    B=j;
    C=k;
  int r;
  r =1;
  while(r != 0){
  r= A%B;
  A = B;
  if(r!=0){
  B = r;
  }
  }
  r =1;
while(r != 0){
  r= B%C;
  B = C;
  if(r!=0){
  C = r;
  }
  }
  D += C;
  }
  }
  }

  printf("%lld",D);


 return(0);
 }


Measured memory_bytes: 1732
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
from itertools import permutations,  combinations, accumulate
from functools import *
from collections import deque, defaultdict, Counter
from heapq import heapify, heappop, heappush, heappushpop

INF = float('inf')
NIL = - 1

""" Input
S = input().rstrip()
A = list(map(int, input().split()))
A = np.array(input().split(), dtype=np.float64)
D = [int(input()) for _ in range(N)]
AB = [[int(x) for x in input().split()] for _ in range(N)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]
"""

K = int(input())
A, B = map(int, input().split())

flag = False
for i in range(A, B + 1):
    if i % K == 0:
        flag = True
        break

print('OK' if flag else 'NG')



# def main():

# if __name__ == '__main__':
#     main()


Measured memory_bytes: 9580
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.NoSuchElementException;
import java.util.Random;

class Main {
	public static void main(String[] args) {
		new Main().run();
	}
	
	void run() {
		FastScanner sc=new FastScanner();
		PrintWriter pw=new PrintWriter(System.out);
		char[] cs=sc.next().toCharArray();
		for(int i=0;i<cs.length;++i) {
			if(cs[i]=='1')cs[i]='9';
			else if(cs[i]=='9')cs[i]='1';
		}
		pw.println(String.valueOf(cs));
		pw.close();
	}

	
	static void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}

}


class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    public int nextInt() {
    	return Integer.parseInt(next());
    }
    
    public long nextLong() {
    	return Long.parseLong(next());
    }
}

Measured memory_bytes: 21204
Scanf.scanf "%d" (fun k ->
    let calc k =
        let rec loop i cur =
            let cur = cur mod k in
            if cur = 0 then i else loop (i + 1) (cur * 10 + 7)
        in
        loop 1 7
    in
    let ans = if k mod 2 = 0 || k mod 5 = 0 then -1 else calc k in
    Printf.printf "%d\n" ans
)

Measured memory_bytes: 3800
import std.stdio, std.conv, std.string, std.array, std.range, std.algorithm, std.container;
import std.math, std.random, std.bigint, std.datetime, std.format;
void main(string[] args){ if(args.length > 1) if(args[1] == "-debug") DEBUG = 1; solve(); }
void log()(){ writeln(""); } void log(T, A ...)(T t, lazy A a){ if(DEBUG) write(t, " "), log(a); } bool DEBUG = 0; 
string read(){ static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res; }
// ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- //

void solve(){
	int n = read.to!int;
	int cg = read.to!int;
	
	S[] xs;
	foreach(i; 0 .. n) xs ~= S(read.to!int, read.to!int, read.to!int);
	log("xs:", xs);
	
	Q[][int] ql;
	foreach(x; xs){
		if(x.c !in ql) ql[x.c] = [];
		ql[x.c] ~= Q(x.s, 1);
		ql[x.c] ~= Q(x.t, 0);
	}
	log("ql:", ql);
	
	int[] cs = ql.keys;
	foreach(c; cs) ql[c].sort!"a.isLess(b)"();
	log("cs:", cs);
	
	Q[] qs;
	foreach(c; cs){
		bool hasPended;
		Q pended;
		log("c:", c, "ql[c]:", ql[c]);
		foreach(q; ql[c]){
			log("q:", q);
			if(hasPended){
				if(q.time == pended.time){
					hasPended = 0;
					continue;
				}
				else{
					qs ~= pended;
					pended = q, hasPended = 1;
				}
			}
			else pended = q, hasPended = 1;
			log("qs:", qs);
		}
		if(hasPended) qs ~= pended;
		log("qs:", qs);
	}
	qs.sort!"a.isLess(b)"();
	log("qs:", qs);
	
	int worst = 0;
	int temp;
	foreach(q; qs){
		if(q.v == 1) temp += 1;
		else temp -= 1;
		worst = max(worst, temp);
	}
	
	worst.writeln;
}
struct S{
	int s, t;
	int c; 
}
struct Q{
	int time;
	int v; // 0=終了 1=開始
	bool isLess(Q q){
		if(this.time < q.time) return true;
		if(this.time > q.time) return false;
		if(this.v > q.v) return true;
		if(this.v < q.v) return false;
		return false;
	}
}


Measured memory_bytes: 10236
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>

using namespace std;

int main()
{
    int N;
    vector<int> h;// List of height
    vector<int> DP;// Hold DP value for each node

    cin >> N;

    h.resize(N);
    DP.resize(N);
    
    for(int i=0; i<N; i++)
    {
        cin >> h.at(i);
    }

    /////////////////////////
    // Initialize DP table //
    /////////////////////////
    DP.at(0) = 0;
    DP.at(1) = abs(h.at(0) - h.at(1));

    ////////////////////////////////////
    // Fill DP table to the last node //
    ////////////////////////////////////
    for(int inode=2; inode<N; inode++)
    {
        int dp1, dp2;
        dp1 = abs(h.at(inode-2) - h.at(inode)) + DP.at(inode-2);
        dp2 = abs(h.at(inode-1) - h.at(inode)) + DP.at(inode-1);
        DP.at(inode) = min(dp1, dp2);
    }

    cout << DP.at(N-1) << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <vector>
#include <cassert>
using namespace std;
using ll = long long;

ll MOD = 1e9+7;
ll ADD(ll x, ll y) { return (x+y)%MOD; }
ll MUL(ll x, ll y) { return (x*y)%MOD; }
ll POW(ll b, ll e) {
  if(e==0) { return 1LL; }
  else if(e%2==0) {
    return POW(MUL(b,b),e/2);
  } else {
    return MUL(b, POW(b,e-1));
  }
}
ll INV(ll x) { return POW(x,MOD-2); }

// How many strings of length i have a specific string of length j as a subsequence?
ll dp(ll i, ll j) {
  assert(i>=0 && j>=0 && j<=i);
  if(i==j) { return 1LL; }
  if(j==0) {
    // 26**i
    return MUL(26,dp(i-1,j));
  } else {
    return ADD(MUL(25,dp(i-1,j)),dp(i-1,j-1));
  }
}

// How many strings of length |S|+k have S as a subsequence?
int main() {
  vector<ll> F(2e6+1, 0);
  vector<ll> FI(F.size(),0);
  vector<ll> P25(F.size(), 0);
  F[0] = 1;
  P25[0] = 1;
  for(ll i=1; i<F.size(); i++) {
    F[i] = MUL(F[i-1],i);
    P25[i] = MUL(25, P25[i-1]);
  }
  FI[FI.size()-1] = INV(F[F.size()-1]);
  assert(MUL(FI[F.size()-1], F[F.size()-1])==1);
  for(ll i=FI.size()-2; i>=0; i--) {
    FI[i] = MUL(FI[i+1], i+1);
    assert(MUL(FI[i],F[i])==1);
  }

  ll n;
  string S;
  cin >> n >> S;
  n += S.size();
  ll k = S.size();

  ll ans = 0;
  // C[n][k] = DIV(F[n], MUL(F[n-k],F[k]))
  // F[n][k] = C[n][k]*25**(n-k) + C[n][k+1]*25**(n-(k+1))+...
  for(ll i=k; i<=n; i++) {
    ll cnk = MUL(F[n], MUL(FI[n-i], FI[i]));
    ll term = MUL(cnk, P25[n-i]);
    //cerr << "i=" << i << " cnk=" << cnk << " term=" << term << endl;
    ans = ADD(ans, term);
  }
  cout << ans << endl;
  //cout << dp(n,k) << endl;
}


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

int main(){
    int n;
    while(cin >> n, n){
        vector<char> C(n);
        for(int i = 0; i < n; ++i) cin >> C[i];
        vector<int> V(26,0);
        string ans = "TIE";
        bool g = false;
        char a = '?';
        for(int i = 0; i < n; ++i){
            int c = C[i] - 'A';
            ++V[c];

            bool f = true;
            for(int k = 0; k < 26; ++k){
                f = true;
                for(int j = 0; j < 26; ++j){
                    if(j == k) continue;
                    f &= (V[j]+(n-1-i)) < V[k];
                }
                if(f){
                    a = 'A' + k;
                    break;
                }
            }
            if(f){
                g = true;
                ans = to_string(i+1);
                break;
            }
        }
        if(g) cout << a << " ";
        cout << ans << endl;
    }
}



Measured memory_bytes: 3248
int X,Y,T[90][90],r;
int R(int x,int y,int d){
	if(0<=x&&x<X&&0<=y&&y<Y&&T[y][x]){
		T[y][x]=0;
		R(x-1,y,d+1);
		R(x+1,y,d+1);
		R(x,y-1,d+1);
		R(x,y+1,d+1);
		T[y][x]=1;
	}else if(r<d)r=d;
}
main(){
	int i,j;
	for(;scanf("%d%d",&X,&Y),X;printf("%d\n",r)){
		for(j=0;j<Y;j++)for(i=0;i<X;i++)scanf("%d",T[j]+i);
		for(r=j=0;j<Y;j++)for(i=0;i<X;i++)R(i,j,0);
	}
}

Measured memory_bytes: 632
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M = map(int, readline().split())
    vec = [0] * M
    for _ in range(N):
        K, *A = map(int, readline().split())
        for a in A:
            vec[a - 1] += 1

    ans = 0
    for i, v in enumerate(vec, 1):
        if v == N:
            ans += 1

    print(ans)
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 9144
#include <iostream>
#include <vector>

using namespace std;

vector<int> card;
void shuffle(int p, int c) {
	vector<int> buf(c);

	--p;
	for (int i = 0; i < c; ++i) {
		buf[i] = card[p+i];
	}
	for (int i = p-1; i >= 0; --i) {
		card[c+i] = card[i];
	}
	for (int i = 0; i < c; ++i) {
		card[i] = buf[i];
	}
}
void print() {
	for (int i = 0; i < card.size(); ++i) {
		cout << card[i] << " ";
	}
	cout << endl;
}

int main() {
	int n, r;
	while ( cin >> n >> r, n || r ) {
		card.clear();
		card.resize(n);
		for (int i = 0; i < n; ++i) {
			card[i] = i;
		}
		for (int i = 0; i < r; ++i) {
			int p, c; cin >> p >> c;
			shuffle(p, c);
		}
		cout << n-card[0] << endl;
	}
}

Measured memory_bytes: 1200
#include <iostream>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <queue>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

inline int getInt(){ int s; scanf("%d", &s); return s; }

using namespace std;

typedef pair<int, int> data;

int memo[1<<15];
int W;
vector<int> vk;
vector<int> w;
vector<int> wm;
vector<vector<int> > wss;

int nap(int flag){
  if(flag == 0) return 0;
  if(memo[flag]) return memo[flag];

  int ret = 10000;

  for(int i = 1; i < (1 << (int)w.size()); i++){
    if(wm[i] <= W && (i | flag) == flag)
      ret = min(ret, 1 + nap(flag ^ i));
  }

  return memo[flag] = ret;
}


int main(){
  int n = getInt();
  int m = getInt() - 1;
  W = getInt();

  vector<int> k(n);
  int cnt = 0;

  REP(i,n){
    k[i] = getInt();
    if(k[i] != 0 || i == 0){
      vk.push_back(i);
      wss.push_back(vector<int>());
      REP(j,k[i]){
        int ww = getInt();
        if(i != 0){
          wss[wss.size() - 1].push_back(cnt++);
          w.push_back(ww);
        }
      }
    }
  }

  int all = w.size();
  if(all == 0){
    puts("0");
    return 0;
  }

  wm = vector<int>(1<<all);

  REP(i,1<<all) REP(j,all) if(i & (1<<j))
    wm[i] += w[j];

  int ks  = wss.size();

  int ans = vk[ks - 1] - m;
  int flag = 0;
  for(int i = ks - 1; i > 0; i--){
    REP(j,wss[i].size())
      flag |= (1 << wss[i][j]);

    int dist = vk[i] - vk[i - 1];
    ans += dist + (dist + dist) * (nap(flag) - 1);
    // printf("%d => %d (%d)\n", vk[i], vk[i - 1], ans);
  }

  printf("%d\n", ans);

  return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define between(a,x,b) ((a)<=(x)&&(x)<=(b))
using namespace std;

int main(){
  int t, x, y, w, h;
  scanf("%d", &t);
  while(t--){
    scanf("%d%d%d%d", &x, &y, &w, &h);
    w += x; h += y;
    int res = 0, cx, cy, n;
    scanf("%d", &n);
    while(n--){
      scanf("%d%d", &cx, &cy);
      if(between(x, cx, w) && between(y, cy, h)) res++;
    }
    printf("%d\n", res);
  }
  return 0;
}

Measured memory_bytes: 1184
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cstdint>

using namespace std;
using i64 = int64_t;
using i32 = int32_t;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0) 
{ v = vector<T>(n+o); for (size_t i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> void read_n(T a[], size_t n, size_t o = 0)
{ for (size_t i=o; i<n+o; ++i) cin >> a[i]; }
template<class T> T gabs(const T& x) { return max(x, -x); }
#define abs gabs

template<class T, class F = plus<T>>
struct Fenwick {
  i64 n;
  vector<T> c;
  F f;
  Fenwick(i64 n, F f = plus<T>(), T init = T())
    : n(n), c(n + 1, init), f(f) {}
  T sum(i64 i) {
    return i > 0 ? f(sum(i - (i & -i)), c[i]) : T();
  }
  void add(i64 i, i64 x) {
    if (i <= n) {
      c[i] = f(c[i], x);
      add(i + (i & -i), x);
    }
  }
};
template<class T, class F>
Fenwick<T, F> make_fenwick(i64 n, F f, T init = T()) {
  return Fenwick<T, F>(n, f, init);
}

const i64 mod = 1e9 + 7;
i64 n, k;
int main() {
  cin >> n >> k;
  i64 m = sqrt(double(n));
  vector<i64> nums(2 * m + 1), cnts(2 * m + 1, 1), rngs(2 * m + 1);
  for (i64 i = 1; i <= m; ++i) {
    i64 j = 2 * m - i + 1, d = n / i;
    nums[i] = i;
    nums[j] = d;
    rngs[i] = j;
    rngs[j] = i;
  }
  for (i64 i = m + 1; i <= 2 * m; ++i) {
    cnts[i] = nums[i] - nums[i - 1];
  }

  bool dbg = false; //true;
  if (dbg) {
    cerr << "i\tnums\tcnts\trngs\n";
    for (i64 i = 1; i <= 2 * m; ++i)
      cerr << i << '\t' << nums[i] << '\t' 
        << cnts[i] << '\t' << rngs[i] << endl;
  }
  Fenwick<i64> fen(m * 2 + 1);
  for (i64 i = 1; i <= m * 2; ++i) fen.add(i, cnts[i]);
  for (i64 i = 1; i < k; ++i) {
    Fenwick<i64> fen_to(m * 2 + 1);
    for (i64 j = 1; j <= m * 2; ++j) {
      fen_to.add(j, cnts[j] * fen.sum(rngs[j]) % mod);
    }
    fen = fen_to;
  }
  cout << fen.sum(2 * m) % mod << '\n';

  return 0;
}



Measured memory_bytes: 2704
#include <iostream>
#include <vector>
#include <string>
#include <queue>

using namespace std;

typedef pair<int,int> P;

#define INF 1000001

int bfs(vector<vector<char> >& mp, P now, P dist, int H, int W) {
    int len[H][W];

    for(int i=0; i<H; ++i) {
        for(int j=0; j<W; ++j) {
            len[i][j]=INF;
        }
    }

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

    len[now.first][now.second]=0;
    queue<P> que;
    que.push(now);

    while(!que.empty()) {
        P p=que.front(); que.pop();

        if(p==dist) break;

        for(int i=0; i<4; ++i) {
            int ni=p.first+dy[i];
            int nj=p.second+dx[i];

            if(ni>=0 && ni<H && nj>=0 && nj<W && len[ni][nj]==INF && mp[ni][nj]!='X') {
                len[ni][nj]=len[p.first][p.second]+1;
                que.push(P(ni,nj));
            }
        }
    }

    return len[dist.first][dist.second];
}

int main()
{
    int H,W,N;
    int ans=0;

    cin >> H >> W >> N;

    P pos[N]; // first=H, second=W
    vector<vector<char> > mp; // mp[H][W]

    mp.resize(H+2);

    for(int i=0; i<H; ++i) {
        string instr;
        cin >> instr;
        for(int j=0; j<W; ++j) {
            mp[i].push_back(instr[j]);
            if(instr[j]>='0' && instr[j]<='9') pos[instr[j]-'0']=make_pair(i,j);
            if(instr[j]=='S') pos[0]=make_pair(i,j);
        }
    }

    for(int i=0; i<N; ++i) {
        ans+=bfs(mp,pos[i],pos[i+1],H,W);
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 7752
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using static System.Math;
using MethodImplAttribute = System.Runtime.CompilerServices.MethodImplAttribute;
using MethodImplOptions = System.Runtime.CompilerServices.MethodImplOptions;

public static class P
{
    public static void Main()
    {
        string s = Console.ReadLine();
        Console.WriteLine(s[2] == s[3] && s[4] == s[5] ? "Yes" : "No");
    }
}


Measured memory_bytes: 11092
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <bitset>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <utility>
#include <set>
#include <map>
#include <tuple> 
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <list>
using namespace  std;
using ll = long long;
using P = pair<ll, ll>;
#define REP(i, n) for(long long (i)=0, i_bound = (long long)(n); (i)<i_bound; ++i)
#define FOR(i, a, b) for(long long (i)=(a); (i)<(b); ++i)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
const long long MOD = static_cast<long long>(1e9) + 7LL;
const long long INF = 1234567891234567890LL;
int main(){
    cin.tie(0);
    cout.sync_with_stdio(false);
    ll X; cin>>X;
    ll Y = X + 3000;
    vector<int> furui(Y+10, 1);
    for(int i=2; i*i<=Y; i++){
        if(!furui[i]) continue;
        for(int j=2; i*j<=Y; j++){
            furui[i*j] = 0;
        }
    }
    ll res = -1;
    for(int i=X; i<=Y; i++){
        if(furui[i]) {
            res = i;
            break;
        }
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pint;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
template<int MOD> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    constexpr int getmod() { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};

using mint = Fp<1000000007>;
vector<pint> prime_factorize(ll n){
  vector<pint> ans;
  for(ll i=2;i<=sqrt(n);i++){
    if(n%i!=0) continue;
    ll num=0;
    while(n%i==0){
      n/=i;
      num++;
    }
    ans.push_back(make_pair(i,num));
  }
  if(n!=1) ans.push_back(make_pair(n,1));
  return ans;
}

int main(){
  IOS;
  ll n;
  cin>>n;
  vector<ll> v(n);
  vector<ll> num(1100000,0);
  rep(i,n){
    cin>>v[i];
    auto pf=prime_factorize(v[i]);
    for(auto p:pf) num[p.first]=max(num[p.first],p.second);
  }
  mint LCM=1;
  rep(i,1100000){
    LCM*=modpow((mint)i,num[i]);
  }
  mint ans=0;
  rep(i,n){
    ans+=LCM/v[i];
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 8960
#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>

#define ll long long int
#define pb push_back
#define mk make_pair
#define pq priority_queue

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

int main(int argc, char const* argv[])
{
  int n;
  cin >> n;
  vector<int> p;
  vector<int> q = vector<int>(n, 0);
  for(int i = 0; i < n; i++){
    int x;
    cin >> x;
    x--;
    p.pb(x);
    q[x] = i;
  }
  vector<int> vec = vector<int>(n + 1, 0);
  vec[0] = 1;
  int res = 1;
  for(int i = 1; i < n; i++){
    if(q[i - 1] < q[i])vec[i] = vec[i - 1] + 1;
    else vec[i] = 1;
    res = max(res, vec[i]);
  }

  cout << n - res << endl;
	return 0;
}


Measured memory_bytes: 2676
h,w=map(int,input().split())
a=[list(input()) for i in range(h)]

from collections import deque

v=[[0]*w for i in range(h)]
m=[[-1,0],[0,-1],[1,0],[0,1]]
que=deque([])
for i in range(h):
    for  j in range(w):
        if a[i][j]=='#':
            v[i][j]=1
            que.append([i,j,0])
            #print(que)

while len(que)>0:
    n=que.popleft()
    for i in m:
        ni,nj=i[0]+n[0],i[1]+n[1]
        if ni>=0 and nj>=0 and ni<h and nj<w:
            if v[ni][nj]==0:
                v[ni][nj]=1
                que.append([ni,nj,n[2]+1])
print(n[2]) 

Measured memory_bytes: 183900
// AOJ 2069: Greedy, Greedy.
// 2017.11.5 bal4u@uu

#include <stdio.h>
#include <string.h>
#define TM 0
#if TM
#include <time.h>
#endif

int c[52], n;
int dp[2001];

int calcGreedy(int lim)
{
	int p, i, s;
	while (lim--) {
		p = lim, s = 0, i = n;
		while (i--) {
			if (p == c[i]) { s++; break; }
			if (p < c[i]) continue;
			s += p/c[i];
			p %= c[i];
		}
		if (s != dp[lim]) return 0;
	}
	return 1;
}

void calcDP(int lim)
{
	int i, j, k;
	memset(dp, 0x33, sizeof(dp)), dp[0] = 0;
	for (i = 0; i < n; i++) for (j = 0; (k = j + c[i]) <= lim; j++) {
		if (dp[j+c[i]] > dp[j] + 1) dp[j+c[i]] = dp[j] + 1;
	}
}

char buf[302], *p;
int getint()
{
	int n = 0;
	while (*p >= '0') n = (n<<3) + (n<<1) + (*p++ & 0xf);
	return n;
}

int main()
{
	int cno = 0, i, lim;
#if TM
	clock_t start, end;
	start = clock();
#endif
	while (fgets(p=buf, 300, stdin) && *p != '0') {
		printf("Case #%d: ", ++cno);
		n = getint(), p++;
		c[0] = getint(), p++;
		if (c[0] != 1) { puts("Cannot pay some amount"); continue; }
		if (n <= 2) { puts("OK"); continue; }
		for (i = 1; i < n; i++) c[i] = getint(), p++;
		lim = c[n-1] + c[n-2];
		calcDP(lim);
		if (calcGreedy(lim)) puts("OK");
		else puts("Cannot use greedy algorithm");
	}
#if TM
	end = clock();
	printf("time %lf\n", (double)(end-start)/CLOCKS_PER_SEC);
#endif
	return 0;
}

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

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

    int n, l;
    cin >> n >> l;

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

    sort(v.begin(), v.end(), [](string a, string b) {
        return a < b;
    });

    for (int i = 0; i < n; i++)
        cout << v[i];

    cout << '\n';

    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<(n); i++)
#define rep_1(i,n) for(int (i)=0;(i)<=(n);(i)++)
#define rep_2(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

int main()
{

    double L;
    double ans;
    cin >> L ;
    ans =(double)(L / 3)* (double)(L/3)* (double)(L/3);
    printf("%.12f\n",ans);
    return 0;
}

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

int n,X[1000],Y[1000];
inline int _abs(int a) { return a<0 ? -a : a; }

int main() {
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d%d",X+i,Y+i);
    
    int pari=((X[0]+Y[0])%2+2)%2;
    for(int i=0;i<n;i++) if(((X[i]+Y[i])%2+2)%2!=pari) { puts("-1"); return 0;}

    vector<int> vs;
    for(int i=30;i>=0;i--) vs.push_back(1<<i);
    if(pari==0) vs.push_back(1);
    printf("%lu\n",vs.size());
    for(auto &v:vs)printf("%d ",v);
    puts("");
    for(int i=0;i<n;i++) {
        long long x=X[i],y=Y[i];
        for(auto &v:vs) {
            if(_abs(x) > _abs(y)) {
                if(x>0) printf("R"), x-=v;
                else printf("L"), x+=v;
            } else {
                if(y<0) printf("D"), y+=v;
                else printf("U"), y-=v;
            }
        }
        puts("");
    }

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

using u128 = __uint128_t;

#define int long long
#define idxSet tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
#define atIdx find_by_order
#define idxOf order_of_key
#define MOD 1000000007
#define MAX 200005
#define endl '\n'

#define v(type) vector<type>
#define p(type1, type2) pair<type1 , type2>
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

int dp[MAX];

void solve() {
    int sx , sy , tx , ty;
    cin>>sx>>sy>>tx>>ty;
    for(int i = 0 ; i < tx - sx ; i++){
        cout<<"R";
    }
    for (int j = 0; j < ty - sy; ++j) {
        cout<<"U";
    }
    for(int i = 0 ; i < tx - sx ; i++){
        cout<<"L";
    }
    for(int i = 0 ; i < ty - sy ; i++){
        cout<<"D";
    }
    cout<<"L";
    for(int i = 0 ; i <= ty - sy ; i++){
        cout<<"U";
    }
    for(int j = 0 ; j <= tx - sx ; j++){
        cout<<"R";
    }
    cout<<"D";
    cout<<"R";
    for(int i = 0 ; i <= ty - sy ; i++){
        cout<<"D";
    }
    for(int i = 0 ; i <= tx - sx ; i++){
        cout<<"L";
    }
    cout<<"U";

}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    //cin>>t;
    while (t--)
        solve();
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
    public class Main {
     
    	public static void main(String[] args) {
    			
    		Scanner scan=new Scanner(System.in);
    		
    		int x=Integer.parseInt(scan.next());
    		int a=Integer.parseInt(scan.next());
    		int b=Integer.parseInt(scan.next());

    		if(a-b>=0) {
    			System.out.print("delicious");
    		}else if (b-a<=x) {
    			System.out.print("safe");
    		}else {
    			System.out.print("dangerous");
    		}
    		
    	
  
    				
 
     
    }
    }

Measured memory_bytes: 23764
#include <iostream>
#include <string>

int main() {
  int n;
  std::string s, s_shift = "";
  std::cin >> n >> s;
  for (int i = 0; i < s.length(); ++i) {
      s_shift += char(int(s[i]+n-65)%26+65); 
  }
  std::cout << s_shift; 
}

Measured memory_bytes: 3640
n = gets.to_i
a = gets.split.map(&:to_i)
num = [0]*8
r = 0

8.times do |i|
  num[i] = a.count{|j| j>=r && j<r+400}
  r += 400
end

overs = a.count{|j| j>=3200}

ans = num.count{|i| i!=0}
if ans == 0 && overs > 0
  puts "1 #{ans+overs}"
else
  puts "#{ans} #{ans+overs}"
end


Measured memory_bytes: 1788
#include <bits/stdc++.h>
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define ll long long
#define LEFT(a) ((a)<<1)
#define RIGHT(a) (LEFT(a) + 1)
#define MID(a,b) ((a+b)>>1)
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
using namespace std;

const int N = 110000;

int n;
pair < ll, pair < ll, ll > > P[N];
ll ans;

int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++){
        ll x, y;
        cin >> x >> y;
        P[i] = { - x - y, {x, y}};
    }
    sort (P + 1, P + n + 1);
    for (int i = 1; i <= n; i++){
        if (i % 2 == 1)
            ans += P[i].S.F;
        else
            ans -= P[i].S.S;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
template<typename T> inline void chkmin(T &a, const T &b) { a = a < b ? a : b; }
template<typename T> inline void chkmax(T &a, const T &b) { a = a > b ? a : b; }

const int MAXN = 200005;
vector<int> A[MAXN], B[MAXN];
int da[MAXN], db[MAXN], par[MAXN], lab[MAXN], n, X, Y, ans;

void dfs1(int u, int fa) {
	for (int v : A[u]) if (v != fa) {
		da[v] = da[u] + 1;
		dfs1(v, u);
	}
}

void dfs2(int u, int fa) {
	par[u] = fa;
	for (int v : B[u]) if (v != fa) {
		db[v] = db[u] + 1;
		dfs2(v, u);
	}
}

void dfs3(int u, int fa) {
	if (da[u] > db[u]) return;
	chkmax(ans, db[u]);
	if (da[u] == db[u]) return;
	if (lab[u]) { puts("-1"); exit(0); }
	for (int v : A[u]) if (v != fa) dfs3(v, u);
}

int main() {
	scanf("%d%d%d", &n, &X, &Y);
	for (int i = 1; i < n; i++) {
		int u, v; scanf("%d%d", &u, &v);
		A[u].push_back(v), A[v].push_back(u);
	}
	for (int i = 1; i < n; i++) {
		int u, v; scanf("%d%d", &u, &v);
		B[u].push_back(v), B[v].push_back(u);
	}
	dfs1(X, 0);
	dfs2(Y, 0);
	for (int u = 1; u <= n; u++)
	for (int v : A[u]) if (da[v] > da[u]) {
		int a = u, b = v;
		if (db[a] == db[b]) {
			if (par[a] != par[b]) lab[a] = lab[b] = 1;
			continue;
		}
		if (db[a] > db[b]) swap(a, b);
		if (par[b] != a && par[par[b]] != a) lab[a] = lab[b] = 1;
	}
	dfs3(X, 0);
	printf("%d\n", ans * 2);
	return 0;
}

Measured memory_bytes: 33788
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<functional>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
//#define MOD 998244353
#define LINF (long long)4e18
#define jck 3.141592

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;

int main(){
    char c; cin >> c;
    cout << char(c+1) << endl;

}
    



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int v[100005], n;
set<tuple<int, int, int>> st;
char res[100005];
bool dfs(int id, int a, int b, int c) {
  if(st.find({id, a, b}) != st.end()) return true;
  if(id == n) return true;
  if(v[id] == 0) {
    if(b) {
      res[id] = 'A';
      if(dfs(id + 1, a + 1, b - 1, c)) return true;
    }
    if(a) {
      res[id] = 'B';
      if(dfs(id + 1, a - 1, b + 1, c)) return true;
    }
  } else if(v[id] == 1) {
    if(c) {
      res[id] = 'A';
      if(dfs(id + 1, a + 1, b, c - 1)) return true;
    }
    if(a) {
      res[id] = 'C';
      if(dfs(id + 1, a - 1, b, c + 1)) return true;
    }
  } else {
    if(b) {
      res[id] = 'C';
      if(dfs(id + 1, a, b - 1, c + 1)) return true;
    }
    if(c) {
      res[id] = 'B';
      if(dfs(id + 1, a, b + 1, c - 1)) return true;
    }
  }
  st.insert({id, a, b});
  return false;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  int a, b, c; cin >> n >> a >> b >> c;
  for(int i = 0; i < n; i++) {
    string s; cin >> s;
    if(s == "AB") v[i] = 0;
    else if(s == "AC") v[i] = 1;
    else v[i] = 2;
  }
  if(dfs(0, a, b, c)) {
    cout << "Yes\n";
    for(int i = 0; i < n; i++) {
      cout << res[i] << '\n';
    }
  } else {
    cout << "No\n";
  }
}

Measured memory_bytes: 12436
use std::io::stdin;

fn main () {
    let mut nk = String::new();
    stdin().read_line(&mut nk).unwrap();
    let nk: Vec<_> = nk.trim().split_whitespace().map(|it|it.parse().unwrap()).collect();
    resolve(nk[0], nk[1]);
}

fn resolve(n: i64, k:i64) {
    println!("{}", if n % k == 0 { 0 } else { 1 });
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 1000000100
#define LLINF 100000000000000000ll
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define all(x) (x).begin(),(x).end()
#define sq(x) ((x)*(x))
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define repn(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++)
#define EQ(a,b) (abs((a)-(b))<eps)
template<class T> void chmin(T& a,const T& b){if(a>b)a=b;}
template<class T> void chmax(T& a,const T& b){if(a<b)a=b;}
int N,W;
int w[105];
ll v[105];
ll dp[105][100100];
int main(){
	cin >> N >> W;
	for(int i=0;i<N;i++){
		cin >> w[i] >> v[i];
	}
	for(int i=0;i<=N;i++){
		for(int j=0;j<=W;j++){
			dp[i][j]=-INF;
		}
	}
	dp[0][0]=0ll;
	for(int i=0;i<N;i++){
		for(int j=0;j<=W;j++){
			chmax(dp[i+1][j],dp[i][j]);
			if(j>=w[i])chmax(dp[i+1][j],dp[i][j-w[i]]+v[i]);
		}
	}
	ll ans = 0ll;
	for(int i=0;i<=W;i++)chmax(ans,dp[N][i]);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 80128
from collections import deque

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]

graph = [[] for _ in range(n + 1)]
for i in range(m):
    a = ab[i][0]
    b = ab[i][1]
    graph[a].append(b)
    graph[b].append(a)

inf = 100100100
ans = [[inf, inf] for _ in range(n + 1)]
ans[0] = [0, 0]
ans[1] = [0, 0]

q = deque([1])
while q:
    now = q.popleft()
    depth = ans[now][1]
    for x in graph[now]:
        if ans[x][0] == inf:
            q.append(x)
            if ans[x][1] > depth + 1:
                ans[x][0] = now
                ans[x][1] = depth + 1

print('Yes')
for i in range(2, n + 1):
    print(ans[i][0])


Measured memory_bytes: 65776
N = int(input())
L = list(map(int, input().split()))
L.sort(reverse=True)
L_ = []
for i in range(N):
    L_ += [L[i]*(10**3) + (N-i-1)]
# length_list[m] m 以下の長さの辺の個数
length_list = [0] * (10**3 + 1)
for i in range(N):
    length_list[L[i]] += 1
for i in range(10**3):
    length_list[i+1] += length_list[i]

length_list_ = [0] * (2* 10**6 + 1)
for i in range(N):
    length_list_[L_[i]] += 1
for i in range(2* 10**6):
    length_list_[i+1] += length_list_[i]
    
ans = 0
for i in range(N):
    for j in range(i+1,N):
        ans += max(0, length_list_[L_[j]-1] - length_list[(L[i]-L[j])] )
print(ans)

Measured memory_bytes: 78452
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
#define int long long
#define vel vector<long long>
#define vvel vector<vel>
#define vvvel vector<vvel>
void mmin(int &a, int b) { a = min(a, b); }
void mmax(int &a, int b) { a = max(a, b); }
void sor(vel &v) { sort(v.begin(), v.end()); }
int zero() { return 0; }
int gcd(int a, int b) {
	if (a < b) {
		return gcd(b, a);
	}
	if (b == 0) {
		return a;
	}
	int r = a % b;
	return gcd(b, r);
}
signed main() {
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	int dx = abs(a - c);
	int dy = abs(b - d);
	cout << dx + dy - gcd(dx, dy) << endl;
	return 0;
}

Measured memory_bytes: 256
class UnionFind:
    """
    size の要素数の UnionFind を管理する
    data 中の負数の要素が根となる
    """

    def __init__(self, size):
        # 根は子を含む集合のデータ数を負数でもつ
        self.data = [-1] * size

    def merge(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y: return False

        # y の方がデータ数を多く
        if self.data[x] < self.data[y]:
            x, y = y, x

        # y に x をつなげる
        self.data[y] += self.data[x]
        self.data[x] = y
        return True

    def root(self, x):
        if self.data[x] < 0:
            return x
        self.data[x] = self.root(self.data[x])
        return self.data[x]

    def size(self, x):
        """
        根は負数でデータ数を管理しているのでそれを返す
        """
        return -self.data[self.root(x)]

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


N, M = [int(_) for _ in input().split()]
uf = UnionFind(N+10)
P = [int(_) for _ in input().split()]
for i in range(M):
    x, y = [int(_) for _ in input().split()]
    uf.merge(x, y)
cnt = 0
for i, p in enumerate(P):
    cnt += uf.same(i + 1, p)
print(cnt)


Measured memory_bytes: 15220
# -*- coding: utf-8 -*-

'''Snippets for prime.
Available functions:
- is_included: Determine whether it is a prime number.
- generate: Generate a list of prime numbers using sieve of Eratosthenes.
'''


class Prime(object):
    '''Represents a snippet for prime numbers.
    '''

    def __init__(self, number):
        self.number = number
        self._values = []

    def is_included(self) -> bool:
        '''Determine whether it is a prime number.
        Args:
            number: Int of number (greater than 0).
        Returns:
            True if the input number was prime.
            False if the input number was not prime.
        See:
            https://qiita.com/srtk86/items/874639e361917e5016d4
            https://docs.python.org/ja/3/library/2to3.html?highlight=isinstance#2to3fixer-isinstance
        '''

        from math import sqrt

        if (self.number <= 1) or (isinstance(self.number, float)):
            return False

        for i in range(2, int(sqrt(self.number)) + 1):
            if self.number % i == 0:
                return False

        return True

    def generate(self) -> list:
        '''Generate a list of prime numbers using sieve of Eratosthenes.
        Returns:
            A list of prime numbers that is eqaul to or less than the input
            number.
        Landau notation: O(n log log n)
        See:
            https://beta.atcoder.jp/contests/abc110/submissions/3254947
        '''

        if self._values:
            return self._values

        is_met = [True for _ in range(self.number + 1)]
        is_met[0] = False
        is_met[1] = False

        for i in range(2, self.number + 1):
            if is_met[i]:
                self._values.append(i)

                for j in range(2 * i, self.number + 1, i):
                    is_met[j] = False

        return self._values


def main():
    from itertools import accumulate

    q = int(input())
    max_n = 10 ** 5 + 100
    prime = Prime(max_n)
    primes = prime.generate()
    like_numbers = [0 for _ in range(max_n + 1)]

    for current_prime in primes:
        new_prime = Prime((current_prime + 1) // 2)

        if new_prime.is_included():
            like_numbers[current_prime] = 1

    like_number_count = list(accumulate(like_numbers))

    for i in range(q):
        li, ri = map(int, input().split())
        print(like_number_count[ri] - like_number_count[li - 1])


if __name__ == '__main__':
    main()


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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

#define gap ' '
#define L(i) ((i) - (&i))
#define mp make_pair
#define debug puts("WHAP")

const int MAXN = 100;
const int MAX = 1e5;
const int mxn = 1e5;
const int MOD = 1e9+7;
const int INF = 1e9;
const int N = 110000;

int main(){
	string s; cin >> s;
	int ans[N], n = s.length();
	vector<int> v;
	for(int i = 0; i < n-1; ++i){
		if(s[i]=='R' and s[i+1] =='L')
			v.push_back(i+1);
	}
	for(int i = 0; i < n; ++i){
		if(s[i] == 'R'){
			int at = v[lower_bound(v.begin(),v.end(),i)-v.begin()];
			int to = at;
			if((at-i)%2==1)
				to = at-1;
			ans[to]++;
		}
		else{
			int at = v[upper_bound(v.begin(), v.end(),i)-1-v.begin()];
			int to = at-1;
			if((i-at+1)%2==1)
				to = at;
			ans[to]++;
		}
	}
	for(int i = 0; i < n; ++i)
		cout << ans[i] << gap;
	cout << "\n";
	return 0;
}


Measured memory_bytes: 4268
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class t>
using table = vector<vector<t>>;
const ld eps=1e-9;

//// < "d:\d_download\visual studio 2015\projects\programing_contest_c++\debug\a.txt"

int main() {
	while (1) {
		int H, W; cin >> W >> H;
		if (!H)break;
		vector<vector<int>>field(H + 3, vector<int>(W + 2,1));
		for (int i = 0; i < H; ++i) {
			for (int j = 0; j < W; ++j) {
				cin >> field[i][j+1];
			}
		}
		for (int i = H; i < H + 3; ++i) {
			for (int j = 1; j <= W; ++j) {
				field[i][j] = 0;
			}
		}
		vector<vector<long long int>>nums(H + 3, vector<long long int>(W + 2, 0));
		for (int j = 0; j < W + 2; ++j) {
			if (!field[0][j])nums[0][j] = 1;
		}
		long long int ans = 0;
		if (H==1) {
			cout << accumulate(nums[0].begin(), nums[0].end(), 0) << endl;
		}
		else {
			for (int i = 0; i < H - 1; ++i) {
				for (int j = 1; j < W + 1; ++j) {
					for (int dx = -1; dx <= 1; ++dx) {
						const int nextx = j + dx;
						int nexty = i + 1;

						if (field[nexty][nextx] == 1) {

						}
						else if (field[nexty][nextx] == 2) {
							if (!dx) {
								while (1) {
									nexty += 2;
									if (nexty >= H - 1 && field[nexty][nextx] != 1) {
										ans += nums[i][j];
										break;
									}
									else {
										if (field[nexty][nextx] == 1) {
											break;
										}
										else if (field[nexty][nextx] == 0) {

											nums[nexty][nextx] += nums[i][j];
											break;
										}
									}
								}

							}
						}
						else {
							if (nexty >= H - 1)ans += nums[i][j];
							else {
								nums[nexty][nextx] += nums[i][j];
							}
						}
					}

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

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

int main() {
    ll s, c; cin >> s >> c;

    ll Scc = min(s, c/2);
    ll rem = c - 2 * Scc;
    if (rem) Scc += rem /4;

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

Measured memory_bytes: 256