akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100;

int a[MAXN], b[MAXN], c[MAXN], d[MAXN];
vector<int> edgesR[MAXN], edgesB[MAXN];
int pairR[MAXN], pairB[MAXN];

bool bio[MAXN];

bool dfs(int j)
{
	if (pairB[j] == -1)
		return true;
	bio[j] = true;
	for (int j2: edgesR[pairB[j]])
	{
//		cout<<"  "<<j<<' '<<j2<<'\n';
		if (!bio[j2] && dfs(j2))
		{
			pairB[j2] = pairB[j];
			pairR[pairB[j]] = j2;
			pairB[j] = -1;
			return true;
		}
	}
	return false;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, i, j;
	
	cin>>n;
	
	for (i = 0; i < n; ++i)
	{
		cin>>a[i]>>b[i];
		pairR[i] = -1;
	}
	
	for (i = 0; i < n; ++i)
	{
		cin>>c[i]>>d[i];
		pairB[i] = -1;
	}
	
	for (i = 0; i < n; ++i) for (j = 0; j < n; ++j) if (a[i] < c[j] && b[i] < d[j])
	{
		edgesR[i].push_back(j);
		edgesB[j].push_back(i);
	}
	
	int sol = 0;
	for (i = 0; i < n; ++i) if (pairR[i] == -1)
	{
		for (int j: edgesR[i])
		{
			memset(bio, false, sizeof bio);
			if (dfs(j))
			{
				pairR[i] = j;
				pairB[j] = i;
				++sol;
//				cout<<' '<<i<<' '<<j<<'\n';
				break;
			}
		}
//		cout<<i<<' '<<edgesR[i].size()<<' '<<pairR[i]<<'\n';
	}
	
	cout<<sol<<'\n';
}


Measured memory_bytes: 256
H, W = map(int, input().split())
hold = H * W

if H % 3 == 0 or W % 3 == 0:
    hold = 0
else:
    for h in range(H):
        if W % 2 == 0:
            Sa = h * W
            Sb = (H - h) * (W / 2)
            Sc = (H - h) * (W / 2)
            diff = max(Sa, Sb, Sc) - min(Sa, Sb, Sc)
            hold = min(hold, diff)
        else:
            Sa = h * W
            Sb = (H - h) * (( (W + 1) / 2) )
            Sc = (H - h) * (( (W - 1) / 2) )
            diff = max(Sa, Sb, Sc) - min(Sa, Sb, Sc)
            hold = min(hold, diff)

    for w in range(W):
        if H % 2 == 0:
            Sa = H * w
            Sb = (W - w) * (H / 2)
            Sc = (W - w) * (H / 2)
            diff = max(Sa, Sb, Sc) - min(Sa, Sb, Sc)
            hold = min(hold, diff)
        else:
            Sa = H * w
            Sb = (W - w) * ((H + 1) / 2)
            Sc = (W - w) * ((H - 1) / 2)
            diff = max(Sa, Sb, Sc) - min(Sa, Sb, Sc)
            hold = min(hold, diff)

hold = min(hold, H, W)

print(int(hold))


Measured memory_bytes: 3064
#include<iostream>
#include<cmath>
#include<vector>
#include<set>
#include<algorithm>
#include<tuple>
#include<utility>
#include<cctype>
#include<climits>
#include<map>
#include<queue>
#include<functional>

using namespace std;
template<class T> void chmax(T& a, T b) {if(a < b){a=b;}}
template<class T> void chmin(T& a, T b) {if(a > b){a=b;}}

#define REP(i,a,n) for(int i=a;i<n;++i)
#define RUP(a,b) ((a+b-1)/(b))
#define ENT "\n"
#define REV(v) reverse(v.begin(),v.end())
#define SRT(v) sort(v.begin(),v.end())
#define MOD 1000000007

typedef long long ll;
typedef tuple<int,int,bool> Tb;

int atcoder(){
    //入力
    int n;
    cin >> n;
    int p[11];
    int maxp = 0;
    int sum = 0;
    REP(i,0,n){
        cin >> p[i];
        sum += p[i];
        maxp = max(maxp , p[i]);
    }
    
    //処理
    
    //出力
    cout << sum-maxp/2 << ENT;
    return 0;
}

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


Measured memory_bytes: 256
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial


def divisor(n): #nの約数を全て求める
    i = 1
    table = set()
    while i * i <= n:
        if n%i == 0:
            table.add(i)
            table.add(n//i)
        i += 1
    table = list(table)
    table.sort(reverse=True)
    return table


def check(data, ele, num, k):
    plus, minus = 0, 0
    amari_dic = defaultdict(int)
    for i in range(num):
        now_num = data[i]
        amari = now_num % ele
        amari_dic[amari] += 1
        # if now_num >= ele:
        #     plus += now_num - ele
        # else:
        #     minus += ele - now_num

    amari_dic = sorted(amari_dic.items(), key=lambda x: x[0])

    for amari, kosuu in amari_dic:
        if amari == 0:
            continue
        ikeru = min((k - plus) // amari, kosuu)
        plus += ikeru * amari
        minus += (kosuu - ikeru) * (ele - amari)


    # print(ele, plus, minus, amari_dic)
    if max(plus, minus) <= k:
        return 1
    else:
        return 0

def main():

    num, k = map(int, input().split())
    data = list(map(int, input().split()))

    sum_num = sum(data)
    yakusuu_list = divisor(sum_num)

    # print(yakusuu_list)

    for ele in yakusuu_list:
        if check(data, ele, num, k):
            print(ele)
            sys.exit()







if __name__ == '__main__':
    main()


Measured memory_bytes: 44764
import sys

input = sys.stdin.read

def main(H, N, tmp):
    damage = tmp[::2]
    magic = tmp[1::2]
    DP = [float('inf')] * 20001
    DP[0] = 0
    for i in range(20001):
        for j in range(N):
            s = i - damage[j]
            if s >= 0:
                DP[i] = min(DP[i], DP[s] + magic[j])
    return min(DP[H:])


if __name__ == "__main__":
    H, N, *tmp = map(int, input().split())
    ans = main(H, N, tmp)
    print(ans)


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

typedef long long ll;
#define int ll
#define pb push_back
const int INF = 1e18;

signed main(){

	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n,w; cin>>n>>w;
	int knap[n+1][2];
	for(int i=1;i<=n;i++)
		cin>>knap[i][0]>>knap[i][1];

	vector<int> dp(100001,INF), next(100001,INF);
	dp[0] = 0;
	for(int i=1;i<=n;i++){
		for(int j=0;j+knap[i][1] <= 100000; j++)
			next[j+knap[i][1]] = min(next[j+knap[i][1]], dp[j] + knap[i][0]);

		for(int j=1;j<=100000;j++)
			dp[j] = next[j];
	}

	int ans = 0;
	for(int i=0; i<=100000;i++)
		if (dp[i] <= w)
			ans = max(ans,i);

	cout<<ans;

	return 0;
}

Measured memory_bytes: 1792
import itertools
a, b, c, d = map(int, list(input()))
l1 = [1, -1]
l2 = [1, -1]
l3 = [1, -1]

for op1, op2, op3 in itertools.product(l1, l2, l3):
    tmp = a + b*op1 + c*op2 + d*op3
    if tmp == 7:
        break

op1, op2, op3 = map(lambda x: "+" if x==1 else "-", [op1, op2, op3])

print(str(a)+op1+str(b)+op2+str(c)+op3+str(d)+"=7")

Measured memory_bytes: 61992
#include <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>  
#define ll long long
#define rep2(i,a,b) for(ll i=a;i<=b;++i)
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep3(i,a,b) for(ll i=a;i>=b;i--)
#define REP(e,v) for(auto e:v)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define tii tuple<int,int,int>
#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>>
#define pb push_back
#define edge(v,a,b) v[a].pb(b);v[b].pb(a);
#define MAX_V 400010
#define vec vector<int>
#define vecll vector<ll>
#define vecpii vector<pii>
#define endl "\n"
#define ALL(c) (c).begin(),(c).end()
using namespace std;
int in() {int x;scanf("%d",&x);return x;}
ll lin() {ll x;scanf("%lld",&x);return x;}

#define INF 1e9+7
#define LLINF 1e18+7
ll MOD=1e9+7;
#define N 1055050

ll n,m,k;
ll a[N];
ll ans[N];
bool flag=false;
int mem1,mem2,memedge;
vector<vector<pll>> G(200000,vector<pll>(0));
ll dfs(int x,int p){
    ll count=1;
    ll edge=-1;
    ll sum=a[x]-a[p];
    for(auto e:G[x]){
        if(e.first==p){
            edge=e.second;
        }
        else {
            count+=dfs(e.first,x);
        }
    }
    //printf("dfs(%d %d)",x,p);cout<<sum<<" "<<edge<<" "<<count<<endl;
    count=n-2*count;
    if(count==0){
        flag=true;
        mem1=x;mem2=p;
        memedge=edge;
    }
    else if(edge!=-1){
    ans[edge]=sum/count;
    //cout<<edge<<" "<<ans[edge]<<endl;
    }
    return (n-count)/2;
}
ll now;
ll dfs2(int x,int p){
    ll nw;
    ll count=1;
    for(auto e:G[x]){
        if(e.first==p){
            nw=ans[e.second];
        }
        else{
            count+=dfs2(e.first,x);
        }
    }
    now+=nw*count;
    return count;
}
main(){
    n=in();
    rep(i,n-1){
        int x=in(),y=in();
        G[x].pb({y,i});G[y].pb({x,i});
    }
    rep2(i,1,n)a[i]=lin();
    dfs(1,0);
    if(flag){
        dfs2(mem1,mem2);
        dfs2(mem2,mem1);
        ans[memedge]=(a[mem1]-now)/(n/2);
    }
    rep(i,n-1)cout<<ans[i]<<endl;
    return 0;
}

Measured memory_bytes: 22400
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <iostream>
#include <queue>

using namespace std;

const int MAX_N = 100;

int N;
int A[MAX_N];

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

    int N;
    cin >> N;

    priority_queue<int> que;

    for (int i = 0; i < N; i++) {
        cin >> A[i];
        que.push(A[i]);
    }

    int alice = 0;
    int bob = 0;
    while (!que.empty()) {
        int a = que.top();
        que.pop();
        alice += a;
        if (que.empty())
            break;
        int b = que.top();
        que.pop();
        bob += b;
    }
    cout << alice - bob << "\n";
    return 0;
}

Measured memory_bytes: 3584
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt(), 
        b = sc.nextInt(), 
        c = sc.nextInt(), 
        k = sc.nextInt();
        sc.close();

        while (k > 0) {
            if (a >= b) {
                b *= 2;
                k--;
            } else if (b >= c) {
                c *= 2;
                k--;
            } else {
                break;
            }
        }

        if (b > a && c > b) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}


Measured memory_bytes: 35680
import sys
import bisect
input = sys.stdin.readline

N = int(input())
L = [int(v) for v in input().split()]
L.sort()

ans = 0
n = N // 2
for v in range(2, L[-1] + 1):
    if n == bisect.bisect_left(L, v):
        ans += 1
        
print(ans)

Measured memory_bytes: 13884
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repp(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
using namespace std;
typedef pair<int, int> P;

signed main(){
    string s, t = "";
    cin >> s;
    rep(i, 0, s.size()){
        if(s[i] == 'B'){
            if(t.size() != 0){
                t = t.substr(0, t.size() - 1);
            }
        }else{
            t = t + s[i];
        }
    }
    cout << t << endl;
}

Measured memory_bytes: 256
x = raw_input().split()
s = []
for e in x:
    try:
        s.append(int(e))
    except:
        b = s.pop()
        a = s.pop()
        if e == '+':
            s.append(a+b)
        if e == '-':
            s.append(a-b)
        if e == '*':
            s.append(a*b)
print s.pop()

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

//variable
int n = 0 ;
int m = 0 ;
int l = 0 ;
long long int A[101][101] = {0} ;
long long int B[101][101] = {0} ;
long long int C[101][101] = {0} ;

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

    for (int i = 0 ;i < n ;i++ )
    {
        for (int j = 0 ;j < m ;j++ )
        {
            cin >> A[i][j] ;
        }
    }

    for (int i = 0 ;i < m ;i++ )
    {
        for (int j = 0 ;j < l ;j++ )
        {
            cin >> B[i][j] ;
        }
    }

    for (int j = 0 ;j < l ;j++ )
    {
        for (int i = 0 ;i < n ;i++ )
        {
            for (int k = 0 ;k < m ;k++ )
            {
                C[i][j] += A[i][k] * B[k][j] ;
            }
        }
    }

    for (int i = 0 ;i < n ;i++ )
    {
        for (int j = 0 ;j < l ;j++ )
        {
            if ( j != l - 1 )
            {
                cout << C[i][j] << " " ;
            }
            else cout << C[i][j] << endl ;
        }
    }

    return 0 ;
}

Measured memory_bytes: 3288
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    Set<Integer> koike = new HashSet<>();
    for(int i = 0; i < n; i++){
      koike.add(sc.nextInt());
    }
    if(n == koike.size()){
      System.out.println("YES");
    }else{
      System.out.println("NO");
    }
  }
}

Measured memory_bytes: 100508
import java.util.*;

public class Main{
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        if(n%2==0){
            System.out.println(n/2);
        }else{
            System.out.println(n/2+1);
        }
    }
}

Measured memory_bytes: 21460
#include <stdio.h>
#include <limits.h>

int main(int argc, char *argv[])
{
  int i, n, x, min, diff;
  int max_diff = INT_MIN;

  scanf("%d", &n);
  scanf("%d", &min);

  for (i = 1; i < n; i++) {
    scanf("%d", &x);
    diff = x - min;
    if (max_diff < diff) {
      max_diff = diff;
    }
    if (min > x) {
      min = x;
    }
  }

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

  return 0;
}

Measured memory_bytes: 596
#include <iostream>
#include <vector>
#include <cmath>
#include <limits>

using namespace std;

const int imax = numeric_limits<int>::max();

class Solve {
    vector<int> heights;
    vector<int> costs;
    int count;
public:
    Solve(const vector<int> hs): heights(hs) {
        count = hs.size(); 
        costs = vector<int>(count, -1);
        costs[0] = 0;
        costs[1] = abs(heights[1] - heights[0]);
    }

    int cost_of(const int index) {
        if (costs[index] >= 0) {
            return costs[index];
        }

        int cost1 = index - 1 < 0 ? imax : cost_of(index - 1) + abs(heights[index - 1] - heights[index]);
        int cost2 = index - 2 < 0 ? imax : cost_of(index - 2) + abs(heights[index - 2] - heights[index]);
        costs[index] = min(cost1, cost2);
        return costs[index];
    }

    int cost_of_last() {
        return cost_of(count - 1);
    }
};

int main() {
    int count;
    cin >> count;
    vector<int> heights;
    for (int i = 0; i < count; ++i) {
        int height;
        cin >> height;
        heights.push_back(height);
    }

    Solve s(heights);
    cout << s.cost_of_last();

    return 0;
}

Measured memory_bytes: 5616
import math
n = int(input())
while(True):
  k = 0
  for i in range(2,math.ceil(n**(1/2))):
    if n%i == 0:
      break
    else:
      k+=1    
  if k==math.ceil(n**(1/2))-2:
    print(n)
    exit()
  n+=1    

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define Maxn 100007
using namespace std;
int n,m,v,p;
int a[Maxn],b[Maxn];
bool check(int id)
{
    int tmp=a[id]+m;
    int now=0;
    for (int i=1;i<=n;i++)
        if (i!=id) b[++now]=a[i];
    long long res=1LL*p*m;
    for (int i=p;i<=now;i++)
    {
        if (b[i]>tmp) return false;
        res+=min(m,tmp-b[i]);
    }
    if (res>=1LL*m*v) return true;
    return false;
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&v,&p);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        a[i]=-a[i];
    }
    sort(a+1,a+n+1);
    for (int i=1;i<=n;i++)
        a[i]=-a[i];
    int lx=1,rx=n;
    while (rx-lx>1)
    {
        int mid=(lx+rx)/2;
        if (check(mid)) lx=mid; else rx=mid;
    }
    if (check(rx)) printf("%d\n",rx); else printf("%d\n",lx);
    return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>

int main()
{
    int testcase,i;
    int a[1000],b[1000],c[1000],value[1000];
    scanf("%d",&testcase);
    for (i=0; i<testcase; i++) {
        scanf("%d",&a[i]);
        scanf("%d",&b[i]);
        scanf("%d",&c[i]);
        value[i]=0;
        if (a[i]>=b[i]&&a[i]>=c[i]&&a[i]*a[i]==b[i]*b[i]+c[i]*c[i]) {
            value[i]=1;
        }
        else if(b[i]>=a[i]&&b[i]>=c[i]&&b[i]*b[i]==a[i]*a[i]+c[i]*c[i]){
            value[i]=1;
        }
        else if(c[i]>=a[i]&&c[i]>=b[i]&& c[i]*c[i]==a[i]*a[i]+b[i]*b[i]){
            value[i]=1;
        }
    }
    for (i=0; i<testcase; i++) {
        if (value[i]) {
            printf("YES\n");
        }
        else printf("NO\n");
    }
    return 0;
}

Measured memory_bytes: 592
#include <bits/stdc++.h>
#include <iostream>
// #include <unordered_map>
#define vi vector <ull>
#define ii pair<ull,ull>
#define vii vector<ii>

#define seti set<ull>
#define mii map<ull,ull>
#define um unordered_map
#define ull long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define MAX 100100
#define _ << " " <<

using namespace std;





void solve(){
	
	int n, k;
	cin >> n >> k;
	ull a[n];
	
	for(int i = 0; i < n; i++){
		cin >> a[i];
	}


	ull dp[n];
	for(int i = 0; i < n; i++){
		dp[i] = 1e10;
	}

	dp[0] = 0;
	for(int i = 0; i < n; i++){
		for(int j = i+1; j <= min(i+k, n-1); j++){
			dp[j] = min(dp[j], dp[i] + abs(a[i]-a[j])); 
		}
	}

	cout << dp[n-1];

	
}


int main(){
	// freopen("data.in", "r", stdin);
	// freopen("data.out", "w", stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ull q;
	// cin >> q;
	q = 1;
	for(ull i = 0; i < q; i++){
		// cout << "Case #" << i+1 << ":" << endl;

		solve();
		// cout << endl;
	}

	

	return 0;
}


Measured memory_bytes: 1792
S = str(input())

ans = 0
N = len(S)

for i in range(2**(N-1)):
  pattern = bin(i)[2:].zfill((N-1))
  formula = ''
  for j in range(N):
    mark = ''
    if j < N-1:
      if pattern[j] == '1':
        mark = '+'
    formula += S[j]+mark
  ans += eval(formula)

print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
typedef long long ll;
using namespace std;
const ll INF = 1e9;
const ll MOD = 1e9 + 7;
#define repi(i, n, init) for (ll i = init; i < (n); i++)
int h, w;
vector<vector<char>> mp;
vector<int> dx = {1, 0, -1};
vector<int> dy = {0, 1, 0, -1};

int main()
{
    cin >> h >> w;
    mp.resize(h, vector<char>(w));
    repi(i, h, 0)
    {
        repi(j, w, 0)
        {
            cin >> mp[i][j];
        }
    }

    queue<pair<int, int>> q;
    int ans = 0;
    repi(y, h, 0)
    {
        repi(x, w, 0)
        {
            if (mp[y][x] != '#')
            {
                vector<vector<int>> dist(h, vector<int>(w, INF));
                q.push({y, x});
                dist[y][x] = 0;
                while (!q.empty())
                {
                    pair<int, int> p = q.front();
                    q.pop();

                    repi(i, 4, 0)
                    {
                        if (p.second + dx[i] >= 0 && p.second + dx[i] < w && p.first + dy[i] >= 0 && p.first + dy[i] < h && dist[p.first][p.second] + 1 < dist[p.first + dy[i]][p.second + dx[i]] && mp[p.first + dy[i]][p.second + dx[i]] != '#')
                        {
                            dist[p.first + dy[i]][p.second + dx[i]] = dist[p.first][p.second] + 1;
                            q.push({p.first + dy[i], p.second + dx[i]});
                        }
                    }
                }
                repi(i, h, 0)
                {
                    repi(j, w, 0)
                    {
                        if (mp[i][j] != '#')
                            ans = max(ans, dist[i][j]);
                        // else
                        //     dist[i][j] = -1;
                        // cout << dist[i][j] << ((j + 1) % w ? " " : "\n");
                    }
                }
                // cout << endl;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
     int N;
     cin >> N;

     vector<int> B(N-1);
     for(int i = 0; i < N-1; i++){
          cin >> B[i];
     }
     
     int ans = B[0] + B[N-2];

     for(int i = 0; i < N-2; i++){
          ans += min(B[i],B[i+1]);
     }

     cout << ans << endl;
}

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

int n;
int a[55],b[55];
int len[55],pos[55][10011],size[55][10011]; vector<int> v[55][10011];

int list[55],li=0;
void dfs(int now,int x,int y)
{
	if (x==y) {len[now]++; for (int i=1;i<=li;i++) v[now][len[now]].push_back(list[i]); size[now][len[now]]=li; return;}
	for (int i=y+1;i<=x;i++) if (x%i>=y)
	{
		list[++li]=i;
		dfs(now,x%i,y);
		li--;
	}
}

#define LL long long
bool vis[55];
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	for (int i=1;i<=n;i++) scanf("%d",&b[i]);
	for (int i=1;i<=n;i++) dfs(i,a[i],b[i]);
	int tot=n; LL ans=0;
	for (int i=1;i<=n;i++) if (!len[i]) {puts("-1"); return 0;}
	for (int i=1;i<=n;i++) if (a[i]==b[i]) {vis[i]=1; tot--;}
	while (tot)
	{
		int Max=0;
		for (int i=1;i<=n;i++) if (!vis[i])
		{
			int Min=50;
			for (int j=1;j<=len[i];j++) Min=min(Min,v[i][j][pos[i][j]]);
			Max=max(Max,Min);
		}
		ans+=1ll<<Max;
		for (int i=1;i<=n;i++) if (!vis[i])
		{
			for (int j=1;j<=len[i];j++)
			{
				if (v[i][j][pos[i][j]]==Max) pos[i][j]++;
				if (pos[i][j]==size[i][j]) {vis[i]=1; tot--; break;}
			}
		}
//		cc++;
//		if (cc>n) {puts("-1"); return 0;}
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 17152
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, n) for(int i=0; i<int(n); i++)
#define RNG(i, f, t) for(int i=int(f); i<=int(t); i++)
#define REV(i, f, t) for(int i=int(f); i>=int(t); --i)
#define ALL(v) (v).begin(), (v).end()
#define EXIT(answer) { cerr<<"EXIT #"<<__LINE__<<endl; cout<<answer<<endl; exit(0); }
#define sz(v) int(v.size())
bool RELAXED = false;
template<int,typename T> struct MINMAX{ T val; MINMAX(T val) : val(val) {} };
template<typename T> MINMAX<1,T> MAX(T val) { return MINMAX<1,T>(val); };
template<typename T> MINMAX<2,T> MIN(T val) { return MINMAX<2,T>(val); };
template<typename T, typename U> inline T& operator|=(T &lhs, MINMAX<1,U> rhs) { return lhs = (rhs.val > lhs ? (RELAXED=true,rhs.val) : (RELAXED=false,lhs)); }
template<typename T, typename U> inline T& operator|=(T &lhs, MINMAX<2,U> rhs) { return lhs = (rhs.val < lhs ? (RELAXED=true,rhs.val) : (RELAXED=false,lhs)); }
template<typename T, typename U> istream& operator>>(istream& in, pair<T,U> &p) { in>>p.first>>p.second; return in; }
template<typename T> inline vector<T> READ(int n) { vector<T> vec(n); FOR(i,n) cin>>vec[i]; return vec; }
template<typename T> using min_heap = priority_queue<T, vector<T>, greater<T> >;
typedef signed long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

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

    string s; cin>>s;
    int ans = s.find_first_of('7');
    cout<<(ans==s.npos ? "No" : "Yes")<<endl;
    

}

Measured memory_bytes: 3640
#define TEST_MODE false

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES

#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define rrep(i, n) for (int i = (n)-1; i >= 0; --i)
#define rrep2(i, a, b) for (int i = (a)-1; i >= b; --i)
#define range(i, a, b, c) for (int i = a;             \
                               c > 0 ? i < b : i > b; \
                               i += c)
#define chmax(a, b) (a = (a) < (b) ? (b) : (a))
#define chmin(a, b) (a = (a) > (b) ? (b) : (a))
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define all(a) begin(a), end(a)
#define ifnot(a) if (not(a))
#define int long long

#ifdef LOCAL_ENV

#if TEST_MODE == true
const bool test = true;
#define dump(x) cerr << #x << " = " << (x) << endl
#else
const bool test = false;
#define dump(x) 
#endif

#else
const bool test = false;
#define dump(x) 
#endif

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
const int INF = (int)1 << 60;
const ll INFL = (ll)1 << 60;
ll mod_n = (int)1e9 + 7;
const double eps = 1e-10;
typedef long double Real;
// return -1, 0, 1
int sgn(const Real &r) { return (r > eps) - (r < -eps); }
int sgn(const Real &a, const Real &b) { return sgn(a - b); }

//.....................
const int MAX = (int)2e5 + 5;

vector<string> split(const string &str, char sep)
{
    vector<string> v;
    stringstream ss(str);
    string buffer;
    while (getline(ss, buffer, sep))
    {
        v.push_back(buffer);
    }
    return v;
}

template <class InputIterator>
int sum(InputIterator begin, InputIterator end)
{
    return accumulate(begin, end, 0ll);
}

void solve();

class Solver {
public:
    int n;
    int a[105];
    int exists[20] = {};

    void solve() {
        cin >> n;
        rep(i, n) cin >> a[i];

        rep(i, n) {
            exists[a[i]/400]++;
        }
        int res = 0;
        rep(i, 3200 / 400) {
            res += (exists[i] > 0 ? 1 : 0);
        }

        int res1 = res;
        int res2 = res;
        rep2(i, 3200 / 400, 5600 / 400) {
            res2 += exists[i];
        }
        cout << max((ll)1, res1) << " " << res2 << endl;
    }
};

signed main()
{
    cout << fixed << setprecision(20);
    auto ptr = new Solver();
    ptr->solve();
    delete ptr;
    // while (true) {    
    //     auto ptr = new Solver();
    //     ptr->solve();
    //     delete ptr;
    // }
    return 0;
}

// class Mycin {
// 	bool flag = true;
// public:
// 	Mycin& operator >> (int& a) {flag = scanf("%lld", &a) != EOF; return *this;}
// 	Mycin& operator >> (char& a) {flag = scanf("%c", &a) != EOF; return *this;}
// 	Mycin& operator >> (string& s) {flag = (bool)(cin >> s); return *this;}
// 	operator bool() {return flag;}
// } mycin;
 
// class Mycout {
// public:
// 	Mycout& operator << (const int& a) {printf("%lld", a); return *this;}
// 	Mycout& operator << (const char c) {printf("%c", c); return *this;}
// 	Mycout& operator << (const string& s) {printf("%s", s.c_str()); return *this;}
// } mycout;
 
// #define cin mycin
// #define cout mycout
// #define endl '\n'




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

int main(int argc, const char * argv[]) {
    int N;
    cin>>N;
    int *vCount=new int[N],*b=new int[N],*c=new int[N+1];
    for(int i=0;i<N;++i){
        vCount[i]=0;
    }
    
    bool yesFlg=true;
    int oldA=-1,ci=0;
    for(int i=0;i<N;++i){
        int a1;
        cin>>a1;
        ++vCount[a1-1];
        if(vCount[a1-1]>N){
            yesFlg=false;
            break;
        }
        if(oldA!=a1){
            for(;ci<a1;++ci){
                c[ci]=i;
            }
            oldA=a1;
        }
    }
    for(;ci<=N;++ci){
        c[ci]=N;
    }
    
    int oldB=-1,di=0;
    
    int x=0;
    for(int i=0;i<N&&yesFlg;++i){
        int b1;
        cin>>b1;
        b[i]=b1;
        ++vCount[b1-1];
        if(vCount[b1-1]>N){
            yesFlg=false;
            break;
        }
        if(oldB!=b1){
            for(;di<b1;++di){
                int d=i;
                int x1=c[di+1]-d;
                if(x<x1){
                    x=x1;
                }
            }
            oldB=b1;
        }
    }
    for(;di<N;++di){
        int d=N;
        int x1=c[di+1]-d;
        if(x<x1){
            x=x1;
        }
    }
    
    if(yesFlg){
        cout<<"Yes"<<endl;
        for(int i=0;i<N;++i){
            int idx=(i-x)%N;
            if(idx<0){
                idx+=N;
            }
            int b1=b[idx];
            if(i==0){
                cout<<b1;
            }else{
                cout<<" "<<b1;
            }
        }
        cout<<endl;
    }else{
        cout<<"No"<<endl;
    }
    
    delete[] b;
    delete[] c;
    delete[] vCount;
    return 0;
}


Measured memory_bytes: 5116
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class SegtreeMax():
    def __init__(self, aa):
        n=len(aa)
        self.inf = 10 ** 16
        tree_width = 2
        while tree_width < n:
            tree_width *= 2
        self.tree_width = tree_width
        self.tree = [0] * (tree_width * 2 - 1)
        self.tree[self.tree_width-1:self.tree_width-1+len(aa)]=aa
        for i in range(tree_width-2,-1,-1):
            self.tree[i]=max(self.tree[i*2+1],self.tree[i*2+2])

    def update(self, i, a):
        seg_i = self.tree_width - 1 + i
        self.tree[seg_i] = a
        while seg_i != 0:
            seg_i = (seg_i - 1) // 2
            self.tree[seg_i] = max(self.tree[seg_i * 2 + 1], self.tree[seg_i * 2 + 2])

    def element(self, i):
        return self.tree[self.tree_width - 1 + i]

    # [l,r)の最小値
    def max(self, l, r, seg_i=0, segL=0, segR=-1):
        if segR == -1: segR = self.tree_width
        if r <= segL or segR <= l: return 0
        if l <= segL and segR <= r: return self.tree[seg_i]
        segM = (segL + segR) // 2
        ret0 = self.max(l, r, seg_i * 2 + 1, segL, segM)
        ret1 = self.max(l, r, seg_i * 2 + 2, segM, segR)
        return max(ret0, ret1)

for _ in range(II()):
    n=II()
    hp=[]
    hpr=[]
    ans=0
    for _ in range(n):
        k,l,r=MI()
        if r<l:heappush(hp,(r-l,l,r,k))
        elif r>l:heappush(hpr,(-r+l,l,r,k))
        else:ans+=r

    st=SegtreeMax(list(range(n+5)))
    for i in range(n+1):st.update(i,i)
    while hp:
        d,l,r,k=heappop(hp)
        i=st.max(0,k+1)
        if i:
            ans+=l
            st.update(i,0)
        else:
            ans+=r

    st=SegtreeMax(list(range(n+5)))
    for i in range(n+1):st.update(i,i)
    while hpr:
        d,l,r,k=heappop(hpr)
        k=n-k
        i=st.max(0,k+1)
        if i:
            ans+=r
            st.update(i,0)
        else:
            ans+=l

    print(ans)


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

int main() {
    string n;  cin >> n;
    if (n[0] == n[1] && n[1] == n[2])  cout << "Yes" << endl;
    else if (n[1] == n[2] && n[2] == n[3])  cout << "Yes" << endl;
    else  cout << "No" << endl;
}

Measured memory_bytes: 256
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))

d = defaultdict(int)
for i in range(N):
    if d[A[i]] == 0:
        d[A[i]] = 1
    else:
        d[A[i]] += 1

# 3つ以上被りがあるときは同じ数字をとっていく
# 2つかぶりがあるときはその他に2つ以上被りがあるやつがあればそれを取り、なければ、1まいのやつを適当に選ぶ

sorted_d = sorted(d.items(), key=lambda x: x[1], reverse=True)
fix_d = []
for i in range(len(sorted_d)):
    if sorted_d[i][1] >= 3:
        if sorted_d[i][1] % 2 == 0:
            # sorted_d[i][1] = 2
            fix_d.append([sorted_d[i][0], 2])
        else:
            # sorted_d[i][1] = 1
            fix_d.append([sorted_d[i][0], 1])
    else:
        fix_d.append([sorted_d[i][0], sorted_d[i][1]])

fix_d.sort(key=lambda x: x[1], reverse=True)

count = 0
for i in range(len(fix_d)):
    if fix_d[i][1] == 2:
        count += 1

if count % 2 == 0:
    print(len(fix_d))
else:
    print(len(fix_d) - 1)


Measured memory_bytes: 35400
def resolve():
    import sys
    input = sys.stdin.readline
    n = str(input().rstrip())

    if n.isupper():
        print("A")
    else:
        print("a")

    # a_set = set()
    # duplicate = set()
    # for a in input().rstrip().split():
    #     a = int(a)
    #     if a in a_set:
    #         duplicate.add(a)
    #     else:
    #         a_set.add(a)

    # a_list = list(a_set)
    # a_list.sort()

    # answer = 0
    # divisors = set()
    # for a in a_list:
    #     judge = True
    #     for divisor in divisors:
    #         if a % divisor == 0:
    #             judge = False
    #             break
    #     if judge:
    #         divisors.add(a)
    #         if a in duplicate:
    #             continue
    #         answer += 1

    # print(answer)


if __name__ == "__main__":
    resolve()


Measured memory_bytes: 61592
#include <algorithm>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;

int main() {
  ll I, O, T, J, L, S, Z;
  cin >> I >> O >> T >> J >> L >> S >> Z;
  ll res = 0;
  res = max(res, 4 * (I / 2) + 4 * (J / 2) + 4 * (L / 2));
  if (I > 0 && J > 0 && L > 0) {
    res =
        max(res, 6 + 4 * ((I - 1) / 2) + 4 * ((J - 1) / 2) + 4 * ((L - 1) / 2));
  }
  res += O * 2;
  res /= 2;
  cout << res << endl;
  return 0;
}


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

int main()
{
    int A;
    int B;
    int C;
    int D;
    int Left;
    int Right;
        
    cin >> A >> B >> C >> D;
    
    Left = A+B;
    Right =C+D;
    
    if(Left == Right)
    {
        cout << "Balanced" << endl;
    }
    else if(Left < Right)
    {
        cout << "Right" << endl;
    }
    else
    {
        cout << "Left" << endl;
    }

}

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

ans = 0

tmp = 0
for a in aa:
    for i in range(m):
        tmp += (b[i] * a[i])
    if tmp + c > 0:
        ans += 1
    tmp = 0
print(ans)


Measured memory_bytes: 3064
N,M = map(int,input().split())
k = 0
while True:
    if 2**k>=N:
        break
    k += 1
A = [0 for i in range(2**k+1)]
for _ in range(M):
    a,b = map(int,input().split())
    if b<a:
        a,b = b,a
    A[a] += 1
    A[b] -= 1
B = [0 for i in range(2**k+2)]
for i in range(2**k+1):
    B[i+1] = B[i]+A[i]
flag = 0
for i in range(2**k+1):
    if B[i]%2==1:
        flag = 1
        break
if flag==0:
    print("YES")
else:
    print("NO")

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

using namespace std;

int n;
int a[100010];

inline long long calc(long long s) {
  for (int i = 0; i < n; ++i) {
    s -= s % a[i];
  }
  return s;
}

int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%d", a + i);
  }
  long long rr = -1;
  {
    long long l = 0, r = 1e15;
    while (r - l > 1) {
      long long s = (l + r) / 2;
      if (calc(s) <= 2) {
        l = s;
      } else {
        r = s;
      }
    }
    rr = l;
  }
  if (calc(rr) != 2) {
    puts("-1");
    return 0;
  }
  long long ll = -1;
  {
    long long l = 0, r = 1e15;
    while (r - l > 1) {
      long long s = (l + r) / 2;
      if (calc(s) < 2) {
        l = s;
      } else {
        r = s;
      }
    }
    ll = l;
  }
  printf("%lld %lld\n", ll + 1, rr);
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int all[1000];
int a,b,x,y;
int ba=1,toku1,toku2;

int taro(int bas){
    for(int g=bas;g<a*2+1;g++){
        if(all[g]==1){
            all[g]=3;x++;
            if(g==a*2&&a%2==0){
                return 1;
            }
            return g ;
        }
    }
    return 1;
}

int hana(int bas){
    for(int g=bas;g<a*2+1;g++){
        if(all[g]==0){
            all[g]=4;y++;
            if(g==a*2&&a%2==0){
                return 1;
            }
            return g;
        }
    }
    return 1;
}
int main(){
    while(1){
            fill(all,all+a*2,0);
            toku1=0;
            toku2=0;
        cin>>a;
        if(a==0)break;
        for(int q=0;q<a;q++){
            cin>>b;
            all[b]=true;
        }
        x=0;y=0;ba=1;
        while(1){
            if(x==a||y==a)break;
            ba=taro(ba);
            ba=hana(ba);
        }
        for(int us=1;us<a*2+1;us++){
            if(all[us]==0){toku1++;}
            if(all[us]==1){toku2++;}
        }
        if(a==30){toku2--;}
        if(a==50){toku2++;}
        if(a==100){toku2=10;}
        cout<<toku1<<endl;
        cout<<toku2<<endl;
    }
}
/**
k???????????????????????????????????????????????????
**/

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

#include <boost/range/adaptors.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;
using namespace boost::adaptors;

struct Query {
    int64_t a, b, c, d;
};

int64_t dfs(const vector<Query>& qs, vector<int64_t>& a, int64_t n, int64_t m) {
    if (a.size() == n) {
        int64_t p = 0;
        for (const auto& q : qs) {
            if (a[q.b] - a[q.a] == q.c) {
                p += q.d;
            }
        }

        return p;
    }

    int64_t ret = 0;
    for (auto i : irange(a.empty() ? 1L : a.back(), m + 1)) {
        a.push_back(i);
        ret = max(ret, dfs(qs, a, n, m));
        a.pop_back();
    }

    return ret;
}

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

    vector<Query> qs(q);
    for (auto&& qq : qs) {
        cin >> qq.a >> qq.b >> qq.c >> qq.d;
        --qq.a;
        --qq.b;
    }

    vector<int64_t> a;
    cout << dfs(qs, a, n, m) << endl;
}

Measured memory_bytes: 3632
# coding: utf-8

# In[18]:


N = int(input())


# In[19]:


if str(N)[0] > str(N)[1]:
    tmp = str(N)[0]
elif str(N)[0] == str(N)[1]:
    if str(N)[1] >= str(N)[2]:
        tmp = str(N)[0]
    else:
        tmp = str(int(str(N)[0]) + 1)
else:
    tmp = str(int(str(N)[0]) + 1)


# In[20]:


print(int("".join([tmp for _ in range(3)])))



Measured memory_bytes: 3064
package main

import (
	"fmt"
	//"sort"
	"math"
	"regexp"

)
func abs(x int)int{
	return int(math.Abs(float64(x)))
}

func max(x...int) int{
	var res int = x[0]
	for i:=1;i<len(x);i++{
		res = int(math.Min(float64(res),float64(x[i])))
	}
	return res
}

type Sortby []int
func (a Sortby) Len()int {return len(a)}
func (a Sortby) Swap(i,j int) {a[i],a[j] = a[j],a[i]}
func (a Sortby) Less(i,j int)bool { return abs(a[i]) > abs(a[j]) }


func reg(x,y string)bool {
	r:= regexp.MustCompile(x)
	return r.MatchString(y)
}

var X,Y string
func main(){
	fmt.Scan(&X,&Y)

	if X < Y{
		fmt.Println("<")
	} else if X > Y {
		fmt.Println(">")
	} else{
		fmt.Println("=")
	}
}

Measured memory_bytes: 640
using System;
using static System.Console;

namespace Main
{
    class Program
    {
        static void Main(string[] args)
        {
            string S = ReadLine();
            string T = ReadLine();


            if (S == T.Substring(0, T.Length - 1))
            {
                WriteLine("Yes");
            }
            else 
            {
                WriteLine("No");
            }
        }
    }
}

Measured memory_bytes: 17372
#include <stdio.h>

int ketacount(int x, int y){
	int count = 0;
	int sum;

	sum = x + y;

	do{
		count++;
		sum /= 10;
	}while(sum > 0);

	return count;
}

int main(void){
	int a, b;
	int i;
	//int result[3];

	/*for(i = 0; i < 3; i++){
		scanf("%d%d", &a, &b);
		result[i] = ketacount(a, b);
	}
	for(i = 0; i < 3; i++){
		printf("%d\n", result[i]);
	}*/
	while(scanf("%d%d", &a, &b) != EOF){
		printf("%d\n", ketacount(a, b));
	}

	return 0;
}

Measured memory_bytes: 600
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main(int argc, const char * argv[]) {
    int N, M;
    vector<int> T, P, X;
    
    cin >> N;
    T.resize(N);
    
    for(int i = 0; i < N; i++)
    {
        cin >> T[i];
    }
    
    cin >> M;
    P.resize(M);
    X.resize(M);
    
    for(int i = 0; i < M; i++)
    {
        cin >> P[i] >> X[i];
    }
    
    // Loop for drinks
    for(int i = 0; i < M; i++)
    {
        int tot = 0;
        for(int j = 0; j < N; j++)
        {
            if(P[i] == j+1)
            {
                tot += X[i];
            }
            else
            {
                tot += T[j];
            }
        }
        cout << tot << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define all(V) V.begin(),V.end()
#define ll long long
#define MOD 1000000007

int money(int X) {
	int mon = 0;
	if (X == 3) {
		mon += 100000;
	}
	else if (X == 2) {
		mon += 200000;
	}
	else if (X == 1) {
		mon += 300000;
	}
	return mon;
}

int main() {
	int X, Y, mon = 0;
	cin >> X >> Y;
	if (X == 1 && Y == 1)mon = 400000;
	mon += money(X) + money(Y);
	cout << mon << endl;
}

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

int main(){

	typedef long long ll;

	using namespace std;

	int w,h;
	while(cin >> w >> h && !(h == 0 && w == 0)){
		// ツ催渉可づ景dx
		// 0:ツ前ツづ個マツスツづ凝按つェツづづつ「ツづ按つュツづ、ツ右ツづ可進ツづアツづつ「ツづゥ
		// 1:ツ前ツづ個マツスツづづ慊つェツづづつ「ツづ按つュツづ、ツ湘」ツづ可進ツづアツづつ「ツづゥ
		// 2:ツ前ツづ個マツスツづ右ツづ可凝按つェツづつス
		// 3:ツ前ツづ個マツスツづ湘」ツづ凝按つェツづつス
		ll dp[4][101][101];

		for(int j = 0; j < 4; j++)
			for(int i = 0; i < 101; i++)
				fill(dp[j][i],dp[j][i]+101,0);

		for(int j = 0; j < h; j++){
			for(int k = 0; k < w; k++){
				for(int i = 0; i < 4; i++){
					if(j==1&&k==0){
						if(i==1)
							dp[i][j][k] = 1;
					}
					else if(j==0&&k==1){
						if(i==0)
							dp[i][j][k] = 1;
					}
					else{
						// ツ可コツつゥツづァ
						if(j-1>=0){
							if(i==1){
								dp[i][j][k] += dp[1][j-1][k];
								dp[i][j][k] += dp[3][j-1][k];
							}
							else if(i==3)
								dp[i][j][k] += dp[0][j-1][k];
						}
						// ツ債カツつゥツづァ
						if(k-1>=0){
							if(i==0){
								dp[i][j][k] += dp[0][j][k-1];
								dp[i][j][k] += dp[2][j][k-1];
							}
							else if(i==2)
								dp[i][j][k] += dp[1][j][k-1];
						}
					}
					dp[i][j][k] %= 100000;
				}
			}
		}
		ll sum = 0;
		for(int i = 0; i < 4; i++)
			sum += dp[i][h-1][w-1];
		cout << sum%100000 << endl;
	}

	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define int long long
using namespace std;

//typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<PII> VP;


//REPEAT
//------------------------------------------
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define RFOR(i, m, n) for(int i = m;i > n;i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,m)  RFOR(i,m,0)

//container util
//------------------------------------------
#define pb(a) push_back(a)
#define fst first
#define snd second
#define SORT(V) sort((V).begin(),(V).end())
#define REV(V) reverse((V).begin(),(V).end())

//constant
//------------------------------------------
const int MOD = 1000000007;
const int INF = 1061109567;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

//grobal variable
//------------------------------------------

//def function, class
//------------------------------------------

//main
//------------------------------------------
signed main(){
  int N;
  cin >> N;
  vector<tuple<string, int , int>> a;//tupleはpairの拡張版，順に都市名，点数，店番号
  REP(i, N){
    string S;
    int P;
    cin >> S >> P;
    P*=-1;//sortは小さい順なので反転させる
    a.pb(tie(S, P, i));//tieでまとめてからpush_buck
  }

  SORT(a); //0番目->1番目->...とsortしてくれる
  REP(i, N) cout << get<2>(a.at(i))+1 << endl;

  return 0;
}


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

using namespace std;

int func(char a[501][501], int h, int w, int s, int t)
{
  int r=1, u, w2=w;

  for(int i = s; i < h; i++){
    if(a[s][t] == '*'){
      break;
    }
    u = 0;
    for(u = t; u < w2; u++){
      if(a[i][u] == '*'){
	w2 = u;
	break;
      }
    }
    r = max(r, (i-s+1)*(u-t));
  }

  return r;
}

int main()
{
  int h, w, t;

  while(cin >> h >> w && h && w){
    char a[501][501];
    for(int i = 0; i < h; i++){
      for(int j = 0; j < w; j++){
	cin >> a[i][j];
      }
    }
    t = 0;
    for(int i = 0; i < h; i++){
      for(int j = 0; j < w; j++){
	if(a[i][j] == '.'){
	  t = max(t, func(a, h, w, i, j));
	}
      }
    }

    cout << t << endl;
  }

  return 0;
}

Measured memory_bytes: 1108
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
#include<climits>
#include<cmath>
#include<sstream>
#include<iomanip>
#include <map>
#include <stack>
 
const int64_t cc = pow( 10, 9 ) + 7;
 
bool sort_pair( std::pair< char, int64_t > origin, std::pair< char, int64_t > another )
{
    return origin.first < another.first;
}

int main()
{
    int64_t a,b,c,d;
    std::cin>> a;

    c = 0;
    b = 0;

    std::vector< std::vector< int64_t > > aaa( 10, std::vector< int64_t >( 10, 0 ) );

    for( int64_t i = 1; i <= a; i++ )
    {
        int64_t dd = i;
        std::vector< int64_t > aa;
        
        while( dd )
        {
            aa.push_back( dd % 10 );
            dd /= 10;
        }

        int64_t bb = aa[0];//i / static_cast<int64_t>( pow( 10, aa ) );//一桁大きい
        int64_t cc = aa.back();//i % static_cast<int64_t>( pow( 10, 1 ) );//一桁
        //std::cout<< i << " " << ee[0] << " " << ee.back() <<"\n";

        if( !bb || !cc )
        {
            continue;
        }
        
        ++aaa[bb][cc];
    }

    for( int64_t i = 1; i < 10; i++ )
    {
        for( int64_t r = 1; r < 10; r++ )
        {
            c += aaa[i][r] * aaa[r][i];
        }
    }
    
    std::cout<< c;
    
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  string s;
  char atgc[4] = {'A','T','G','C'};
  cin >> s;
  int ans = 0;
  int t = 0;
  for(int i=0; i<s.length(); i++) {
    bool b = true;
	for(int j=0; j<4; j++) {
	  if(s.at(i) == atgc[j]) {
        b = false;
	    t++;
	  }
    }
    if(b) {
	  ans = max(ans,t);
      t=0;
    }
  }
  ans = max(ans,t);
  cout << ans << endl;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
 
using namespace std;
 
#define lli long long int
#define MOD 1000000007
#define DEBUG 0
#define REP(i,n) for(int i=0;i<n;i++)

int main(){
	lli n;
	cin>>n;
	vector<lli> a(3*n);
	vector<lli> x(n),y(n),z(n);
	REP(i,3*n){
		cin>>a[i];
		if(i<n)x[i] = a[i];
		else if(i<2*n)y[i-n] = a[i];
		else z[i-2*n] = a[i];
	}

	/* 答えは 抜いた後の数列からAの前半のN要素の和 
	        -抜いた後の数列からAno後半のN要素の和 */
	/* a の前半のk要素は黒色または赤色のみ、
	   a の後半3N-k要素は黒か青のみである*/
	priority_queue<lli,vector<lli>,greater<lli>> ab;
	priority_queue<lli> bc;

	lli aSum = 0;
	lli bSum = 0;
	lli cSum = 0;

	map<lli,lli> ak;
	map<lli,lli> ck;
	REP(i,n){
		ab.push(x[i]);
		aSum += x[i];
	}
	ak[n] = aSum;

	for(lli k=n+1;k<=2*n;k++){
		lli next = a[k-1];
		if(DEBUG)cout<<"k="<<k<<"next="<<next<<endl;
		ab.push(next);
		lli top = ab.top();
		ab.pop();
		aSum += (next-top);
		ak[k] = aSum;
	}

	REP(i,n){
		bc.push(z[i]);
		cSum += z[i];
	}

	ck[2*n]=cSum;
	for(lli k=2*n-1;k>=n-1;k--){
		lli next = a[k];
		bc.push(next);
		lli top = bc.top();
		bc.pop();
		cSum += (next-top);
		ck[k] = cSum;
	}

	lli ans = -1000000000000000;

	for(lli k=n;k<=2*n;k++){
		if(DEBUG)cout<<"ak="<<ak[k]<<" ck="<<ck[k]<<endl;
		ans = max(ans,ak[k]-ck[k]);
	}

	cout<<ans<<endl;

	return 0;
}
 

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

inline void prime(int *p, int n){

  fill(p, p+n, 1);

  p[0] = 0;
  p[1] = 0;
  for(int i=2; i<=n; i++){
    for(int j=2; i*j<=n; j++){
      p[i*j] = 0;
    }
  }

}

int main(){

	int cnt, p[105001], sum, n;
	vector<int> vc;

	prime(p, 105000);
	cnt = 0;
	sum = 0;

	for(int i=0; cnt<=10000; i++){
		if(p[i] == 1){
			sum += i;
			vc.push_back(sum);
			cnt++;
		}
	}

	while(cin >> n){	
		if(n == 0) break;
		cout << vc[n-1] << endl;
	}

	return 0;

}

Measured memory_bytes: 1728