akhauriyash/Code-Regression huggingface dataset:
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#include <cmath>
#include <stack>
#include <iomanip>
#include <tuple>
#include <functional>
#include <cfloat>
#include <map>

#define int long long
#define CONTAINS(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ARY_SORT(a, size) sort((a), (a)+(size))
#define MAX(a,b) (((a) > (b)) ? (a) : (b))
#define MIN(a,b) (((a) < (b)) ? (a) : (b))
#define REMOVE(v,a) (v.erase(remove((v).begin(), (v).end(), (a)), (v).end()))
#define REVERSE(v) (reverse((v).begin(), (v).end()))
#define LOWER_BOUND(v,a) (lower_bound((v).begin(), (v).end(), (a)))
#define UPPER_BOUND(v,a) (upper_bound((v).begin(), (v).end(), (a)))
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define CONTAINS_MAP(m, a) (m).find((a)) != m.end()
using namespace std;

int N;
int a[200001];

signed main()
{
	cin >> N;
	REP(i, N)
	{
		int p;
		cin >> p;
		a[p] = i;
	}

	int max = 0;
	int b = 0;
	for (int i = 1; i <= N - 1; i++)
	{
		if (a[i] < a[i + 1])
		{
			b++;
		}
		else
		{
			max = MAX(max, b);
			b = 0;
		}
	}
	max = MAX(max, b);

	cout << (N - (max + 1)) << endl;
}







Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define r(i,n) for(int i=0;i<n;i++)
int n,m,x,y,ch;
vector<int>v[100001],t,tt,vv[100001];
bool b[100001];
void dfs(int p){
    b[p]=1;
    r(i,v[p].size()){
        if(!b[v[p][i]]){
            dfs(v[p][i]);
        }
    }
    t.push_back(p);
}
void dfs2(int p){
    b[p]=1;
    r(i,vv[p].size()){
        if(!b[vv[p][i]]){
            dfs2(vv[p][i]);
        }
    }
    tt.push_back(p);
}
main(){
  cin>>n>>m;
  while(m--){
    cin>>x>>y;
    v[x].push_back(y);
    vv[y].push_back(x);
  }
  r(i,n)if(!b[i+1])dfs(i+1);
  memset(b,0,sizeof(b));
  r(i,n)if(!b[i+1])dfs2(i+1);
  r(i,n)cout<<t[n-i-1]<<endl;
  r(i,n)if(t[i]!=tt[n-i-1])ch=1;
  cout<<ch<<endl;
}

Measured memory_bytes: 9192
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

INF = float('inf')
from math import floor
def solve():
    yen = 100
    x = II()
    for i in range(5000):
        yen = floor(yen * 1.01)
        if yen >= x:
            print(i+1)
            break

if __name__ == '__main__':
    solve()


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

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

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF 1e16
#define mod 1000000007

#define SQ 4

ll N,M;
ll A[100010],B[100010];
ll X[100110];
ll add[SQ][100010];

int main(){
  cin>>N>>M;
  rep(i,M){
    cin>>A[i]>>B[i];
  }
  rep(i,M){
    if(B[i]>=SQ){
      ll s=B[i]-A[i];
      for(;s<=N;s+=B[i]){
        X[min(s+1,N+5)]+=1;
        X[min(s+B[i],N+5)]-=B[i];
        X[min(s+B[i]+1,N+5)]+=B[i]-1;
      }
      s=B[i]-A[i];
      if(B[i]-A[i]!=1){
        ll t=(A[i]+1)%B[i];
        X[1]+=t;
        X[2]-=t-1;
        X[min(s,N+5)]-=B[i];
        X[min(s+1,N+5)]+=B[i]-1;
      }
    }else if(B[i]<SQ){
      for(ll j=1;j<=B[i];j++){
        add[B[i]][j%B[i]]+=(A[i]+j)%B[i];
      }
    }
  }
  rep(i,N+3)X[i+1]+=X[i];
  rep(i,N+3)X[i+1]+=X[i];
  repl(i,1,N+1){
    repl(k,1,SQ)X[i]+=add[k][i%k];
  }
  repl(i,1,N+1)cout<<X[i]<<endl;

  return 0;
}



Measured memory_bytes: 5304
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define NDEBUG
#define eprintf(...) do {} while (0)
#endif
#include<cassert>

using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

int N;
int A[100011];

void MAIN() {
    scanf("%d", &N);
    REP (i, N) scanf("%d", A+i);

    LL ans = 0;
    int last = 0;
    REP (i, N) {
	int p = __lg(A[i]), q = 0;
	if (A[i] != 1<<p) {
	    q = 1;
	} 

	ans += p + q - min(last, p+q);
	if (p+q <= last) last = p;
	else last = p+q;
    }

    printf("%lld\n", ans);
}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}



Measured memory_bytes: 640
import java.util.*;
public class Main {

	public static class unionfind{
		int[] parent;
		int[] rank;
		int[] size;
		public unionfind(int n){
			this.parent = new int[n+1];
			this.rank = new int[n+1];
			this.size = new int[n+1];
			for(int i = 1; i <= n; i++) set(i);
		}
		public void set(int i) {
			parent[i] = i;
			rank[i] = 0;
			size[i] = 1;
		}
		public int find(int i) {
			if (i == parent[i])
				return parent[i];
			else
				return parent[i] = find(parent[i]);
		}
		public boolean same(int x, int y){
			return find(x) == find(y);
		}
		public void unite(int x, int y) {
			int xroot = find(x);
			int yroot = find(y);
			if(xroot == yroot)
				return;
			if(rank[xroot] > rank[yroot]) {
				parent[yroot] = xroot;
				size[xroot] += size[yroot];
			}
			else if(rank[xroot] < rank[yroot]) {
				parent[xroot] = yroot;
				size[yroot] += size[xroot];
			}
			else {
				parent[yroot] = xroot;
				size[xroot] += size[yroot];
				rank[xroot]++;
			}
		}
		public int get_size(int i) {
			return size[find(i)];
		}
		public int group_num() {
			Set<Integer> parents = new HashSet<>();
			for(int i = 1; i < this.parent.length; i++)
				parents.add(find(i));
			return parents.size();
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		unionfind u = new unionfind(N);
		for(int i = 0; i < M; i++)
			u.unite(sc.nextInt(), sc.nextInt());
		int ans = 0;
		for(int i = 0; i < N; i++)
			ans = Math.max(ans, u.get_size(i));
		System.out.println(ans);
	}

}


Measured memory_bytes: 61856
#include<iostream>
#include<stdio.h>
using namespace std;
int main(void) {
	int a;
	int b;
	int c = 0;
	int d;
	int i;
	scanf("%d", &a);

	for (i = 0; i <= a; i++) {
		b = 108 * i / 100;
			if (a == b) {
				c = 1;
			break;
		}
	}

	if (c == 1) {
		printf("%d",i);
	}
	else {
		printf(":(");
	}
	return 0;
}

Measured memory_bytes: 888
#include "bits/stdc++.h"
using namespace std;
typedef long long li;

li c;
li calc(vector<li> xs, vector<li> vs) {
    li n = xs.size();
    vector<li> acc(n + 1);
    for (int i = 0; i < n; ++i) {
        acc[i + 1] = acc[i] + vs[i];
    }
    vector<li> single(n + 1);
    for (int i = 0; i < n; ++i) {
        single[i + 1] = acc[i + 1] - xs[i];
    }

    li ans = 0;
    li max_double = 0;
    for (int su = n; su >= 0 ; --su) {
        li d_profit = acc[n] - acc[su] - (su == n ? 0 : (c - xs[su])) * 2;
        max_double = max(max_double, d_profit);
        li s_profit = single[su];
        li profit = s_profit + max_double;
        ans = max(ans, profit);
    }
    return ans;
}

int main() {
    li n;
    cin >> n >> c;

    vector<li> xs(n), vs(n);
    for (int i = 0; i < n; ++i) {
        cin >> xs[i] >> vs[i];
    }

    li ans = 0;
    ans = max(ans, calc(xs, vs));
    vector<li> rxs, rvs;
    for (int j = n-1; j >= 0 ; --j) {
        rxs.push_back(c - xs[j]);
        rvs.push_back(vs[j]);
    }

    ans = max(ans, calc(rxs, rvs));

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


Measured memory_bytes: 6464
#include <iostream>
#include <math.h>
#include <numeric>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <queue>
#include <queue>
#include <stack> 
#include <sstream>
#include <set>

typedef  long long ll;
const int dx[8]={1,0,-1,0,1,-1,-1,1};
const int dy[8]={0,1,0,-1,1,1,-1,-1};
const int dr[4] = {-1, 0, 1, 0};
const int dc[4] = { 0, 1, 0,-1};
const int INF = 1e9;
#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define SORT(a) sort(a.begin(),a.end())
#define REVERSE(a) reverse(a.begin(),a.end())
int guki (int a){
    if(a%2==0) return 0;
    else return 1;
}
int gcd(int a, int b){
    if(a%b==0){
        return b;
    }else{
        return (gcd(b,a%b));
    }
}
int lcm(int a, int b){
    int x = gcd(a,b);
    return (a*b/x);
}

using namespace std;
// now

struct UnionFind {
    vector<int> d;
    UnionFind(int n=0) : d(n,-1){}
    int Find (int x){//根の番号を探す
        if(d[x] < 0) return x;
        return d[x] = Find(d[x]);
    }
    bool unite (int x, int y){
        x = Find(x); y = Find(y);
        if(x == y ) return false;
        if(d[x] < d[y]){
            swap(x,y);
        }
        d[x] += d[y];
        d[y] = x;
        return true;
    } 

    bool same(int x, int y){
        return Find(x) == Find(y);
    }
    int size(int x) {
        return (-d[Find(x)]);
    }
};


ll nCr (ll n, ll r){
    ll ans = 1;
    for(ll i = n ; i > n-r ; i --){
        ans *= i;
    }
    for(ll i = 1 ; i<= r; i ++){
        ans /= i;
    }
    return ans ;
}

int nPr (int n,int r){
    int ans = 1;
    for(int i = n ; i > n-r ; i --){
        ans *= i;
    }
    return ans ;
}
 ll modd = 1e9+ 7;
ll wa (ll n,ll mi, ll ma){
    ll ans  = n * (mi+ma) /2;
    return ans;
}


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

    vector<int> vm(n),v(n);
    REP(i,n){
        cin >> v[i];
        vm[i] = 0;
    }
    int a,b;
    REP(i,m){
        cin >> a >> b;
        a--;b--;
        vm[a] = max(vm[a], v[b]);
        vm[b] = max(vm[b], v[a]);
    }
    int ans = 0;
    REP(i,n){
        bool fl = true;
        if(v[i] <= vm[i]) fl = false;
        if(fl) ans++;
    }
    cout << ans <<endl;
}





Measured memory_bytes: 4028
#include<iostream>
#include<cstdio>
#include<string>
#include<math.h>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<map>
#include<numeric>
#include<stack>
#include<queue>
#include<functional>
#include<cassert>
#include<set>
#define rep(a,b) for(int a=0;a<b;++a)
#define REP(a,b,c,d) for(int a=b;a<c;a+=d)
#define yes cout<<"Yes"<<endl
#define no cout<<"No"<<endl
#define mod 1000000007
using namespace std;
//using ll = long long;
//using p_i = pair<int, int>;
int main() {
    int N;cin>>N;
    int Mid=0;
    vector<int> A(N);
    rep(i,N){
        cin>>A[i];
        if(A[i]%2==0)++Mid;
    }
    cout<<pow(3,N)-pow(2,Mid)<<endl;
}

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

import sys
sys.setrecursionlimit(300000)


def solve(A: int, B: int):
    def gcd(a, b):
        return a if b == 0 else gcd(b, a % b)
    ret = A * B // gcd(A, B)
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    solve(A, B)

if __name__ == '__main__':
    main()


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

using namespace std;

typedef long long int ll;

ll maxPossiblePoint(vector<int> point[] , int day)
{
    ll dp[day][3] = {0};
    dp[0][0] = point[0][0];
    dp[0][1] = point[0][1];
    dp[0][2] = point[0][2];

    for(int i=1 ; i<day ; i++)
    {
        dp[i][0] = point[i][0] + max(dp[i-1][1] , dp[i-1][2]);
        dp[i][1] = point[i][1] + max(dp[i-1][0] , dp[i-1][2]);
        dp[i][2] = point[i][2] + max(dp[i-1][0] , dp[i-1][1]);
    }
    
    //return 0;
    return max(dp[day-1][0] , max(dp[day-1][1] , dp[day-1][2]) );
}

int main() 
{
    int day;
    cin >> day;
    
    vector<int> point[day];
    for(int i=0 ; i<day ; i++)
    {
        point[i].resize(3);
        cin >> point[i][0] >> point[i][1] >> point[i][2];
    }

    cout << maxPossiblePoint(point , day);
    return 0;
}


Measured memory_bytes: 8064
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <set>

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef pair<int, int> PII;
typedef long long LL;
#define ALL(a) (a).begin(),(a).end()
#define PB push_back
#define MP make_pair
#define SORT(c) sort((c).begin(),(c).end())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define IFOR(v,it) for(VI::iterator it=(v).begin();it!=(v).end();++it)

int N, M;
int solve(vector<vector<bool> >& edge, bool visited[9], int start) {
  bool allVisited = true;
  int count = 0;
  REP(i, N) {
    if (!visited[i]) {
      allVisited = false;
      if (edge[start][i]) {
        visited[i] = true;
        count += solve(edge, visited, i);
        visited[i] = false;
      }
    }
  }
  if (allVisited)
    return 1;
  return count;
}

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

  vector<vector<bool> > edge;
  REP(i, N) {
    vector<bool> v(N, false);
    edge.PB(v);
  }
  REP(i, M) {
    int a, b;
    cin >> a >> b;
    edge[a-1][b-1] = true;
    edge[b-1][a-1] = true;
  }
  bool visited[8];
  fill(visited, visited + 8, false);
  visited[0] = true;
  cout << solve(edge, visited, 0) << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (long long i = j; i < (long long)(n); i++)
#define _GLIBCXX_DEBUG
#define MOD 1000000007
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; }
//name[i][j]-> vvl name(i,vl(j))
//map<int,int>mp
//余りを切り上げる =>  (a + b - 1) / b 

signed main(){
	int n; cin>>n;
	vi a(n);
	int total=0;
	rep(i,0,n){
		int b; cin>>b;
		a[i]=b;
		total^=b;
	}
	rep(i,0,n){
		cout<<(total^a[i])<<" ";
	}
	
	return 0;
}

Measured memory_bytes: 3928
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;

int main() {
  int m,f,r;
  while(true) {
    char ans;
    cin >> m >> f >> r;
    if(m==-1&&f==-1&&r==-1) break;
    if(m==-1||f==-1) ans = 'F';
    else {
      int sum = m + f;
      if(80 <= sum) ans = 'A';
      if(65 <= sum && sum < 80) ans = 'B';
      if(50 <= sum && sum < 65) ans = 'C';
      if(30 <= sum && sum < 50){
        ans = 'D';
        if(50 <= r) ans = 'C';
      }
      if(sum < 30) ans = 'F';
    }
    cout << ans << endl;
  }
  return 0;
}


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

int main(){
    ll N,M;
    cin >> N >> M;
    ll L;
    ll R;
    ll left = 1, right = N + 1;
    
    for(ll i = 0; i < M; i++){
        cin >> L >> R;
        
        if(left < L)    left = L;
        if(right > R)   right = R;
    }
  	ll ans = right - left + 1;
  	if(ans < 0) ans = 0;
    cout << ans << "\n";
    return 0;
} 


Measured memory_bytes: 256
from math import factorial

n=int(input())

print(factorial(n)//factorial(n-2)//2-n//2)

m = (n//2)*2
for i in range(1,n+1):
    for j in range(i+1,n+1):
        if i+j != m+1:
            print(i,end=' ')
            print(j)

Measured memory_bytes: 45544
#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(a) (a).begin(),(a).end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF=1e9;
double EPS=1e-10;
vector<P> rotate(vector<P>V){
      int sw=INF,sh=INF,mw=-INF,mh=-INF;
      REP(i,V.size()){
            sw=min(sw,V[i].first);sh=min(sh,V[i].second);
            mw=max(mw,V[i].first);mh=max(mh,V[i].second);
      }
      int w=mw-sw,h=mh-sh;
      //cout<<w<<" "<<h<<endl;
      vector<P> res;
      REP(i,V.size()){
            res.PB(MP(h-V[i].second,V[i].first));
      }
      return res;
}
vector<P> rvrs(vector<P>V){
      reverse(ALL(V));
      return V;
}
bool ok(vector<P>a,vector<P>b){
      if(a.size()!=b.size())return false;
      REP(i,a.size()){
            if(a[i].first!=b[i].first)return false;
            if(a[i].second!=b[i].second)return false;
      }
      return true;
}
int main(){
      int n,m,x,y;
      while(cin>>n&&n){
            vector<P>V1[8];
            vector<P>V2[n];
            cin>>m;
            vector<P>A;
            int sw=INF,sh=INF;
            REP(i,m){
                  cin>>x>>y;
                  A.PB(MP(x,y));
                  sw=min(sw,x);sh=min(sh,y);
            }
            REP(i,A.size()){
                  A[i].first-=sw;
                  A[i].second-=sh;
            }
            //cout<<sw<<" "<<sh<<endl;
            REP(i,2){
                  REP(j,4){
                        V1[i*4+j]=A;
                        A=rotate(A);
                  }
                  A=rvrs(A);
            }
            REP(i,n){
                  cin>>m;
                  int sw=INF,sh=INF;
                  REP(j,m){
                        cin>>x>>y;
                        V2[i].PB(MP(x,y));
                        sw=min(sw,x);sh=min(sh,y);
                  }
                  REP(j,V2[i].size()){
                        V2[i][j].first-=sw;
                        V2[i][j].second-=sh;
                  }
            }
            /*REP(i,8){
                  REP(j,V1[i].size())cout<<V1[i][j].first<<","<<V1[i][j].second<<" ";
                  cout<<endl;
            }*/
            int ans=0;
            REP(i,n){
                  REP(j,8)if(ok(V2[i],V1[j])){
                        cout<<i+1<<endl;
                  }
            }
            cout<<"+++++"<<endl;
            //cout<<ans<<endl;
      }
}

Measured memory_bytes: 1208
str = input()
q = int(input())
for i in range(q):
  lst = list(input().split())
  a = int(lst[1])
  b = int(lst[2])
  if lst[0] == "print":
    print(str[a:b+1])
  elif lst[0] == "reverse":
    s = str[a:b+1]
    ss = "".join(list(reversed(s))) #文字列はイミュータブル(更新不可)なので元のオブジェクトを書き換えることはできない
    t1 = str[0:a]
    t2 = str[a:b+1]
    t3 = str[b+1:len(str)]
    str = t1 + ss + t3
  elif lst[0] == "replace":
    t1 = str[0:a]
    t2 = str[a:b+1]
    t3 = str[b+1:len(str)]
    str = t1 + lst[3] + t3
  else:
    pass



Measured memory_bytes: 5616
import java.util.*;
class Main{
  public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    int k = sc.nextInt();
    if(k<=9){
      pl(k+"");
    }else{
      long count=9;
      for(int ij=2;;ij++){
        long l=0;
        for(int i=1;i<=9&&count<k;i++){
          long ll[] = deside(i,2,ij,count,k);
          count = ll[1];l=i*ten(ij)+ll[0];
        }
        if(count==k){
          pl(l+"");
          break;
        }
      }
    }
  }

  public static long[] deside(int b,int n,int max,long count,int k){
    for(int i=max(b-1,0);i<=b+1&&i<=9;i++){
      if(n==max){
        count++;
        if(count==k){
          return new long[]{i,k};
        }
        if(i==b+1||i==9){
          return new long[]{0,count};
        }
      }else{
        long lo[] = deside(i,n+1,max,count,k);
        count = lo[1];
        if(count==k){
          lo[0]=i*ten(max-n+1)+lo[0];
          return lo;
        }
        if(i==b+1||i==9){
          return lo;
        }
      }
    }
    return new long[]{0,0};
  }

  public static int getNum(long a,int n){
    return (int)(a/ten(n))%10;
  }

  public static int max(int a,int b){
    if(a>b){return a;}
    else{return b;}
  }

  public static long ten(int n){
    long a=1;
    for(int i=1;i<n;i++){
      a*=10;
    }
    return a;
  }

  public static void pr(String str){
    System.out.print(str);
  }
  public static void pl(String str){
    System.out.println(str);
  }
}


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

#define REP(i, x, n) for (int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x.size())
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define uniq(x) x.erase(unique(x.begin(), x.end()), x.end())
#define F first
#define S second
#define mp make_pair
#define eb emplace_back
#define pii pair<int, int>
#define pll pair<ll, ll>

using namespace std;

typedef long long ll;

/* --- INFやMODの値が適切か確認する --- */
// const int INF = 1 << 30;
// const ll INF = 1LL << 60;
// const ll MOD = 1000000007;

int main() {
  ll n;
  cin >> n;

  ll cnt = 0;
  ll sum = 0;
  rep(i, n) {
    ll d, c;
    cin >> d >> c;
    cnt += c;
    sum += d * c;
  }

  cout << cnt - 1 + (sum - 1) / 9 << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define SORT(x) sort(x.begin(),x.end(),greater<int>())
#define ALL(x) x.begin(),x.end()
#define rep(i, n) for(int i = 0; i < n; i++)
#define reps(i, m, n) for(int i = m; i < n; i++)
#define repr(i, m, n) for(int i = m; i >= n; i--)
#define INF 1000000000000000003 //1000000007
#define PI (acos(-1))
#define MOD 1000000007
using namespace std;
typedef long long ll;



void Main(){

  int N;
  cin>>N;

  int a[N];

  ll x=0;

  rep(i,N){
    cin>>a[i];
    x+=a[i];
  }

  ll ans=INF;

  rep(i,N-1){
    x-=2*a[N-1-i];
    ans=min(ans,abs(x));
  }

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

//-----------------------------------
int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  Main();
}
//-----------------------------------


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <cstdlib>
#include <queue>
#include <stack>

using namespace std;

int main(){
	int cnt[4]={};
	for(int i=0;i<6;i++){
		int a;
		cin>>a;
		cnt[a-1]++;
	}
	int cnt2=0;
	int cnt3=0;
	for(int i=0;i<4;i++){
		if(cnt[i]==2)cnt2++;
		if(cnt[i]==1)cnt3++;
	}
	if(cnt2==2&&cnt3==2){
		cout<<"YES"<<endl;
	}
	else{
		cout<<"NO"<<endl;
	}
	
	return 0;
}


Measured memory_bytes: 256
#include <iostream>

int main() {

    int A, B, C, X;
    std::cin >> A >> B >> C >> X;

    int counter = 0;

    for (int a=0; a<=A; a++)
        for (int b=0; b<=B; b++)
            for (int c=0; c<=C; c++)
                if (500 * a + 100 * b + 50 * c == X) counter++;

    std::cout << counter << std::endl;

    return 0;

}



Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int main()
{
int a[4][3][10];
int b,f,r,v;
int i,j,k;
int n;
for(i=0;i<4;i++) for(j=0;j<3;j++) for(k=0;k<10;k++) a[i][j][k]=0;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf(" %d %d %d %d",&b,&f,&r,&v);
a[b-1][f-1][r-1]=a[b-1][f-1][r-1]+v;
}
for(i=0;i<4;i++){
for(j=0;j<3;j++){
for(k=0;k<10;k++){
printf(" %d",a[i][j][k]);
}
printf("\n");
}
if(i<3) printf("####################\n");
}
return 0;
}

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

typedef long long                   ll;
typedef long double                 ld;
typedef pair<ll,ll>                 pll;
typedef pair<ld,ld>                 pld;


#define all(x)          (x).begin(),(x).end()
#define Sort(x)         sort(all(x))
#define sep             ' '
#define endl            '\n'
#define tab             '\t'
#define X               first
#define Y               second
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("in.txt" , "r" , stdin) ; freopen("out.txt" , "w" , stdout);
#define set_random      mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll MOD = 1e9 + 7,
         MAXN= 3e3+10,
         INF=1e18;
ll dp[MAXN][MAXN];
string s,t;
vector<char>ans;
int main()
{
    fast_io;
    cin >> s >> t;
    ll n =s.size();
    ll m=t.size();
    for (ll i = 1; i <= n; i++) {
        for (ll j = 1; j <= m; j++) {
            dp[i][j] = max({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]+(s[i-1]==t[j-1])});
            }
    }
    //cout<<dp[n][m];
   ll i = n, j = m;
   while (i&&j) {
       if (s[i-1] == t[j-1]) {
           ans.push_back(s[i-1]);
           i--;
           j--;
           continue;
       }
       if (dp[i-1][j] > dp[i][j-1]) i--;
       else  j--;
   }
    for(ll i=ans.size()-1;i>=0;i--){
        cout<<ans[i];
    }
    //cout<<ans.size();

    return 0;
}


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

int main(){
    int n;
    cin >> n;
    vector<int> L(n);
    rep(i,n) cin >> L.at(i);
    L.push_back(INF);
    sort(L.begin(),L.end());
    int ans = 0;
    for(int i = 0; i < n;i++){
        for(int j = i+1; j < n;j++){
            int l = j;
            int r = n;
            while(l + 1 < r){
                int m = (l+r)/2;
                if(L.at(m) < L.at(i) + L.at(j)) l = m;
                else r = m;
            }
            ans += (l - j);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3644
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
typedef  vector<int> vi;
typedef  pair<int,int> pii;
typedef  pair<int,string> pis;
double pi=3.1415926535898;
#define speed      ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
#define lop(i,n)   for(int i=0;i<int(n);i++)
#define rep(i,a,b) for(int i=a;i<=int(b);i++)
#define rng(i,a,b) for(int i=a;i>=int(b);i--)
#define ms(x,a)    memset(x,a,sizeof(x))
#define all(x)     (x).begin(),(x).end()
#define sz(x)      int(x.size())
#define pb         push_back
#define r0         return 0;
#define CC         continue;
#define bb(x)      cerr<< x <<endl;
#define F          first
#define S          second       //  __builtin_popcount;
//freopen("output.txt","w",stdout),freopen("input.txt","r",stdin);
const ll M  = 1e9+7 ;
const int N = 100100;
const int inf = INT_MAX;
const double eps = 1e-7;
const ll iinf = -1e18 ;
//////////////////////    Hi    ^_^  hack me if you can :P
 
ll n, a[100100];
ll lo, hi, md;
 
ll A,B;
ll D ;
bool ok(ll x)
{
    ll cost = 0LL;
    ll dam = x*B;
    lop(i,n) {
        if (a[i]>dam) {
            cost += (a[i]-dam + D - 1LL) / D;
        }
    }
    return cost <= x;
}
 
int main()
{
    //speed;
    cin >> n >> A >> B ;
    D = A - B ;
    lop(i,n)
    {
        cin >> a[i] ;
    }
    lo = 0;
    hi = 1e9+100000;
    while (lo < hi)
    {
 
        md = lo + (hi - lo) / 2LL;
 
        if (ok(md))
        {
            hi = md;
        }
        else
        {
            lo = md +1LL;
        }
    }
    cout << lo << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=998244353;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

int l,r,k;

int main(){
	cin>>k>>l>>r;
	cout<<(r/k-(l-1)/k>0?"OK":"NG")<<endl;
}

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

int main(){
  string s;
  int n,k;
  cin>>n>>k;
  cin>>s;
  int st,co;
  vector<int> array(1,0);
  st=0;
  co=0;
  for(int i=0;i<n;i++){
    if(s[i]=='0'){
      st++;
      if(co>0){
	array.push_back(co);
	co=0;
      }
  }
   else if(s[i]=='1'){
      co++;
      if(st>0){
	array.push_back(st);
	st=0;
      }
  }
  }
  if(st<co) st=co;
  array.push_back(st);
  int size;
  size=(int)array.size()-1;
  int buf;
  int k2=k*2+1;
  int ans_num=size-2*k;
  vector<int> ans(size);
  int max=0;
  if(ans_num>0){
  for(int i=0;i<ans_num;i++){
    buf=0;
    for(int j=0;j<k2;j++){
      buf+=array[i+j+1];
      //      printf("array[%d]=%d\n",i+j+1,array[i+j+1]);
    }
    ans[i]=buf;
    //    printf("ans[%d]=%d\n",i,ans[i]);
  }
  //  int max=0;
  int ans_tmp=0;
  //最初が0なら奇数番のansのmax
  if(s[0]=='0'){
    for(int i=0;i<ans_num;i++){
      if(i%2==1){
	if(max<ans[i]) max=ans[i];
      }}
    ans_tmp=ans[0]-array[k2];
    if(max<ans[0]) max=ans_tmp;

  }
  if(s[0]=='1'){
    for(int i=0;i<ans_num;i++){
      if(i%2==0){
	if(max<ans[i]) max=ans[i];
      }}}
  //  cout<<ans[ans_num-1]<<endl;
  if(s[n-1]=='0') {
    ans[ans_num-1]-=array[ans_num];
    if(max<ans[ans_num-1]) max=ans[ans_num-1];
  }}
  else max=n;
  if(n==2 ||n==1) max=n;
  /*    cout<<"array"<<endl;
    for(int i=0;i<size+1;i++){
    cout<<array[i]<<endl;
  }
  cout<<"ans"<<endl;
  for(int i=0;i<ans_num;i++){
    cout<<ans[i]<<endl;
    }*/
  cout<<max<<endl;
  return 0;
}


Measured memory_bytes: 1272
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(v) v.begin(), v.end()
#define F first
#define S second
#define INF 1000000000000
#define MOD 10000007
typedef long long ll;
//
int main(){
   int n;cin>>n;
   int ans=n+n*n+n*n*n;
   cout<<ans<<endl;
}

Measured memory_bytes: 3596
package main

import (
	"fmt"
)

func main() {
	var H, W int
	fmt.Scan(&H, &W)
	c := make([]string, H)
	for i := 0; i < H; i++ {
		fmt.Scan(&c[i])
	}
	var ma [310][310]int
	var dp [310][310]int
	var ans int
	for n := 0; n < W-1; n++ {
		for i := 0; i < H; i++ {
			for j := 0; j < H; j++ {
				if c[i][n] == c[j][n+1] {
					ma[i+1][j+1] = ma[i][j] + 1
				} else {
					ma[i+1][j+1] = ma[i][j]
				}
			}
		}
		for i := 0; i < H; i++ {
			for j := 0; j < H; j++ {
				dp[i+1][j+1] = min(dp[i][j+1], dp[i+1][j]) + ma[i+1][j+1]
			}
		}
		ans += dp[H][H]
	}
	fmt.Println(ans)
}

func min(a ...int) int {
	r := a[0]
	for i := 0; i < len(a); i++ {
		if r > a[i] {
			r = a[i]
		}
	}
	return r
}


Measured memory_bytes: 2176
#include<iostream>
#include<vector>
#include<queue>
#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() {
  int s,w;
  cin >> s >> w;
  
  if ( w >= s ) {
    cout << "unsafe" << endl;
  }else {
    cout << "safe" << endl;
  }
  return 0;
}


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

int main(){
    int S, h, m, s;
    cin >> S;
    h = S/3600;
    m = (S%3600)/60;
    s = (S%3600)%60;
    cout << h <<':' << m << ':' << s << endl;
    return 0;
}

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

int main(){
	int n, k;
	char *s;
	
	scanf("%d", &n);
	s = malloc(sizeof(char) * (long)n);
	scanf("%s%d", s, &k);
	char a = s[k - 1];
	for(int i = 0; i < n; ++i){
		printf("%c", a == s[i] ? a : '*');
	}
	printf("\n");
	free(s);
	return 0;
}


Measured memory_bytes: 128
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int A = sc.nextInt();
		int B = sc.nextInt();
		
		System.out.println(Math.min(B, A * N));
	}
}


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


int main(){
        int N, K;
        std::cin >> N  >> K;
        std::vector<int> heights(N);
        for(int i = 0; i< N ; i++){
            std::cin >> heights[i] ; 
            // std::cout << heights[i] << std::endl;
        }
        // std::cout << heights[0] << "\n";
        // std::cout << heights[1] << "\n";


        // Writing the dp funcction 
        const int INF = 10e9 + 5 ;

        std::vector<int> dp(N,INF);
        dp[0] = 0;
        for(int i=0; i< N; i++){
            for(int k = 1; k <= K ; k++){
                for(int j :{i+k}){
                    if(j < N ){
                        dp[j] =std::min(dp[j], dp[i] + abs(heights[j] -heights[i]));

                    }
            }
        }   

            }
            
        // std::vector<int> dp(n, INF);
    //      dp[0] = 0;
    // for(int i = 0; i < n; ++i) {
    //     for(int j : {i + 1, i + 2}) {
    //         if(j < n) {
    //             dp[j] = min(dp[j], dp[i] + abs(h[i] - h[j]));
    //         }
    //     }
    // }
        std::cout << dp[N-1] << std::endl;


        return 0;


}

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

int main()
{
	string s;
	cin >> s;
	cout << s[0];
	cout << s.size() - 2;
	cout << s[s.size() - 1] << endl;
	return 0;
}

Measured memory_bytes: 256
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main(){

    input!{
        n: usize,
        s: chars,
        t: chars,
    }

    let mut ans: String = String::new();
    for i in 0..n{
        ans += &s[i].to_string();
        ans += &t[i].to_string();
    }

    println!("{}", ans);

}

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

using namespace std;
main(){
	int a,b;
	while(cin >> a >> b){
	int s=1;
	int g=0;
	int d=a+b;
	while(d >= 1){
		d=d/10;
		g=g+1;
		}
		printf("%d\n",g);
	}
}


Measured memory_bytes: 3120
#include <iostream>
#include <map>
#include<unordered_map>
using namespace std;

int main()
{   int a,b,c;
    cin>>a>>b>>c;
    if((a==b &&b!=c) ||(a==c&&a!=b)||(b==c&&a!=b) )cout<<"Yes"<<endl;
    else cout<<"No"<<endl;


    return 0;
}


Measured memory_bytes: 256
N, M = map(int, input().split())
Edges = []
for i in range(M):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    c = -c
    Edges.append([a, b, c])

dist = [float('inf')] * N
dist[0] = 0

for i in range(N):
    for fr, to, cost in Edges:
        if (dist[fr] != float('inf')) and (dist[to] > dist[fr] + cost):
            dist[to] = dist[fr] + cost
            if (i == N - 1) & (to == N - 1):
                print('inf')
                exit()

print(-dist[-1])


Measured memory_bytes: 3416
def no(x, y, z, k):
    return ([y, z, k] == [1, 2, 3]) or ([y, z, k] == [2, 1, 3]) or ([y, z, k] == [1, 3, 2]) or ([x, z, k] == [1, 2, 3]) or ([x, y, k] == [1, 2, 3])

MOD = 10**9 + 7
n = int(input())
dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(n + 1)]
dp[0][0][0][0] = 1
for i in range(n):
    for x in range(4):
        for y in range(4):
            for z in range(4):
                for k in range(4):
                    if not no(x, y, z, k):
                        dp[i + 1][y][z][k] += dp[i][x][y][z]
                        dp[i + 1][y][z][k] %= MOD
ans = 0
for x in range(4):
    for y in range(4):
        for z in range(4):
            ans += dp[n][x][y][z]
            ans %= MOD
print(ans)

Measured memory_bytes: 3316
import sys

def main(argv):
    k = int(sys.stdin.readline().rstrip("\n"))
    if k < 10:
        return print(k)
    d = {i: [i] for i in range(10)}

    counter = 9
    n = 1
    while counter < k:
        next_d = {}
        candidates = d[0]
        candidates.extend(d[1])
        next_d[0] = sorted([c for c in set(candidates)])
        for i in range(1, 10):
            candidates = d[i - 1]
            candidates.extend(d[i])
            candidates.extend(d.get(i + 1, []))
            next_d[i] = sorted([i * (10 ** n) + c for c in set(candidates)])
            n_candidates = len(next_d[i])
            if (counter + n_candidates) >= k:
                print(next_d[i][k - counter - 1])
                counter += n_candidates
                break
            counter += n_candidates
        d = next_d
        n += 1
    return 0


if __name__ == "__main__":
    sys.exit(main(sys.argv))


Measured memory_bytes: 8204
N=int(input())
room=[[[0]*10 for _ in range(3)] for _ in range(4)]

for _ in range(N):
    b,f,r,v=map(int,input().split())
    room[b-1][f-1][r-1]+=v
    
for i in range(4):
    for j in range(3):
        for k in range(10):
            print(" {}".format(room[i][j][k]),end="")
        print()
    if i!=3:
        print("####################")


Measured memory_bytes: 5624
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int a,b;
  cin>>a>>b;
  int c=1;//未使用
  int d=0;//使用タップ数
  int e=a-1;//未使用増加数
  if(a>=b){
    if(b==1){//bが1なら拡張の必要なし?
      cout<<0;
      return 0;
    }
    cout<<1;
    return 0;
  }
  for(int i=0;i<20;i++){
    c+=e;
    d++;
    if(c>=b){
      break;
    }
  }
  cout<<d;
}
    

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int h, w, n;

pair<int, int> move(pair<int, int> p) {
  if (p.second % 2 == 0 && p.first < h - 1)
    p = make_pair(p.first + 1, p.second);
  else if (p.second % 2 == 0 && p.first == h - 1)
    p = make_pair(p.first, p.second + 1);
  else if (p.second % 2 != 0 && p.first > 0)
    p = make_pair(p.first - 1, p.second);
  else if (p.second % 2 != 0 && p.first == 0)
    p = make_pair(p.first, p.second + 1);

  return p;
}

int main() {
  cin >> h >> w >> n;

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

  vector<vector<int> > c(h, vector<int>(w));
  pair<int, int> now(0, 0);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < a[i]; j++) {
      c[now.first][now.second] = i + 1;
      now = move(now);
    }
  }

  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      cout << c[i][j] << " ";
    }
    cout << endl;
  }
}

Measured memory_bytes: 384
n, m = map(int, input().split())
S = [list(map(int, input().split())) for _ in range(m)]
d = 0
for i in range(0, 1000):
    if len(str(i)) == n:
        l = list(str(i))
        c = 0
        for j in range(m):
            if int(l[S[j][0] - 1]) == S[j][1]:
                c += 1
        if c == m:
            print(i)
            d = 1
            break
if d == 0:
    print(-1)

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <bitset>
#include <cassert>
#include <random>
using namespace std;
using ll = long long;


void chmax(int &a, int b) {
	a = max(a, b);
}

int main() {
	int n, t; cin >> n >> t;
	vector<int> a(n), b(n);
	for (int i = 0; i < n; i++) cin >> a[i] >> b[i];
	vector<vector<int>> dp1(n + 2, vector<int>(10000)), dp2(n + 2, vector<int>(10000));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < t; j++) {
			chmax(dp1[i + 1][j], dp1[i][j]);
			chmax(dp1[i + 1][j + a[i]], dp1[i][j] + b[i]);
		}
	}
	for (int i = n - 1; i >= 0; i--) {
		for (int j = 0; j < t; j++) {
			chmax(dp2[i][j], dp2[i + 1][j]);
			chmax(dp2[i][j + a[i]], dp2[i + 1][j] + b[i]);
		}
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < t; j++) {
			chmax(ans, dp1[i][j] + dp2[i + 1][t - 1 - j] + b[i]);
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 235136
#include<algorithm>
#include<cassert>
#include<cfloat>
#include<climits>
#include<cmath>
#include<cstring>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

using namespace std;

using lint = long long;
using P = pair<int, int>;
using LLP = pair<long long, long long>;

#define REP(i, x, n) for(int i = (x), i##_len = int(n) ; i < i##_len ; ++i)
#define rep(i, n) for(int i = 0, i##_len = int(n) ; i < i##_len ; ++i)
#define reps(i, n) for(int i = 1, i##_len = int(n) ; i <= i##_len ; ++i)
#define rrep(i, n) for(int i = int(n) - 1 ; i >= 0 ; --i)
#define rreps(i, n) for(int i = int(n) ; i > 0 ; --i)
#define SORT(x) sort((x).begin(), (x).end())
#define SORT_INV(x) sort((x).rbegin(), (x).rend())
#define TWINS(x) cout << ((x) ? "Yay!" : ":(") << endl

constexpr int IINF = (1 << 30) - 1;
constexpr long long LLINF = 1LL << 61;
constexpr double EPS = 1e-8;

constexpr int dx4[] = {1, 0, -1, 0}, dy4[] = {0, 1, 0, -1};
constexpr int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};

template<typename T>
bool chmax(T& a, T b, bool equal = false){
    if(a < b || equal && a == b){
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool chmin(T& a, T b, bool equal = false){
    if(b < a || equal && a == b){
        a = b;
        return true;
    }
    return false;
}

bool warshall_floyd(vector< vector<long long> >& cost){
    const int v = (int)cost.size();

    constexpr long long INF = 1LL << 61;

    for(int k = 0 ; k < v ; ++k){
        for(int i = 0 ; i < v ; ++i){
            for(int j = 0 ; j < v ; ++j){
                if(cost[i][k] < INF && cost[k][j] < INF){
                    cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
                }
            }
        }
    }

    for(int i = 0 ; i < v ; ++i){
        if(cost[i][i] < 0LL){
            return false;
        }
    }

    return true;
}

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

    int h, w;
    cin >> h >> w;

    vector< vector<lint> > c(10, vector<lint>(10));
    for(int i = 0 ; i < 10 ; ++i){
        for(int j = 0 ; j < 10 ; ++j){
            cin >> c[i][j];
        }
    }

    warshall_floyd(c);

    lint ans = 0;

    for(int i = 0 ; i < h ; ++i){
        for(int j = 0 ; j < w ; ++j){
            int a;
            cin >> a;
            if(a >= 0){
                ans += c[a][1];
            }
        }
    }

    cout << ans << endl;

    return 0;
}

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

using namespace std;

#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define repr(i,n) for(int i=(n);i>=0;--i)
const long long INF = 1LL<<60;
const long long MOD = 1e9+7;
int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);}
int lcm(int a,int b){return a/gcd(a,b)*b;}
void Yes(){cout<<"Yes"<<endl;}
void No(){cout<<"No"<<endl;}
void YN(bool b){cout<<(b?"Yes":"No")<<endl;}

int main(void){
  long long int n,k,i,j;

  string s;
  cin >> n >> s;
  
  int r = 0;
  int b = 0;
  for(auto ch: s){
    if(ch=='R'){
      r++;
    }
    else{
      b++;
    }
  }
  
  YN(r>b);
  return 0;
}




Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
using namespace std;
long long i,sum=1,n;
int main()
{
    cin>>n;
    for(i=1; i<=n; i++)
    {
        while(sum<=n)
        {
            sum*=2;
            if(sum>n)
            {
                cout<<sum/2<<endl;
                return 0;
            }
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <vector>
#include <math.h>
#include <queue>
#include <deque>
#include <map>
const int MOD = 1e9+7;
typedef long long ll;
using namespace std;


int main(){
	ll n, mini = 1e18;
	cin >> n;
	ll a[5];
	for (int i = 0; i < 5; i++){
		cin >> a[i];
		if (mini > a[i]) mini = a[i];
	}
	cout << 4 + (n+mini-1)/mini << endl;
 }



Measured memory_bytes: 256
import copy

def j(n):
    if n:print("Yes")
    else:print("No")
    exit(0)
rem = 10 ** 9 + 7

"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def iprow():
    return [int(i) for i in input().split()]
def ips():
    return (int(i) for i in input().split())
def ipmultiplerow(n):
    a = []
    for i in range(n):
        a.append(ip())
    return a
def printrow(a):
    for i in a:
        print(i)
a = input()
for i in range(len(a)):
    if i%2:
        if a[i] == "R":j(0)
    else:
        if a[i] == "L":j(0)
j(1)

Measured memory_bytes: 3700
#include <cstdio>
#include <cstdlib>
#include <algorithm>

int main(){
	long N,M;
	long E[100001];

	scanf("%ld %ld",&N,&M);

	for(long i=1;i<=N;i++) E[i] = 0;

	for(long i=0;i<M;i++){
		long a,b;
		scanf("%ld %ld",&a,&b);
		E[a]++;
		E[b]++;
	}

	bool exist = true;
	for(long i=1;i<=N;i++) if(E[i]%2!=0) exist = false;

	if(exist){
		printf("YES\n");
	}else{
		printf("NO\n");
	}

	return 0;
}


Measured memory_bytes: 1024
#include<iostream>
using namespace std;
int main(){
    int N;
    cin >> N;
    
    int A[N];
    for(int i = 0; i < N; i++){
        cin >> A[i];
    }
    
    int flag = 1;
    int count = 0;
    
    while(flag){
        flag = 0;
        for(int j = (N - 1); j > 0; j--){
            if(A[j] < A[j - 1]){
                int B = A[j - 1];
                A[j - 1] = A[j];
                A[j] = B;
                count++;
                flag = 1;
            }
        }
    }
    
    for(int i = 0; i < (N - 1); i++){
        cout << A[i] << " ";
    }   
    cout << A[N - 1] << endl;
    cout << count << endl;
}


Measured memory_bytes: 3104
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std ;

typedef long long ll ;
#define rep (i , n ) for ( int i =0; i < n ; i++)
#define _sort(arg) sort(begin(arg), end(arg))
#define MOD 1000000007
#define pb push_back
#define DEBUG(x) cout << #x << ": " << x << endl;

/*
__attribute__((constructor))
void initial()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);
}
*/

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

	int N;
	
	cin >> N;

	int a[N];

	float sum = 0;

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

	//sum += 0.5;

	int bb = 0;
	if (sum >= 0)
	{
		bb = (sum / N + 0.5);
	}
	else
	{
		bb = (sum / N - 0.5);
	}
	
	int ret = 0;

	for (int i = 0; i < N; i++)
	{
		ret += pow((a[i] - bb), 2);
	}

	cout << ret << endl;

	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define rep(i, n) repd(i, 0, n)

using namespace std;

namespace mp = boost::multiprecision;

using ll = long long;
using Bint = mp::cpp_int;
ll mod = pow(10, 9) + 7;

int main() {
    // source
    int a, b;
    cin >> a >> b;
    int ans = (a + b) / 2;
    if ((a + b) % 2 == 1) {
        ans++;
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
int main()
{
	double a, b, h, m;
	scanf("%lf %lf %lf %lf", &a, &b, &h, &m);
	m += 60 * h;
	printf("%.20lf\n", sqrt(a * a + b * b - 2 * a * b * cos(2 * acos(-1) * (m / 12 / 60 - fmod(m, 60) / 60))));
	return 0;
}

Measured memory_bytes: 2624