akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
#define pb push_back

const int N = 1<<18;

using namespace std;

int n, m;
ll dp[N];
pll seg[2*N];
vector<pll > ra[N];

void push(int k){
	seg[k].F += seg[k].S;
	if(k<N){
		seg[2*k].S += seg[k].S;
		seg[2*k+1].S += seg[k].S;
	}
	seg[k].S = 0;
}

ll add(int a, int b, int k, int x, int y, ll o){

	if(seg[k].S) push(k);
	if(a>y || b<x) return seg[k].F;
	if(a==x && b==y){
		seg[k].S += o;
		return seg[k].F+o;
	}

	int d = (y-x+1)/2;

	ll lst = add(a, min(b, y-d), 2*k, x, y-d, o);
	ll rst = add(max(a, x+d), b, 2*k+1, x+d, y, o);

	seg[k].F = max(lst, rst);

	return seg[k].F;
}

ll mas(int a, int b, int k, int x, int y){
	
	if(a>y || b<x) return -1e18;
	if(seg[k].S) push(k);
	if(a==x && b==y) return seg[k].F;

	int d = (y-x+1)/2;

	ll lst = mas(a, min(b, y-d), 2*k, x, y-d);
	ll rst = mas(max(a, x+d), b, 2*k+1, x+d, y);

	return max(lst, rst);
}

int main(){

	cin >> n >> m;

	for(int i=0; i<m; i++){
		int l, r, a;
		cin >> l >> r >> a;
		ra[l].pb({r, a});
	}

	for(int i=n; i>0; i--){
		dp[i] = mas(i, n+1, 1, 0, N-1);
		add(i, i, 1, 0, N-1, dp[i]);
		for(pii j : ra[i]) add(i, j.F, 1, 0, N-1, j.S);
	}

	cout << mas(1, n+1, 1, 0, N-1) << endl;

	return 0;
}


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

int main(){
	long long N;
	cin >> N;
	if(N%2==1){
		cout << 0 << endl;
		return 0;
	}
	N/=2;
	long long ans=0;
	for(int k=1;k<=25;k++){
		long long t=1;
		for(int i=0;i<k;i++)t*=5;
		ans+=N/t;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
o = input()
e = input()

O = []
for _ in o:
  O.append(_)
E = []
for _ in e:
  E.append(_)

ans = []

if len(O) == len(E):
  for i in range(len(O)):
    ans.append(O[i])
    ans.append(E[i])
elif len(O) > len(E):
  for j in range(len(E)):
    ans.append(O[j])
    ans.append(E[j])
  ans.append(O[len(O)-1])
print(*ans, sep='')


Measured memory_bytes: 3064
using System;

class AOJ
{
	public static void Main()
	{
		var input = Console.ReadLine().Trim().Split(' ');
		int W = int.Parse(input[0]);
		int H = int.Parse(input[1]);
		int x = int.Parse(input[2]);
		int y = int.Parse(input[3]);
		int r = int.Parse(input[4]);

		if(x - r < 0 || x + r > W){ Console.WriteLine("No"); }
		else if(y - r < 0 || y + r > H){ Console.WriteLine("No"); }
		else{ Console.WriteLine("Yes"); }
	}
}

Measured memory_bytes: 19620
///Bismillahir Rahmanir Rahim
#include "bits/stdc++.h"

#define                           ll                          long long
#define                           int                         ll
#define                           fi                          first
#define                           si                          second
#define                           mp                          make_pair
#define                           pb                          push_back
#define                           pi                          pair<ll,ll>
#define                           clr(x)                      memset(x,0,sizeof(x));
#define                           f(i,l,r)                    for(int i=l;i<=r;i++)
#define                           rf(i,r,l)                   for(int i=r;i>=l;i--)
#define                           done(i)                     cout<<"done = "<<i<<endl;
#define                           show(x,y)                   cout<<x<<" : ";for(auto z:y)cout<<z<<" ";cout<<endl;
#define                           fast                        ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

const ll inf=1e18;
const int mod=1e9+7;
const int M=1000009;
int dp[M][2];
string s;
int sz;
int solve(int pos,int carry)
{
    if(pos==(sz-1))
    {
        if(carry==1)return 1;
        else return 0;
    }
    int &ret=dp[pos][carry];
    if(ret!=(-1))return ret;
    ret=inf;
    int x=s[pos]-'0';
    int cost;
    if(carry==1)
    {
         int niche=x+1;
         for(int i=niche;i<=9;i++)
         {
               cost=i+(i-niche)+solve(pos+1,0);
               ret=min(ret,cost);
         }
         for(int i=0;i<niche;i++)
         {
             cost=solve(pos+1,1)+i+(i+10-niche);
             ret=min(ret,cost);
         }
    }
    else
    {
         int niche=x;
          for(int i=niche;i<=9;i++)
         {
               cost=i+(i-niche)+solve(pos+1,0);
               ret=min(ret,cost);
         }
         for(int i=0;i<niche;i++)
         {
             cost=solve(pos+1,1)+i+(i+10-niche);
             ret=min(ret,cost);
         }
    }
    return ret;
}
 main()

{
    fast
    memset(dp,-1,sizeof dp);
    cin>>s;
    reverse(s.begin(),s.end());
    s+="0";
    sz=s.size();
    int ses=solve(0,0);
    cout<<ses<<endl;
    return 0;

}





































Measured memory_bytes: 113532
#include <stdio.h>
#include <stdlib.h>
#define MAX 100000

int partition(int *A,int p,int r);

int main(){
  int n,i,q;
  int *A;

  scanf("%d", &n);

  A =(int *)malloc(sizeof(int)*n);

  for ( i = 0; i < n; i++ ){
    scanf("%d", &A[i]);
  }
  
  q = partition(A,0,n-1);

  for ( i = 0; i < n; i++ ){
    if(i==q){
      printf("[%d] ",A[i]);
      continue;
    }
    if(i==n-1)  printf("%d\n",A[i]);
    else printf("%d ", A[i]);
  }
  return 0;
}

int partition(int *A,int p,int r){
  int x,i,j,a;  
  x = A[r];
 
  i = p-1;
  for (j = p; j <= r-1; j++){
  
    if (A[j] <= x){

      i = i+1;

      a = A[i];
      A[i] = A[j];
      A[j] = a;
    }
  }
  a = A[i+1];
  A[i+1] = A[r];
  A[r] = a;
  return i+1;
}

Measured memory_bytes: 992
s = input()

substring = set(['A', 'C', 'G', 'T'])

MAX = 0
i = 0
while i < len(s):
    t = 0
    for j in range(i, len(s)):
        if s[j] in substring:
            t += 1
        else:
            break
    i += 1
    MAX = max(MAX, t)
print(MAX)

Measured memory_bytes: 38256
#include<iostream>
using namespace std;
int main(){
    int mh;
    cin>>mh;
int n;
cin>>n;
int arr[n];
int sum=0;
for(int i=0;i<n;i++){
    cin>>arr[i];
    sum=sum+arr[i];
}
if(sum>=mh){
    cout<<"Yes"<<endl;
}
else{
    cout<<"No"<<endl;
}
return 0;
}


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

using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int dx[] = { 0, 1, -1, 0, 1, -1, 1, -1 };  // i<4:4way i<8:8way
int dy[] = { 1, 0, 0, -1, 1, -1, -1, 1 };

const ll mod = 1e9 + 7;
const ll INF = -1 * ((1LL << 63) + 1);
const int inf = -1 * ((1 << 31) + 1);

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    ll x,k,d;
    cin >> x >> k >> d;
    // まずxを正にする
    if(x<0)x*=-1;
    // xが負になるまでの操作回数を求める
    ll num = (x+d-1)/d;
    if(k<=num)cout << abs(x - (k * d) ) << endl;
    else{
        k -= num;
        x -= num * d;
        k%= 2;
        cout << abs(x + k*d) << endl;
    }
}

Measured memory_bytes: 3644
//By a boy whose heart was hurted badly
#include<bits/stdc++.h>
#define int long long
//#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
const int inf=0x3f3f3f3f;
const double eps=1e-6;
const int mod=1000000007;
typedef long long ll;
int modpow(int x,int y,int md){if(y==0)return 1;int ret=modpow(x,y>>1,md);ret=(ll)ret*ret%md;if(y&1)ret=(ll)ret*x%md;return ret;}
int A,B,Q;
int a[111111],b[111111];
pair<int,int>binary_searchA(int x){
	int l=-1,r=A;
	while(r-l>1){
		int mid=l+r>>1;
		if(a[mid]<x)l=mid;
		else r=mid;
	}
	if(l==-1)return make_pair(-1e18,a[0]);
	return make_pair(a[l],a[r]);
}
pair<int,int>binary_searchB(int x){
	int l=-1,r=B;
	while(r-l>1){
		int mid=l+r>>1;
		if(b[mid]<x)l=mid;
		else r=mid;
	}
	if(l==-1)return make_pair(-1e18,b[0]);
	return make_pair(b[l],b[r]);
}
signed main(){
	cin>>A>>B>>Q;
	for(int i=0;i<A;i++)cin>>a[i];
	for(int i=0;i<B;i++)cin>>b[i];
	sort(a,a+A);a[A]=1e18;
	sort(b,b+B);b[B]=1e18;
	while(Q--){
		int x;cin>>x;
		pair<int,int>pa=binary_searchA(x),pb=binary_searchB(x);
		int la=pa.first,ra=pa.second,lb=pb.first,rb=pb.second;
		int ans=1e18;
		//(la,lb)
		ans=min(ans,x-min(la,lb));
		//(ra,rb)
		ans=min(ans,max(ra,rb)-x);
		//(la,rb)
		ans=min(ans,min(rb-x,x-la)+rb-la);
		//(lb,ra)
		ans=min(ans,min(ra-x,x-lb)+ra-lb);
		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 2944
# 7/3

# n 以下の「753数」の個数

n = int(input())

def dfs(val):
    # 終了条件
    if val > n:
        return

    A.append(val)

    for v in [3, 5, 7]:
        val = A.pop()
        dfs(10 * val + v)
        A.append(val)

A = []
for v in [3, 5, 7]:
    dfs(v)

res = 0
for v in A:
    s = str(v)
    if '3' in s and '5' in s and '7' in s:
        res += 1

print(res)

Measured memory_bytes: 76128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
int a[maxn];
ll ans[maxn];
int main()
{
	int n;
	cin >> n;
	for(int i = 0; i < n; i++) cin >> a[i];
	ll odd = 0, even = a[n-1];
	for(int i = 0; i < n-1; i++) {
		if((i+1)&1) odd += a[i];
		else even += a[i];
	}
	ans[n-1] = even - odd;
	for(int i = n-2; i >= 0; i--) {
		ans[i] = 2LL * a[i] - ans[i+1];
	}
	for(int i = 0; i < n; i++) cout << ans[i] << " ";
	cout << endl;
}

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

using namespace std;

#define LL long long
#define Re register
#define U unsigned
#define forn(i,a,b) for(Re int i = a;i <= b;++i)
#define nfor(i,a,b) for(Re int i = a;i >= b;--i)
#define CLR(i,a) memset(i,a,sizeof(i))
#define BR printf("--------------------\n")
#define pb push_back
#define Rep(i,a,b) for(int i=a;i<=b;i++)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const double PI=atan(1.)*4.;
const int maxn=1e6+5;
const int mod=1e9+7;
const double e=2.71828182845904523536;
int dir[4][2]={1,0,0,1,-1,0,0,-1};
bool vis[maxn];
int f[maxn];
int main()
{
	ios::sync_with_stdio(false);
    cin.tie(0);
   	cout.tie(0);
    int n,m;
    cin>>n>>m;
    memset(vis,false,sizeof(vis));
    for(int i=0;i<m;i++)
    {
        int tmp;
        cin>>tmp;
        vis[tmp]=true;
    }
    f[0]=1;
    if(vis[1])f[1]=0;
    else
        f[1]=1;

    for(int i=2;i<=n;i++)
    {
        if(!vis[i])
            f[i]=f[i-1]+f[i-2];
        else
            f[i]=0;
        f[i]%=mod;
    }
    cout<<f[n]<<endl;
	return 0;
}


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

int main() {
  char c;
  cin >> c;
  
  if (isupper(c))
    cout << 'A' << endl;
  else
    cout << 'a' << endl;
  
  return 0;
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ll n, m; cin >> n >> m;
	if(n == 1){
		if(m == 1){
			cout << 1 << endl;
		} else {
			cout << m-2 << endl;
		}
	} else if(m == 1){
		cout << n-2 << endl;
	} else {
		cout << (n-2)*(m-2);
	}
	return 0;
}


Measured memory_bytes: 256
# https://atcoder.jp/contests/abc110/tasks/abc110_c
# 文字のカウント数についてその種類が同じならばYes

S = input()
T = input()

from collections import Counter
s_cnt = Counter(S)
t_cnt = Counter(T)

if set(s_cnt.values()) == set(t_cnt.values()) and len(s_cnt) == len(t_cnt):
    print('Yes')
else:
    print('No')


Measured memory_bytes: 3776
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
#include <vector>
#include <cstdio>
#include <bits/stdc++.h>
#include <set>
#include <map>
#include <stdio.h>
#include <stack>
#include <queue>
#include <deque>
#include <numeric>
#include <bits/stdc++.h>
#include <utility>
#include <iomanip>

#define ALL(obj) (obj).begin(), (obj).end()
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define RFOR(i,a,b) for(int i = (a); (b) <= i; i--)
#define REP(i,n) for(int i = 0; i < (n); i++)
#define RREP(i,n) for(int i = n; n <= i; i--)
#define ABS(a) ((a < 0) ? ((-1)*(a)) : (a))
#define elif else if
#define MOD 1000000007
#define INF (1<<29)

using namespace std;

#define ld long double
#define ll long long

map <int ,int> mpa,mpb;
typedef pair<ll, ll> P;
priority_queue<P, vector<P>, greater<P>> pque;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  ll N,M;
  cin >> N >> M;
  vector<ll> X;
  ll t;
  if(N>=M){
    cout << 0 << endl;
    return 0;
  }
  for(int i=0;i<M;i++){
    cin >> t;
    X.push_back(t);
  }
  sort(X.begin(),X.end());
  ll ans=0;
  vector<ll> Y;
  ll a,b;
  for(int i=0;i<M-1;i++){
    a=X[i];
    b=X[i+1];
    Y.push_back(abs(a-b));
  }
  sort(Y.begin(),Y.end());
  for(int i=0;i<M-N;i++){
    ans+=Y[i];
  }

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


Measured memory_bytes: 2548
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <numeric>
#include <cctype>
#include <tuple>
#include <array>
#include <climits>
#include <bitset>
#include <cassert>

// BEGIN CUT HERE
#ifdef _MSC_VER
#include <agents.h>
#define __float128 long double
#endif
// END CUT HERE 

#define FOR(i, a, b) for(int i = (a); i < (int)(b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define REV(v) v.rbegin(), v.rend()
#define MEMSET(v, s) memset(v, s, sizeof(v))
#define UNIQUE(v) (v).erase(unique(ALL(v)), (v).end())
#define MP make_pair
#define MT make_tuple

using namespace std;

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

int fr[110][110];
vector<P> G[110];
vector<int> cand[20];


int v[20];

int calc(int n){
	//rep(i, n) cout << v[i] << ' ';
	//cout << endl;
	int res = 0;
	rep(i, n){
		int tmp = 1e9;
		rep(j, n){
			if (i == j) continue;
			tmp = min(tmp, fr[v[i]][v[j]]);
		}
		res += tmp;
	}
	return res;
}

int dfs(int i, int k, int sz, int n){
	if (i == n) return calc(n);

	int res = 0;
	for (int j = k; j < sz; ++j){
		v[i] = cand[n][j];
		res = max(res, dfs(i + 1, j + 1, sz, n));
		if (i + sz - k < n) break;
	}
	return res;
}

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

	int n, m;
	cin >> n >> m;


	rep(i, m){
		int a, b, f;
		cin >> a >> b >> f;
		--a, --b;
		G[a].push_back(MP(b, f));
		G[b].push_back(MP(a, f));
		fr[a][b] = fr[b][a] = f;
	}

	rep(i, n){
		FOR(j, 1, 15){
			if (G[i].size() >= j) cand[j+1].push_back(i);
		}
	}

	int ans = 0;
	FOR(i, 2, 15){
		ans = max(ans, dfs(0, 0, cand[i].size(), i));
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1268
#include<iostream>
using namespace std;
int main(){
  int n;cin>>n;
  bool flag=false;
  for(int i=1;i<n+1;i++){
    int t=i;
    while(t!=0){
      if(t%10==3){flag=true;break;}
      t/=10;
    }
    if(i%3==0  or flag)cout<<" "<<i;
    flag=false;
  }
  cout<<endl;
}


Measured memory_bytes: 3100
a=[]
while True:
    m,n_min,n_max=map(int,input().split())
    if m==0 and n_min==0 and n_max==0:
        for i in range(len(a)):
            print(a[i])
        break
    else:
        p=[]
        count=0
        counter=0
        for i in range(m):
            s=int(input())
            p.append(s)
        p=sorted(p,reverse=True)
        for i in range(n_min-1,n_max):
            if counter<=int(p[i])-int(p[i+1]):
                counter=int(p[i])-int(p[i+1])
                count=i+1
        a.append(count)



Measured memory_bytes: 5628
#include <bits/stdc++.h>
using namespace std;
int main(){
  long int n,k,value;
  cin>>n>>k;
  vector<long int> a;
  for(long int i=0;i<n;i++){
    cin>>value;
    a.push_back(value);
  }
  long int r;
  vector<long int> p;
   p.push_back(0);
  for(long int i=1;i<n;i++){
      long int m=999999999;
      for(long int j=i-k;j<i;j++){
          if(j>=0){
               r=min((p[j]+abs(a[i]-a[j])),m);
            m=r;
              }
              
          }
    p.push_back(r);
  }
  cout<<p[n-1];
  return 0;
}

Measured memory_bytes: 2548
import java.util.*;
import java.util.ArrayList;
import java.util.List;

public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    double n = sc.nextDouble();
    System.out.println((int)((n % 2) == 0 ? n : n * 2 ));
    return;
  }
}


Measured memory_bytes: 23124
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int X = sc.nextInt();
		int A = sc.nextInt();
		Integer[] array = new Integer[X];
		int count = 0;
		
		for(int i =0; i < X; i++ ) {
			array[i] = sc.nextInt();
		}
		Arrays.sort(array);
		
		for(int i =0; i < X ; i++) {
			if(array[i] <= A) {
				A -= array[i];
				count++;
			}
		}
		if(count == X && A != 0) {
			count--;
		}
		System.out.println(count);
	}
}


Measured memory_bytes: 23764
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;


int main(){
  int N;
  cin >> N;
  vector<int> V, C;
  rep(i,N){
    int a;
    cin >> a;
    V.push_back(a);
  }
  rep(i,N){
    int a;
    cin >> a;
    C.push_back(a);
  }

  int ret = 0;
  rep(i,N){
    if(V[i] - C[i] > 0) ret += V[i] - C[i];
  }

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



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

int main(){
	int time,n,start,fin,sum;
	while(cin>>time,time){
		cin>>n;
		sum=0;
		for(int i=0;i<n;i++){
			cin>>start>>fin;
			sum+=fin-start;
		}
		if(sum>=time)cout<<"OK"<<endl;
		else cout<<time-sum<<endl;
	}
}

Measured memory_bytes: 1160
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=1e4+50;
const int mod=1e9+7;
using namespace std;
int n,h,y,a[nmax],b[nmax],f[nmax],i,j;
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>h>>n;
	for(i=1;i<=n;i++)cin>>a[i]>>b[i];
	for(i=1;i<=h;i++)f[i]=inf;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<min(h+1,a[i]);j++)f[j]=min(f[j],b[i]);
		for(j=a[i];j<=h;j++)f[j]=min(f[j],f[j-a[i]]+b[i]);
	}
	cout<<f[h]<<endl;
	return 0;
}


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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;
ll L;
ll A[200050];
ll sum[200050];
ll even[200050];
ll odd[200050];
ll even_after[200050];
ll even_before[200050];
ll odd_after[200050];
ll odd_before[200050];

int main() {
    //cout.precision(10);
    cin >> L;
    for(int i = 1; i <= L; i++) {
        cin >> A[i];
        sum[i] = sum[i - 1] + A[i];
        even[i] = even[i - 1];
        if(A[i] % 2 == 1) even[i]++;
        if(A[i] == 0) even[i] += 2;
        odd[i] = odd[i - 1];
        if(A[i] % 2 == 0) odd[i]++;
    }
    for(int i = 1; i <= L; i++) {
        even_before[i] = min(even_before[i - 1] + (even[i] - even[i - 1]), sum[i]);
        odd_before[i] = min(odd_before[i - 1] + (odd[i] - odd[i - 1]), even_before[i]);
        //cout << i << " " << even_before[i] << " " << odd_before[i] << endl;
    }
//    for(int i = L; i >= 1; i--) {
//        even_after[i] = min(even_after[i + 1] + (even[i] - even[i - 1]), sum[L] - sum[i - 1]);
//        odd_after[i] = min(odd_after[i + 1] + (odd[i] - odd[i - 1]), even_after[i]);
//    }
    for (int i = L - 1; i >= 0; i--) {
        even_after[i] = min(even_after[i + 1] + (even[i + 1] - even[i]), sum[L] - sum[i]);
        odd_after[i] = min(odd_after[i + 1] + (odd[i + 1] - odd[i]), even_after[i]);
    }
    ll ans = 1e16;
    for(int i = 0; i <= L; i++) {
        ans = min(ans, odd_before[i] + odd_after[i]);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 12800
open Scanf
open Printf

let (n,m) = sscanf (read_line ()) "%d %d" (fun a b -> (a,b));;
(*
let array = Array.make n (0,0);;
for i = 0 to (n-1) do
  let (x,y) = sscanf (read_line ()) "%d %d" (fun a b -> (a,b)) in
  array.(i) <- (x,y)
done;;
*)

let rec input_list = function
  | 0 -> []
  | x -> sscanf (read_line ()) "%d %d" (fun a b -> (a,b)) :: (input_list (x-1));;

let list = input_list n;;
let sort_list = List.sort (fun a b -> compare (fst a) (fst b)) list;;

module PrioQueue =
struct
  type priority = int
  type 'a queue = Empty | Node of priority * 'a * 'a queue * 'a queue
  let empty = Empty
  let rec insert queue prio elt =
    match queue with
      Empty -> Node(prio, elt, Empty, Empty)
    | Node(p, e, left, right) ->
      (* prio <= p なら小さいほうが優先 prio >= p なら大きい方が優先 *)
      if prio = p then (* prio = p なら eltが小さい方を優先 *)
        if e >= elt
          then Node(prio, elt, insert right p e, left)
          else Node(p, e, insert right prio elt, left)
      else 
      if prio > p
        then Node(prio, elt, insert right p e, left)
        else Node(p, e, insert right prio elt, left)
  exception Queue_is_empty
  let rec remove_top = function
      Empty -> raise Queue_is_empty
    | Node(prio, elt, left, Empty) -> left
    | Node(prio, elt, Empty, right) -> right
    | Node(prio, elt, (Node(lprio, lelt, _, _) as left), (Node(rprio, relt, _, _) as right)) ->
      if lprio = rprio then (* prio <= p なら小さいほうが優先 prio >= p なら大きい方が優先 *)
        if relt >= lelt
      then Node(lprio, lelt, remove_top left, right)
      else Node(rprio, relt, left, remove_top right)
      else if lprio > rprio 
      then Node(lprio, lelt, remove_top left, right)
      else Node(rprio, relt, left, remove_top right)
  let rec print_queue = function
      Empty -> Printf.printf "Empty\n"
    | Node(prio, elt, left, right) -> 
      let _ = Printf.printf "prio = %d, elt = %d \n" prio elt in
      let _ = Printf.printf "left = " in
      let _ = print_queue left in
      let _ = Printf.printf "right = " in
      let _ = print_queue right in ()
  let extract = function
      Empty -> raise Queue_is_empty
    | Node(prio, elt, _, _) as queue -> (prio, elt, remove_top queue)
end;;

open PrioQueue;;

let rec solve_aux list m pq =
  match list with
  | [] -> ([], pq)
  | (x,y) :: rest ->
    if x <= m then 
      let new_pq = PrioQueue.insert pq y x in
      solve_aux rest m new_pq
    else
      (list,pq);;

let solve () =
let rec loop rest_day ans candi pq =
  (*let _ = printf "candi = " in
  let _ = List.iter (fun a -> printf "%d / " (fst a))  candi in*)
  if rest_day = m+1 then ans
  else
   (* let _ = printf "rest_day = %d, ans = %d, \n pq = " rest_day ans in*)
    let (rest, new_pq) = solve_aux candi rest_day pq in
    (*let _ = PrioQueue.print_queue new_pq in*)
    match new_pq with
    | Empty -> 
      loop (rest_day + 1) ans rest Empty
    | Node(prio, elt, _, _) as queue -> 
      loop (rest_day + 1) (ans + prio) rest (PrioQueue.remove_top queue)
in loop 1 0 sort_list Empty;;

let _ = printf "%d\n" (solve ());;

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

const int m=1000000000;

int main(){
  int h,w,k;
  cin >> h >> w >> k;
  vector<vector<int>> a(h,vector<int>(w));
  vector<vector<int>> ans(h,vector<int>(w));
  rep(i,h){
    rep(j,w){
      char s;
      cin >> s;
      if(s=='#') a[i][j] = 1;
    }
  }
  int ypoint=0,color1=1;
  rep(i,h){
    int xpoint=0;
    bool flag=false;
    rep(j,w){
      if(a[i][j]==1){
        ans[i][j]=color1;
        for(int k=xpoint;k<j;k++) ans[i][k]=color1;
        color1++;
        xpoint=j+1;
        flag=true;
      }
    }
    if(flag==true){
      int color2=ans[i][xpoint-1];
      for(int k=xpoint;k<w;k++) ans[i][k]=color2;
      if(ypoint==i){ypoint++;continue;}
      rep(j,w){
        int color3=ans[i][j];
        for(int k=ypoint;k<i;k++) ans[k][j]=color3;
      }
      ypoint=i+1;
    }
  }
  rep(j,w){
    int color3=ans[ypoint-1][j];
    for(int k=ypoint;k<h;k++) ans[k][j]=color3;
  }    
  
  rep(i,h){
    rep(j,w){
      cout << ans[i][j] << ' ';
    }
    cout << "\n";
  }
  
  return 0;
}

Measured memory_bytes: 4360
#include<iostream>
using namespace std;
int Stairs(int n){
  int sum=0;
  while(n!=0){
    sum+=n;
    n--;
  }
  return sum;
}
int main(){
  int a,b;
  cin >> a >> b;
  int high = Stairs(b-a-1);
  cout << high-a << "\n";
  
  return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<set>
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
int stack[20];
inline void write(int x)
{
	if(x<0){putchar('-');x=-x;}
	if(!x){putchar('0');return;}
	int top=0;
	while(x)stack[++top]=x%10,x/=10;
	while(top)putchar(stack[top--]+'0');
}
inline void pr1(int x){write(x),putchar(' ');}
inline void pr2(int x){write(x),puts("");}
set<int>s;
typedef set<int>::iterator It;
int n,a[100010],cnt[100010];
int top,ans[100010];
inline bool dfs(int limit)
{
	if(top==n){for(int i=1;i<=n;i++)pr1(ans[i]);return true;}
	if(n-top-1==cnt[limit] && s.find(limit)!=s.end())return false;
	for(It i=s.begin();i!=s.end();i++)
	{
		int p=*i;
		if(p==limit)continue;
		ans[++top]=p,cnt[a[p]]--;s.erase(i);
		if(dfs(a[p])==true)return true;
		top--,cnt[a[p]]++;s.insert(p);
	}return false;
}
int main()
{
	//freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++)a[i]=read(),cnt[a[i]]++,s.insert(i);
	if(dfs(0)==false)puts("-1");
	return 0;
}


Measured memory_bytes: 8960
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
using namespace std;
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) int((x).size())
#define OUT(x) cout << (x) << endl
typedef long long ll;
typedef vector<int> V;
typedef vector<vector<int>> VV;
typedef pair<int, int> P;
typedef map<string, int> M;
typedef unordered_map<int, int> HM;
typedef set<int> S;
typedef queue<int> Q;

int main(){
    int n,k;
    cin>>n>>k;
    double ans = 0.0;
    for(int i=1; i<=n; i++){
        double tmp = 1.0/n;
        int score = i;
        while(score < k){
            tmp /= 2.0;
            score *= 2;
        }
        ans += tmp;
    }
    cout << setprecision(10) << ans << endl;
}


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

#ifdef LOCAL
#define DEBUG(...) debug(#__VA_ARGS__, __VA_ARGS__);
#else
#define DEBUG(...)
#endif

template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) {return os << "(" << p.first << ", " << p.second << ")";}
template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream &os, const C &c) {bool f = true; os << "["; for (const auto &x : c) {if (!f) os << ", "; f = false; os << x;} return os << "]";}
template<typename T> void debug(string s, T x) {cerr << s << " = " << x << "\n";}
template<typename T, typename... Args> void debug(string s, T x, Args... args) {cerr << s.substr(0, s.find(',')) << " = " << x << " | "; debug(s.substr(s.find(',') + 2), args...);}

int n, m, q, a[50], b[50], c[50], d[50];

int solve(vector<int> &v, int mn) {
    if (v.size() == n) {
        int ret = 0;
        for (int i=0; i<q; i++)
            ret += (v[b[i]] - v[a[i]] == c[i] ? d[i] : 0);
        return ret;
    }

    int ret = 0;
    for (int i=mn; i<=m; i++) {
        v.push_back(i);
        ret = max(ret, solve(v, i));
        v.pop_back();
    }

    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    cin >> n >> m >> q;
    for (int i=0; i<q; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        a[i]--, b[i]--;
    }

    vector<int> v;
    cout << solve(v, 1) << "\n";

    return 0;
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
int d(int n,int d){
    return (n/(int)pow(10,d-1))%10;
}
int main(){
    int H,W;
    cin>>H>>W;
    
    // 入力の受け取り
    vector<string> grid(H);
    for(int i=0;i<H;++i)cin>>grid[i];
    
    // 移動コストの計算
    vector<vector<int>> node(H,vector<int>(W));
    node[0][0]=0;
    
    // 横方向一列コスト
    {
        for(int j=1;j<W;++j){
            node[0][j]=node[0][j-1]+(grid[0][j-1]!=grid[0][j]);
        }
    }
    // 縦方向一列コスト
    {
        for(int i=1;i<H;++i){
            node[i][0]=node[i-1][0]+(grid[i-1][0]!=grid[i][0]);
        }
    }
    
    for(int i=1;i<H;++i){
        for(int j=1;j<W;++j){
            node[i][j]=min(
                node[i][j-1]+(grid[i][j-1]!=grid[i][j]),
                node[i-1][j]+(grid[i-1][j]!=grid[i][j])
            );
        }
    }
    
    int goalcost=node[H-1][W-1];
    if(grid[0][0]=='#')++goalcost;
    if(grid[H-1][W-1]=='#')++goalcost;
    goalcost/=2;
    cout<<goalcost<<endl;
}

Measured memory_bytes: 256
def main():
  import sys
  import fractions
  input = sys.stdin.readline
  n=int(input())
  a=list(map(int,input().split()))
  l,r=[0]*(n-1),[0]*(n-1)
  for i in range(n-1):
    l[i]=fractions.gcd(l[i-1],a[i]) 
    r[i]=fractions.gcd(r[i-1],a[n-1-i])
  x=[0]*n
  for i in range(n):
    if i==0:
      x[i]=r[-1]
    elif i==(n-1):
      x[i]=l[-1]
    else:
      x[i]=fractions.gcd(l[i-1],r[n-2-i])
  print(max(x)) 
if __name__=='__main__':
  main()

Measured memory_bytes: 16132
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
struct process{
	char name[11];
	int time;
	process(char* n, int t){strcpy(name, n); time = t;}
};

int main(){
	char nm[11];
	int i, n, t, q, t_elapsed = 0;
	int *tp;
	queue<process> prcs;
	
	cin >> n >> q;
	for(i=0;i<n;i++){
		cin >> nm >> t;
		prcs.push(process(nm, t));
	}
	while(!prcs.empty()){
		tp = &(prcs.front().time);
		if(*tp <= q){
			t_elapsed += *tp;
			cout << prcs.front().name << " " << t_elapsed << endl;
			prcs.pop();
		}else{
			t_elapsed += q;
			*tp -= q;
			prcs.push(prcs.front());
			prcs.pop();
		}
	}
	return 0;
}



Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int N,K;
    cin >> N >> K;
    int d,a;
    int count=0;
    vector<int> sunuke(N,0);
    for(int i=0;i<K;i++){
        cin >> d;
        for(int j=0;j<d;j++){
            cin >> a;
            sunuke.at(a-1)++;
        }
    }
    for(int i=0;i<N;i++){
        if(sunuke.at(i)==0){
            count++;
        }
    }
    cout << count << endl;
}

Measured memory_bytes: 3600
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lvector vector<ll> 
#define P pair<ll,ll>
#define ALL(a) a.begin(),a.end()
#define YESNO(i) puts((i)?"YES":"NO");
#define YesNo(i) puts((i)?"Yes":"No");
#define yesno(i) puts((i)?"yes":"no");
#define rep(i,n) for(ll i=0; i<n; ++i)
#define print(a) cout << (a) << endl

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  char alph;cin>>alph;
  print(islower(alph)?'a':'A');
  return 0;
}

Measured memory_bytes: 3612
n = int(input())
info = [list(map(int, input().split())) for _ in range(n)]

def main():
    for cx in range(101):
        for cy in range(101):
            for xi, yi, hi in info:
                if hi > 0:
                    h = abs(xi - cx) + abs(yi - cy) + hi
                    break

            success = True
            for xi, yi, hi in info:
                if hi != max(h - abs(xi - cx) - abs(yi - cy), 0):
                    success = False
                    break

            if success:
                print(cx, cy, h)
                return

main()


Measured memory_bytes: 3064
/*http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0009&lang=jp*/

#include <iostream>
#include <vector>
#include <algorithm>

#define MAX 999999

using namespace std;

int num_prime[MAX];
bool not_prime_flag[MAX];

int main()
{
    int n;
    int max_input;
    vector<int> input;

    while (cin>>n){
        input.push_back(n);
    }
    max_input=*max_element(input.begin(),input.end());
    for (int i = 1; i < max_input; ++i) {
        if(!not_prime_flag[i]){
            for (int j = 2; (i+1)*j-1 < max_input; ++j) {
                not_prime_flag[(i+1)*j-1] = true;
            }
        }
        num_prime[i]=num_prime[i-1]+!not_prime_flag[i];
    }
    for (int i:input) {
        cout<<num_prime[i-1]<<endl;
    }
    return 0;
}

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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int N = 2e5+50;
const int M = 1e6;
const ll oo = 1e18;
const int mod = 1e9+7;

int a[N],dp[N];

int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	dp[1] = 0;
	dp[2] = abs(a[1] - a[2]);
	for(int i=3;i<=n;i++)
		dp[i] = min(dp[i-1] + abs(a[i] - a[i-1]),dp[i-2] + abs(a[i] - a[i-2]));
	
	cout << dp[n] << endl;
}

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


int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  int x,n;
  cin>>x>>n;
  vector<int> v;
  for(int i=0;i<n;i++){
    int t;
    cin>>t;
    v.push_back(t);
  }
  sort(v.begin(),v.end());
  int j;
  int k;
  for(int i=x;i<x+200;i++){
    if(binary_search(v.begin(),v.end(),i)){
      ;
    }else{
       j=i;
      i=x+300;
    }
  }
  for(int i=x-200;i<x;i++){
    if(binary_search(v.begin(),v.end(),i)){
      ;
    }else{
      k=i;
    }
  }
  if(abs(x-j)>abs(x-k)){
    cout<<k;
  }else if(abs(x-k)>abs(x-j)){
    cout<<j;
  }else{
    cout<<k;
  }


}

Measured memory_bytes: 3660
#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i, s, n) for (int i = s; i < n; i++)
#define repe(i, s, n) for(int i = s;i<=n;i++)
static const ll MOD = 1e9 + 7;

ll c[100001] = {};
int main() {
	ll n, k; cin >> n >> k;
	ll a, b;
	rep(i, 0, n) {
		cin >> a >> b;
		c[a] += b;
	}

	repe(i, 1, 100000) {
		k -= c[i];
		if (k <= 0) {
			cout << i << endl;
			return 0;
		}
	}

	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define va first
#define vb second
using namespace std;
using pii = pair<int,int>;

int n, k, q;
int a[2005];
set<pii> S;

vector<int> cmp;

void input(){
    cin >> n >> k >> q;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        cmp.push_back(a[i]);
    }
    sort(all(cmp));
    cmp.resize(unique(all(cmp)) - cmp.begin());
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    input();
    S.emplace(1, n);
    vector<int> tmp, ump;
    vector<pii> vmp, wmp;
    tmp.reserve(n);
    ump.reserve(n);
    vmp.reserve(n);
    wmp.reserve(n);
    int ans = INT_MAX;
    for(int i = 0; i < cmp.size(); i++){
        tmp.clear();
        for(pii p : S){
            ump.clear();
            for(int u = p.va; u <= p.vb; u++){
                ump.push_back(a[u]);
            }
            sort(all(ump));
            for(int i = 0; i < p.vb - p.va - k + 2; i++) tmp.push_back(ump[i]);
        }
        sort(all(tmp));
        if(tmp.size() < q) break;
        ans = min(ans, tmp[q-1] - tmp[0]);
        vmp.clear();
        wmp.clear();
        for(pii p : S){
            int cur = p.va - 1;
            int flag = 0;
            for(int u = p.va; u <= p.vb; u++){
                if(a[u] == cmp[i]){
                    if(!flag){
                        wmp.push_back(p);
                        flag = 1;
                    }
                    vmp.emplace_back(cur + 1, u - 1);
                    cur = u;
                }
            }
            vmp.emplace_back(cur + 1, p.vb);
        }
        for(pii p : wmp) S.erase(p);
        for(pii p : vmp){
            if(p.vb - p.va + 1 >= k) S.insert(p);
        }
    }
    cout << ans << '\n';
}


Measured memory_bytes: 384
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define rep(x,to) for(int x=0; x<(to); ++(x))

int main() {
    int n, m, win, lose;
    cin >> n >> m;
    vector <int> vswin[5000];
    int deg[5000] = {};
    rep(i,m) {
        cin >> win >> lose;
        win--, lose--;
        vswin[win].push_back(lose);
        deg[lose]++;
    }
    bool f = false;
    vector <int> ans;
    queue <int> grade;
    rep(i,n) {
        if(deg[i]==0) grade.push(i);
    }
    while(!grade.empty()) {
        if(grade.size()>=2) f = true;
        int t = grade.front(); grade.pop();
        ans.push_back(t);
        rep(i,vswin[t].size()) {
            int u = vswin[t][i];
            deg[u]--;
            if(deg[u]==0) grade.push(u);
        }
    }
    rep(i,n) {
        cout << ans[i]+1 << endl;
    }
    if(f) cout << 1 << endl;
    else cout << 0 <<endl;
    return 0;
}

Measured memory_bytes: 2052
#include<iostream>
#include<cstdio>
#include<math.h>
using namespace std;
int main(){
  int a,b,x = 0,y = 0,z = 0;
  for(;;){
    if(scanf("%d,%d",&a,&b) == EOF) break;
    x+=a*b;
    y+=b;
    z++;
  }
  cout <<x<<endl<<round((double)y/(double)z)<<endl;
  return 0;
}

Measured memory_bytes: 1280
#include<algorithm>
#include<bitset>
#include<climits>
#include<cmath>
#include<cstdlib>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<string>
#include<time.h>
#include<tuple>
#include<utility>
#include<vector>

using namespace std;
const long mod = 1000000007;
long gcd(long x, long y) { if (x > y) { return gcd(y, x); } long r; while (y != 0) { r = x % y; x = y; y = r; }return x; }
long lcm(long x, long y) { return(x / gcd(x, y)) * y; }

int main() {

	long N; cin >> N;
	cout << (N - 1) * N / 2 << endl;

}

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

int c[33], s[444][33];
int sco(int t, const vector<int> &v) {
    int r = 0, l = 0, d = v.size();
    for(int i = 0; i < d; i++)
        if(v[i] == t)
            r += s[i][t] - c[t] * (i + 1 - l) * (i - l) / 2, l = i + 1;
    r -= c[t] * (d + 1 - l) * (d - l) / 2;
    return r;
}
int main() {
    auto ti = clock();
    int d;
    cin >> d;
    for(int i = 0; i < 26; i++)
        cin >> c[i];
    for(int i = 0; i < d; i++)
        for(int j = 0; j < 26; j++)
            cin >> s[i][j];
    random_device rd;
    mt19937 mt(rd());
    uniform_int_distribution<> rc(0, 25), r0(0, d - 1), r2(1, 6);
    uniform_real_distribution<> ru(0, 1);
    vector<int> tt(d);
    for(int &i : tt)
        i = rc(mt);
    int cnt = 0;
    for(;;) {
        auto T = (clock() - ti + 0.) / CLOCKS_PER_SEC;
        if(T > 1.9)
            break;
        auto U = pow(2e3, 1 - T / 1.9) * pow(6e2, T / 1.9);
        for(int cn = 0; cn < 100; cn++, cnt++) {
            auto uu = tt;
            int di;
            if(rc(mt) < 12) {
                int x0 = r0(mt), xc = rc(mt);
                uu[x0] = xc;
                di = sco(tt[x0], uu) + sco(xc, uu) - sco(tt[x0], tt) -
                     sco(xc, tt);
            } else {
                int x2 = r2(mt);
                uniform_int_distribution<> r1(0, d - 1 - x2);
                int x1 = r1(mt);
                x2 += x1;
                swap(uu[x1], uu[x2]);
                di = sco(tt[x1], uu) + sco(tt[x2], uu) - sco(tt[x1], tt) -
                     sco(tt[x2], tt);
            }
            if(ru(mt) <= exp(di / U))
                tt.swap(uu);
        }
    }
    int M = 0;
    for(int j = 0; j < 26; j++)
        M += sco(j, tt);
    for(int i : tt)
        cout << i + 1 << '\n';
    cerr << M << endl;
    cerr << cnt << endl;
    return 0;
}


Measured memory_bytes: 4284
//
// Created by yamunaku on 2019/09/07.
//

#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repl(i, l, r) for(int i = (l); i < (r); i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
#define perl(i, l, r) for(int i = ((r)-1); i >= (l); i--)
#define all(x) (x).begin(),(x).end()
#define MOD9 998244353
#define MOD1 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000
#define SP <<" "<<
#define CYES cout<<"Yes"<<endl
#define CNO cout<<"No"<<endl
#define CFS cin.tie(0);ios::sync_with_stdio(false)
#define CST(x) cout<<fixed<<setprecision(x)

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int>> mti;
typedef vector<ll> vl;
typedef vector<vector<ll>> mtl;

int n;
int id(int x,int y){
    return min(x,y)*n+max(x,y);
}

int main(){
    cin >> n;
    mti a(n,vi(n-1));
    mti e(n*n);
    vi deg(n*n, 0), dp(n*n, -1);
    rep(i,n) rep(j,n-1){
        cin >> a[i][j];
        a[i][j]--;
        if(j>0){
            e[id(i,a[i][j-1])].push_back(id(i,a[i][j]));
            deg[id(i,a[i][j])]++;
        }
    }
    queue<int> q;
    rep(i,n){
        rep(j,i){
            if(deg[id(i,j)]==0){
                q.push(id(i,j));
                dp[id(i,j)]=1;
            }
        }
    }
    int ma=1;
    while(!q.empty()){
        int now=q.front();
        q.pop();
        for(auto nx:e[now]){
            deg[nx]--;
            dp[nx]=max(dp[nx],dp[now]+1);
            if(deg[nx]==0) q.push(nx);
        }
        ma=max(ma,dp[now]);
    }
    rep(i,n*n){
        if(deg[i]!=0){
            cout << -1 << endl;
            return 0;
        }
    }
    cout << ma << endl;
    return 0;
}


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

#define int long long
#define endl "\n"
#define REP(i,a,n) for(int i=a;i<n;++i)
#define REPR(i,a,n) for(int i=a;i>n;--i)
#define RUP(a,b) (((a)+(b)-1)/(b))
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define INF LLONG_MAX/2
#define PI acos(-1.0)
//#define MOD 1000000007

typedef long long ll;
typedef pair<int,int> Pii;
typedef tuple<int,int,int> Tiii;
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef vector<Pii> VPii;
typedef vector<string> Vs;
typedef priority_queue<int> PQi;

template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
void vout(Vi &v){for(int i=0;i<(v).size();i++) cout<<v[i]<<" ";cout<<endl;}
void vout(Vs &v){for(int i=0;i<(v).size();i++) cout<<v[i]<<" ";cout<<endl;}
void vvout(VVi &v){for(int i=0;i<(v).size();i++) vout(v[i]);}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
int mypow(int x, int n, int m){if(n==0)return 1;if(n%2==0)return mypow(x*x%m,n/2,m);else return x*mypow(x,n-1,m)%m;}
int digit(int k,int i){string s = to_string(k);return s[s.size()-i]-'0';}
void uniq(Vi &v){sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());} //vectorの同じ要素消す
int ctoi(char c){if(c>='0'&&c<='9'){return c-'0';}return 0;}
int leng(int n){string s=to_string(n); return s.size();} //intの桁数
int digitsum(int n){int ret=0; while(n>0){ret+=n%10;n/=10;}return ret;} //桁和
int lesscount(int x,Vi &a){return lower_bound(a.begin(),a.end(),x)-a.begin();} //vector aにおけるx未満の数の個数
int orlesscount(int x,Vi &a){return upper_bound(a.begin(),a.end(),x)-a.begin();} //vector aにおけるx以下の数の個数
int morecount(int x,Vi &a){return a.size()-orlesscount(x,a);} //vector aにおけるxより大きい数の個数
int ormorecount(int x,Vi &a){return a.size()-lesscount(x,a);} //vector aにおけるx以上の数の個数
int count(int x,Vi &a) {return upper_bound(ALL(a),x)-lower_bound(ALL(a),x);} //vector aにおけるxの個数
Vi accum(Vi &v){Vi ret((v).size()+1);REP(i,0,(v).size()) ret[i+1]=ret[i]+v[i];return ret;}
bool comp(Pii a,Pii b){
    if(a.second != b.second) return a.second<b.second;
    else return a.first<b.first;
}


void solve(long long S, long long W){
    if(S>W) cout<<"safe"<<endl;
    else cout<<"unsafe"<<endl;
}

signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);
    long long S;
    scanf("%lld",&S);
    long long W;
    scanf("%lld",&W);
    solve(S, W);
    return 0;
}


Measured memory_bytes: 3716
#include <iostream>
#include <algorithm>
#define rep(i, a, n) for(int i = a;i < n;i++)
#define repr(i, a, n) for(int i = a;i > n;i--)
using namespace std;


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

	int b = n;
	b %= 1000;

	if(b <= a) cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
#define _ ios_base::sync_with_stdio(0); cin.tie(0);
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

using namespace std;

using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 100*1000+10,mod=1e9+7;
const ll INF = 1e18;
int n,m,s,t;
vector<pi>V[nax];
ll dist[nax][2];
int cnt[nax][2],ans;
ll path_len;

void Dijkstra(int start,bool typ) {
	for(int i = 1; i <= n; ++i) {
		dist[i][typ] = INF;
	}
	dist[start][typ] = 0;
	cnt[start][typ] = 1;
	priority_queue< pair<ll,int> > PQ;
	PQ.push({0,start});
	while(!PQ.empty()) {
		int v = PQ.top().ND;
		ll d = -PQ.top().ST;
		PQ.pop();
		if(d > dist[v][typ]) {
			continue;
		}
		for(auto nbh : V[v]) {
			if(d + nbh.ND < dist[nbh.ST][typ]) {
				dist[nbh.ST][typ] = d + nbh.ND;
				cnt[nbh.ST][typ] = cnt[v][typ];
				PQ.push({-dist[nbh.ST][typ],nbh.ST});
			} else if(d + nbh.ND == dist[nbh.ST][typ]) {
				cnt[nbh.ST][typ] = (cnt[nbh.ST][typ] + cnt[v][typ])%mod;
			}
		}
	}
}

int main() {_
	cin >> n >> m >> s >> t;
	for(int a,b,c,i=1; i <= m; ++i) {
		cin >> a >> b >> c;
		V[a].emplace_back(b,c);
		V[b].emplace_back(a,c);
	}
	Dijkstra(s,0);
	Dijkstra(t,1);
	path_len = dist[t][0];
	for(int i = 1; i <= n; ++i) {
		if(dist[i][0] * 2 == path_len) {
			//I'm a middle vertex
			int diff_path = ((ll)cnt[i][0] * cnt[i][1])%mod;
			ans = (ans + ((ll)diff_path * diff_path))%mod;
		}
	}
	for(int i = 1; i <= n; ++i) {
		for(auto nbh : V[i]) {
			if(dist[i][0] + nbh.ND + dist[nbh.ST][1] == path_len) {
				if(dist[i][0] * 2 < path_len && dist[nbh.ST][0] * 2 > path_len) {
					//I'm a middle edge
					int diff_path = ((ll)cnt[i][0] * cnt[nbh.ST][1])%mod;
					ans = (ans + ((ll)diff_path * diff_path))%mod;
				}
			}
		}
	}
	int cnt_all = ((ll)cnt[t][0]*cnt[t][0])%mod;
	ans = (cnt_all - ans)%mod;
	if(ans<0) ans += mod;
	cout << ans;
	
}


Measured memory_bytes: 14292
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define Q 44
#define i16 int
#define Min(xxx,yyy) xxx=min(xxx,yyy)
i16 sm[Q][Q],f[Q][Q][Q][Q];
char aa[Q];
inline i16 G(int x1,int y1,int x2,int y2)
{--x1,--y1;return sm[x2][y2]+sm[x1][y1]-sm[x1][y2]-sm[x2][y1];}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	int sx=-1,sy=-1;
	for(int i=1;i<=n;i++){
		scanf("%s",aa+1);
		for(int j=1;j<=m;j++){
			sm[i][j]=sm[i-1][j]+sm[i][j-1]-sm[i-1][j-1]+(aa[j]=='#');
			if(aa[j]>='A'&&aa[j]<='Z')sx=i,sy=j;
		}
	}
	if(min(sx,sy)<0)cerr<<"Err!!\n";
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			for(int k=1;k<=n;k++)
				for(int l=1;l<=m;l++)
					f[i][j][k][l]=10000;
	f[1][1][n][m]=0;
	i16 ans=10000;
	for(int x1=1;x1<=sx;x1++)
	for(int y1=1;y1<=sy;y1++)
	for(int x2=n;x2>=sx;--x2)
	for(int y2=m;y2>=sy;--y2){
		i16 val=f[x1][y1][x2][y2];
		Min(ans,val+min(min(G(x1,y1,sx,sy),G(sx,sy,x2,y2)),min(G(x1,sy,sx,y2),G(sx,y1,x2,sy))));
		for(int px=sx;px<=x2;px++)
			for(int py=y1;py<=sy;py++)
				Min(f[x1][py][px][y2],val+G(x1,y1,px,py-1)+G(px+1,py,x2,y2));
		for(int px=sx;px<=x2;px++)
			for(int py=sy;py<=y2;py++)
				Min(f[x1][y1][px][py],val+G(x1,py+1,px,y2)+G(px+1,y1,x2,py));
		for(int px=x1;px<=sx;px++)
			for(int py=y1;py<=sy;py++)
				Min(f[px][py][x2][y2],val+G(x1,py,px-1,y2)+G(px,y1,x2,py-1));
		for(int px=x1;px<=sx;px++)
			for(int py=sy;py<=y2;py++)
				Min(f[px][y1][x2][py],val+G(x1,y1,px-1,py)+G(px,py+1,x2,y2));
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 14208