akhauriyash/Code-Regression huggingface dataset:
# Date [ 2020-08-15 21:54:45 ]
# Problem [ e.py ]
# Author Koki_tkg

import sys;      from decimal import Decimal
import math;     from itertools import combinations, product
import bisect;   from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 6 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def lcm(a: int, b: int) -> int: return (a * b) // math.gcd(a, b)

from numba import njit, i8
import numpy as np

@njit(i8(i8, i8, i8[:,:]))
def dp(R, C, grid):
    dp = np.zeros((R+1, C+1, 4), np.int64)
    for y in range(1, R+1):
        for x in range(1, C+1):
            for i in range(4):
                dp[y][x][i] = max(dp[y][x - 1][i], dp[y - 1][x][3])
            for i in range(3, 0, -1):
                dp[y][x][i] = max(dp[y][x][i], dp[y][x][i - 1] + grid[y-1][x-1])
    return dp[R][C][3]

def Main():
    R, C, k = read_ints()
    item = [read_int_list() for _ in range(k)]
    grid = np.zeros((R, C), np.int64)
    for r, c, v in item:
        grid[r - 1][c - 1] = v
    print(dp(R, C, grid))

if __name__ ==  '__main__':
    Main()

Measured memory_bytes: 504996
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
const ll inf = 1LL << 50;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
///////////////////////////////////////

int main() {
	string s, t;
	cin >> s >> t;
	vector<vector<int>>alpha;
	alpha.resize(26);
	for (int i = 0; i < s.size(); ++i) {
		alpha[s[i] - 'a'].push_back(i);
	}
	ll ans = 0;
	ll last = -1;
	for (int i = 0; i < t.size(); ++i) {
		if (alpha[t[i] - 'a'].size()<=0) {
			cout << -1 << endl;
			return 0;
		}
		auto itr = upper_bound(alpha[t[i] - 'a'].begin(), alpha[t[i] - 'a'].end(), last);
		if (itr == alpha[t[i] - 'a'].end()) {
			ans += s.size();
			itr = alpha[t[i] - 'a'].begin();
		}
		last = *itr;
	}
	ans += last+1;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1216
#include <iostream>  // cout, endl, cin
#include <vector>    // vector

using namespace std;

#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define all(a) a.begin(), a.end()

typedef long long ll;

typedef vector<ll> vll;
typedef vector<bool> vb;

int main()
{
  ll n; cin >> n;
  vll base(n); rep(i, n) cin >> base[i];
  ll bit = 0;
  ll K = 1;
  rep(i, n)
  {
    bit += K;
    K *= 2; 
  }
  ll m; cin >> m;
  vll ans(m); rep(i, m) cin >> ans[i];
  vb flag(m, false);
  for(ll i = 0;i <= bit;i++)
  {
    ll tmp = i;
    ll S = 0;
    ll j = 0;
    while(tmp)
    {
      if(tmp % 2 == 1) S += base[j];
      j++;
      tmp /= 2;
    }
    rep(j, m)
    {
      if(ans[j] == S) flag[j] = true;
    }
  }
  rep(i, m)
  {
    cout << (flag[i]?"yes\n":"no\n");
  }
}



Measured memory_bytes: 3108
#include <bits/stdc++.h>
using namespace std;
#define inf 999999999
#define loop(i, a, b) for (int i = (a), i##len = (b); i < i##len; ++i)
#define rep(i, n) loop(i, 0, n)
#define lin long long
#define lfl long double

int main(void)
{
    int n,k;
    cin >> n >> k;
    bool res = (n+1) / 2 >= k;

    if(res)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main(){
  int n;
  string str;
  cin>>n>>str;
  if(n%2==1){
    cout<<"No"<<endl;
    return(0);
  }
  if(str.substr(0,str.size()/2)==str.substr(str.size()/2,str.size()/2)){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
  return(0);
}


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

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin >> n;
  vector<int> a(n + 1), idx;
  for (int i = 1; i <= n; ++i) {
    idx.push_back(i);
    cin >> a[i];
  }
  auto cmp = [&](int i, int j) {
    return a[i] < a[j];
  };
  sort(idx.begin(), idx.end(), cmp);
  set<int> seen;
  seen.insert(0);
  seen.insert(n + 1);
  long long ans = 0;
  for (int i : idx) {
    auto pr = seen.lower_bound(i);
    auto pl = pr;
    --pl;
    seen.insert(i);
    ans += a[i] * (*pr - (long long) (i)) * (i - *pl);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 11252
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

#define MOD 1000000007
#define MOD2 998244353
#define int long long
#define double long double
#define EPS 1e-9
//#define PI 3.14159265358979

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

using namespace std;

template < typename T >
ostream &operator<<(ostream &os, const vector< T > &A) {
	for (int i = 0; i < A.size(); i++)
		os << A[i] << " ";
	os << endl;
	return os;
}
template <>
ostream &operator<<(ostream &os, const vector< vector< int > > &A) {
	int N = A.size();
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < A[i].size(); j++)
			os << A[i][j] << " ";
		os << endl;
	}
	return os;
}

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

struct edge {
	int from, to, d, c;
	edge(int _from = 0, int _to = 0, int _d = 0, int _c = 0) {
		from = _from;
		to = _to;
		d = _d;
		c = _c;
	}
	bool operator<(const edge &rhs) const {
		return (d == rhs.d) ? (c < rhs.c) : (d < rhs.d);
	}
};
struct aabb {
	int x1, y1, x2, y2;
	aabb(int x1, int y1, int x2, int y2) : x1(x1), y1(y1), x2(x2), y2(y2) {}
};

typedef vector< edge > edges;
typedef vector< edges > graph;
struct flow {
	int to, cap, rev, cost;
	flow(int to = 0, int cap = 0, int rev = 0, int cost = 0) : to(to), cap(cap), rev(rev), cost(cost) {}
};
typedef vector< vector< flow > > flows;

const int di[4] = {0, -1, 0, 1};
const int dj[4] = {-1, 0, 1, 0};
const int ci[5] = {0, 0, -1, 0, 1};
const int cj[5] = {0, -1, 0, 1, 0};
const ll LINF = LLONG_MAX / 2;
const int INF = INT_MAX / 2;
const double PI = acos(-1);

int pow2(int n) { return 1LL << n; }
template < typename T, typename U >
bool chmin(T &x, const U &y) {
	if (x > y) {
		x = y;
		return true;
	}
	return false;
}
template < typename T, typename U >
bool chmax(T &x, const U &y) {
	if (x < y) {
		x = y;
		return true;
	}
	return false;
}

struct initializer {
	initializer() {
		cout << fixed << setprecision(20);
	}
};
initializer _____;

int N, M, K, T, Q, H, W;
signed main() {
	cin >> N >> M;
	cout << N * M << endl;
	return 0;
}

Measured memory_bytes: 3624
#include <iostream>
#include <limits>
#include <set>

using namespace std;

using Z = int;
constexpr Z INF = numeric_limits<Z>::max();

#ifdef DEBUG
# define dump(x) cerr << "dump@" << __LINE__ << " : " << #x << " = " << (x) << endl
# define mesg(m) cerr << "mesg@" << __LINE__ << " : " << m << endl
# define debug if (true)
#else
# define NDEBUG
# define dump(x)
# define mesg(m)
# define debug if (false)
#endif
#define rep(i, n) for (auto i = 0; i < n; i++)
#define rrep(i, n) for (auto i = n; i >= 0; i--)
#define all(c) begin(c), end(c)

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  Z s;
  cin >> s;
  set<Z> seen;
  Z i = 1;
  while (!seen.count(s)) {
    seen.insert(s);
    if (s % 2 == 0)
      s /= 2;
    else
      s = s * 3 + 1;
    i++;
  }
  cout << i << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=1e5+10;
int n,d[maxn];
LL a[maxn];
vector<int> G[maxn];
bool flag=1;
void dfs(int u,int fu)
{
	LL sum=0,maxs=0;
	int o=0;
	for (int i=0;i<G[u].size();i++)
	{
		int v=G[u][i];
		if (v==fu) continue;
		o++;
		dfs(v,u);
		sum+=a[v];
		maxs=max(maxs,a[v]);
	}
	if (o==0) return ;
	LL x=sum-a[u],y=2*a[u]-sum;
	if (x<0||y<0||x>min(sum-maxs,sum/2)||(fu==-1&&y)) flag=0;
	a[u]=y;
}
int main()
{
	cin>>n;
	for (int i=1;i<=n;i++) scanf("%I64d",&a[i]);
	for (int i=1;i<n;i++)
	{
		int u,v;scanf("%d%d",&u,&v);
		G[u].push_back(v);G[v].push_back(u);
		d[u]++;d[v]++;
	}
	int root=0;
	for (int u=1;u<=n;u++) if (d[u]>1) {root=u;break;}
	if (root) dfs(root,-1);
	else flag=(a[1]==a[2]);
	if (flag) cout<<"YES";
	else cout<<"NO";
	return 0;
}

Measured memory_bytes: 14848
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define pi M_PI
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

int main() {
    int n;
    while (cin >> n && n){
        vector<pair<double, string> > food(n);
        REP(i,n){
            string l;
            int p, a, b, c, d, e, f, s, m;
            cin >> l >> p >> a >> b >> c >> d >> e >> f >> s >> m;
            food[i].second = l;
            food[i].first = m * f * s - p;
            food[i].first /= a + b + c + m * (d + e);
            food[i].first *= -1;
        }
        sort(food.begin(), food.end());
        REP(i,n) cout << food[i].second << endl;
        cout << "#" << endl;
    }
    return 0;
}

Measured memory_bytes: 2944
#include <stdio.h>

int main(void) 
{
	int i,s,a,ave,b;
	
	for( i=0 ; i<5 ;i++){
		scanf("%d",&s);
		if(s<40){
			s=40;
		}
		b=b+s;
		
	}
	ave=b/5;
	printf("%d\n",ave);
	return 0;
	
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(int i = 1; i <= (int)(n); i++)
#define drep(i, n) for(int i = (n)-1; i >= 0; i--)
#define ALL(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;

// Mod int
const int mod = 1000000007;
// const int mod = 998244353;
struct mint {
  ll x;
  mint():x(0){}
  mint(ll x):x((x%mod+mod)%mod){}
  // mint(ll x):x(x){}
  mint& fix() { x = (x%mod+mod)%mod; return *this;}
  mint operator-() const { return mint(0) - *this;}
  mint& operator+=(const mint& a){ if((x+=a.x)>=mod) x-=mod; return *this;}
  mint& operator-=(const mint& a){ if((x+=mod-a.x)>=mod) x-=mod; return *this;}
  mint& operator*=(const mint& a){ (x*=a.x)%=mod; return *this;}
  mint operator+(const mint& a)const{ return mint(*this) += a;}
  mint operator-(const mint& a)const{ return mint(*this) -= a;}
  mint operator*(const mint& a)const{ return mint(*this) *= a;}
  bool operator<(const mint& a)const{ return x < a.x;}
  bool operator==(const mint& a)const{ return x == a.x;}
};
istream& operator>>(istream&i,mint&a){i>>a.x;return i;}
ostream& operator<<(ostream&o,const mint&a){o<<a.x;return o;}
//



int main() {
  int n;
  cin >> n;
  vector<string> s(n);
  rep(i, n) cin >> s[i];
  int a = 0, b = 0, c = 0, d = 0;
  rep(i, n) {
    if (s[i] == "AC") a++;
    else if (s[i] == "WA") b++;
    else if (s[i] == "TLE") c++;
    else d++;
  }
  printf("AC x %d\n", a);
  printf("WA x %d\n", b);
  printf("TLE x %d\n", c);
  printf("RE x %d\n", d);
}

Measured memory_bytes: 6356
n, s = map(int, input().split())
a = list(map(int, input().split()))
MOD = 998244353

ptn = [0] * (s + 1)
ptn[0] = 1
ans = 0
for i in range(n):
    for j in range(s + 1)[::-1]:
        if j + a[i] > s:
            continue
        ptn[j + a[i]] += ptn[j]
    ans += ptn[s]
    ans %= MOD
    ptn[0] += 1

print(ans)

Measured memory_bytes: 67420
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lowbit(a) ((a) & -(a))
#define clean(a, b) memset(a, b, sizeof(a))
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 9;

int _;

//========================================================================

//========================================================================
int main()
{
    string a,b;
    cin>>a>>b;
    int len=b.size();
    a+=b[len-1];
    if(a==b)puts("Yes");
    else puts("No");
    return 0;
}

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

int main(void){
	string sa, sb, sc;
	cin >> sa >> sb >> sc;
	lli i = 0, j = 0, k = 0;
	char t = 'a';
	char ans;
	while(1){
		if(t == 'a'){
			if(i == sa.size()){
				ans = 'A';
				break;
			}
			t = sa[i];
			i++;
		}else if(t == 'b'){
			if(j == sb.size()){
				ans = 'B';
				break;
			}
			t = sb[j];
			j++;
		}else if(t == 'c'){
			if(k == sc.size()){
				ans = 'C';
				break;
			}
			t = sc[k];
			k++;
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3628
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define fore(i,a) for(auto &i:a)
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
//---------------------------------------------------------------------------------------------------
class LCA {
public:
    int NV, logNV;
    vector<int> D;
    vector<vector<int>> P;
    vector<vector<int>> E;

    LCA() {}
    void init(int N) {
        NV = N;
        logNV = 1;
        while (NV > (1LL << logNV)) logNV++;
        D = vector<int>(NV);
        P = vector<vector<int> >(logNV, vector<int>(NV));
        E = vector<vector<int>>(N);
    }

    void add_edge(int a, int b) {
        E[a].push_back(b);
        E[b].push_back(a);
    }

    void make() {
        dfs(0, -1, 0);
        build();
    }

    void dfs(int v, int par, int d) {
        D[v] = d;
        P[0][v] = par;
        for (int i : E[v]) if (i != par) dfs(i, v, d + 1);
    }

    void build() {
        for (int k = 0; k < logNV - 1; k++) for (int v = 0; v < NV; v++) {
            if (P[k][v] < 0)
                P[k + 1][v] = -1;
            else
                P[k + 1][v] = P[k][P[k][v]];
        }
    }

    int lca(int u, int v) {
        if (D[u] > D[v]) swap(u, v);
        for(int k = 0;k < logNV;k++) if ((D[v] - D[u]) >> k & 1) v = P[k][v];
        if (u == v) return u;

        for (int k = logNV - 1; k >= 0; k--) {
            if (P[k][u] != P[k][v]) {
                u = P[k][u];
                v = P[k][v];
            }
        }
        return P[0][u];
    }
};
/*---------------------------------------------------------------------------------------------------
????????????????????????????????? ??§?????§  
??????????????? ??§?????§ ???????´<_??? ?????? Welcome to My Coding Space!
???????????? ??? ?´_???`??????/??? ???i     
?????????????????????????????? ???  |???|     
????????? /?????? /??£??£??£??£/??????|  
??? ???_(__??????/???    ???/ .| .|????????????  
??? ????????????/????????????/??????u??????  
---------------------------------------------------------------------------------------------------*/



//---------------------------------------------------------------------------------------------------
void _main() {
    int N; cin >> N;
    LCA lca;
    lca.init(N);
    rep(i, 0, N) {
        int K; cin >> K;
        rep(j, 0, K) {
            int c; cin >> c;
            lca.add_edge(i, c);
        }
    }
    lca.make();

    int Q; cin >> Q;
    rep(q, 0, Q) {
        int a, b; cin >> a >> b;
        int ans = lca.lca(a, b);
        printf("%d\n", ans);
    }

}

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

typedef long long ll;
#define rep(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define debug(x) cerr << #x << ": " << x << '\n'

int main()
{
    ll N, H, W, ans = 0;
    cin >> N >> H >> W;
    ll A, B;
    rep(i, N)
    {
        cin >> A >> B;
        if (A >= H && B >= W)
        {
            ++ans;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
import java.util.*;

public class Main{
  
  public static void main(String[] args){
    
    Scanner sc = new Scanner(System.in);
    
    int N = sc.nextInt();
    int[] list = new int[N];
    int count = 0;

    for(int i = 0; i < N ; i++){
      list[i] = sc.nextInt();
      if(((i+1)%2 != 0) && (list[i]%2 != 0)){
        count++;
      }              
     }
    
      System.out.println(count);
     
    
  } 
}

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

int main (){
    ll N, M;
    cin>>N>>M;
    M ++;
    N ;
  	ll Sum=0;
    ll pow=2;
    while(0==0){
      	ll TM=(M/pow)*pow/2;
      	ll SM=(((M%pow-pow/2)>0)?(M%pow-pow/2):0);
        TM += SM;
      	TM %= 2;
      	ll TN=(N/pow)*pow/2;
      	ll SN=(((N%pow-pow/2)>0)?(N%pow-pow/2):0);
        TN += SN;
      	TN %= 2;
        ll TT=TN + TM ;
      	TT%= 2;
      	Sum += TT*pow/2;
      	//cout<<TM<<" "<<TN<<endl;
        if(pow>M){
            break;
        }
        pow *= 2;
    }
   
    cout<<Sum<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
struct T
{
	string s;
	int a;
	bool operator <(T &v){
		if(s<v.s){
			return true;
		}
		else if(s==v.s&&a>v.a){
			return true;
		}
		return false;
	}
	bool operator ==(T &v){
		if(s==v.s&&a==v.a){
			return true;
		}
		return false;
	}
};
int main(){

	long long n;
	cin>>n;
	T ar[n],arr[n];
	for(int i=0;i<n;i++){
		cin>>ar[i].s>>ar[i].a;
		arr[i]=ar[i];
	}
	sort(arr,arr+n);
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(arr[i]==ar[j]){
				cout<<j+1<<endl;
				break;
			}
		}
	}
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;

class Main {

	void solve() {

		out.println(48-inint());

	}

	public static Scanner in = new Scanner(System.in);
	public static PrintWriter out = new PrintWriter(System.out);

	public static void main(String[] args) {
		new Main().solve();
		out.flush();
	}

	public int inint() {
		return in.nextInt();
	}

	public String instr() {
		return in.next();
	}

	public int[] inintar(int num) {
		int[] a = new int[num];
		for (int i=0; i<num; i++) {
			a[i] = in.nextInt();
		}
		return a;
	}

	public char[] incharar() {
		return in.next().toCharArray();
	}

}

Measured memory_bytes: 22100
import Control.Monad
import Data.List

getInts :: IO [Int]
getInts = do s <- getLine
             return $ map read $ words s

getLines :: Int -> IO [String]
getLines n = replicateM n $ getLine

trunc :: [String] -> [String]
trunc ws = filter (not . all (== '.')) ws

main = do [h, w] <- getInts
          bd <- getLines h
          mapM_ putStrLn $ trunc $ transpose $ trunc $ transpose bd

Measured memory_bytes: 1788
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long int
using namespace std;
const int N= 1e5;

bool check(string s, string cs){
  if((int)s.size() != (int)cs.size())
    return 0;
  for(int i = 0; i < (int)s.size(); i++){
    if(s[i] != '?' && s[i] != cs[i]){
      return 0;
    }
  }
  return 1;
}
int main(){ 
    fast;
    string s, t, cs, ans;
    cin >> s >> t;
    ans += '{';
    for(int i = 0; i < (int)s.size(); i++){
      cs.clear();
      for(int j = 0; j < i; j++){
        if(s[j] == '?')
          cs += 'a';
        else
          cs += s[j];
      }
      cs += t;
      for(int j = (int)cs.size(); j < (int)s.size(); j++){
        if(s[j] == '?')
          cs += 'a';
        else
          cs += s[j];
      }
      //cout << cs << "\n";
      if(check(s, cs))
        ans = min (ans, cs);
    }
    //cout << ans;
    if(ans != "{")
    cout << ans;
    else
      cout << "UNRESTORABLE";
    return 0;
}


Measured memory_bytes: 384
#pragma region
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <list>
#include <iomanip>
#include <cstdint>
#include <bitset>

using namespace std;
typedef long long ll;
//#define rep(i, s, e) for (int(i) = (s); (i) < (e); ++(i))
#define rep(i, e) for (int(i) = 0; (i) < (e); ++(i))
#define rrep(i, s) for (int(i) = (s) - 1; (i) >= 0; --(i))
#define all(x) x.begin(),x.end()

#pragma region UnionFind
struct UnionFind
{
	vector<int> par;

	UnionFind(int n) : par(n, -1) {}
	void init(int n) { par.assign(n, -1); }

	int root(int x)
	{
		if (par[x] < 0) return x;
		else return par[x] = root(par[x]);
	}

	bool issame(int x, int y)
	{
		return root(x) == root(y);
	}

	bool merge(int x, int y)
	{
		x = root(x); y = root(y);
		if (x == y) return false;
		if (par[x] > par[y]) swap(x, y);
		par[x] += par[y];
		par[y] = x;
		return true;
	}

	int size(int x)
	{
		return -par[root(x)];
	}
};
#pragma endregion
#pragma region GCD
int gcd(int a, int b)
{
	if (a%b == 0)return b;
	return gcd(b, a%b);
}
#pragma endregion
#pragma region chmin
template<class T> inline bool chmin(T& a, T b)
{
	if (a > b)
	{
		a = b;
		return true;
	}
	return false;
}
#pragma endregion
#pragma region chmax
template<class T> inline bool chmax(T& a, T b)
{
	if (a < b)
	{
		a = b;
		return true;
	}
	return false;
}
#pragma endregion
#pragma endregion


int main()
{
	int n; cin >> n;
	vector<int> p(n), q(n), v(n);
	rep(i, n)cin >> p[i];
	rep(i, n)cin >> q[i];
	rep(i, n)v[i] = i + 1;
	int a = 0, b = 0;
	int cnt = 0;
	do
	{
		++cnt;
		if (v == p)a = cnt;
		if (v == q)b = cnt;
	} while (next_permutation(all(v)));
	cout << abs(a - b) << endl;
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)
const int mod=1000000007;
const int mod1=998244353;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;cin >> n;
	vector<pii> x(n);
	rep(i,n){
		cin >> x.at(i).first;
		x.at(i).second=i;
	}
	vector<int> ans(n*n),a(n),b(n);
	vector<bool> c(n);
	rep(i,n){
		a.at(i)=n-1-i;
		b.at(i)=n-1;
	}
	rep(i,n) ans.at(x.at(i).first-1)=i+1;
	sort(x.rbegin(),x.rend());
	int j=0,k=0;
	bool flg=true,flg1=false;
	for(int i=n*n-1;i>=0;--i){
		if(ans.at(i)){
			c.at(ans.at(i)-1)=true;
			if(a.at(ans.at(i)-1)>0){
				flg=false;
				break;
			}
			continue;
		}
		if(flg1){
			bool flg2=true;
			rep(l,n){
				if(c.at(l) && b.at(l)){
					k=l;
					flg2=false;
					break;
				}
			}
			if(flg2){
				flg=false;
				break;
			}
			ans.at(i)=k+1;
			b.at(k)--;
		}
		else{
			while(a.at(x.at(j).second)==0){
				j++;
				if(j==n) break;
			}
			if(j==n){
				flg1=true;
				bool flg2=true;
				rep(l,n){
					if(c.at(l) && b.at(l)){
						k=l;
						flg2=false;
						break;
					}
				}
				if(flg2){
					flg=false;
					break;
				}
				ans.at(i)=k+1;
				b.at(k)--;
				continue;
			}
			ans.at(i)=x.at(j).second+1;
			a.at(x.at(j).second)--;
			b.at(x.at(j).second)--;
		}
	}
	if(flg){
		cout << "Yes" << endl;
		rep(i,n*n){
			if(i==n*n-1) cout << ans.at(i) << endl;
			else cout << ans.at(i) << " ";
		}
	}
	else cout << "No" << endl;
}

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

using namespace std;

int n, k, q, x[2005], ans = INT_MAX;
set< int > s;
set< int >::iterator it;
vector< int > v, vv;

int main() {
	s.insert(INT_MIN);
	scanf("%d%d%d", &n, &k, &q);
	for (int i = 0; i < n; i++) {
		scanf("%d", x + i);
		s.insert(x[i]);
	}
	for (it = s.begin(); it != s.end(); it++) {
		// printf("%d %d\n", *it, v.size());
		for (int j = 0; j < n; j++)
			if (x[j] > *it)
				vv.push_back(x[j]);
			else {
				if (vv.size() >= k) {
					sort(vv.begin(), vv.end());
					for (int l = 0; l < vv.size() - (k - 1); l++)
						v.push_back(vv[l]);
				}
				vv.clear();
			}
		if (vv.size() == n)
			v = vv;
		else if (vv.size() >= k) {
			sort(vv.begin(), vv.end());
			for (int l = 0; l < vv.size() - (k - 1); l++)
				v.push_back(vv[l]);
		}
		// printf("%d %d\n", *it, v.size());
		sort(v.begin(), v.end());
		if (v.size() >= q)
			ans = min(ans, v[q - 1] - v[0]);
		v.clear();
		vv.clear();
		// printf("%d %d\n", *it, v.size());
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define FORR(i, m, n) for (int i = m; i >= n; i--)
#define INF 1e9;
using namespace std;
typedef long long ll;
int main() {
    ll N,K;
    cin>>N>>K;
    pair<int,int> c[N];
    REP(i,N){
        cin>>c[i].first>>c[i].second;
    }
    sort(c,c+N);

    int ans;
    REP(i,N){
        int a=c[i].first;
        ll b=c[i].second;
        if(K-b<=0){
            ans=a;
            break;
        }
        K-=b;
    }
    cout<<ans;
     return 0; }

Measured memory_bytes: 1024
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define MP make_pair
#define F first
#define S second
#define ET cout << "\n"
#define MEM(i,j) memset(i,j,sizeof i)
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cerr << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

int arr[200005],seg[2][800005];
bitset<200005> high;
string ans;

void modify(int x,int l,int r,int rt,int t,int v)
{
	if(l==r)
		return seg[t][rt]=v,void();
	int m=l+r>>1;
	if(x<=m) modify(x,l,m,rt<<1,t,v);
	else modify(x,m+1,r,rt<<1|1,t,v);
	seg[t][rt]=max(seg[t][rt<<1],seg[t][rt<<1|1]);
}

int query(int L,int R,int l,int r,int rt,int t)
{
	if(L<=l&&R>=r) return seg[t][rt];
	int m=l+r>>1;
	if(R<=m) return query(L,R,l,m,rt<<1,t);
	if(L>m) return query(L,R,m+1,r,rt<<1|1,t);
	return max(query(L,R,l,m,rt<<1,t),query(L,R,m+1,r,rt<<1|1,t));
}

int main()
{jizz
	int n,mx=0,a,b,ma,mb,cnt;
	cin >> n;
	for(int i=1;i<=n;++i)
		cin >> arr[i],high[i]=(arr[i]>mx),mx=max(mx,arr[i]);
	for(int i=n;i>=1;--i)
	{
		a=query(arr[i]+1,n+1,1,n+1,1,0)+high[i]+1,b=query(arr[i]+1,n+1,1,n+1,1,1);
		if(b&1) b+=high[i]+1,modify(arr[i],1,n+1,1,b&1,b);
		modify(arr[i],1,n+1,1,a&1,a);
	}
	cnt=high.count();
	if(seg[cnt&1][1]<cnt)
		return cout << "-1\n",0;
	a=b=ma=mb=0;
	for(int i=1;i<=n;++i)
	{
		modify(arr[i],1,n+1,1,0,0),modify(arr[i],1,n+1,1,1,0);
		cnt-=high[i];
		int t=a-b+cnt+(arr[i]>ma);
		if(t>=0&&query(mb+1,n+1,1,n+1,1,t&1)>=t)
			a+=(arr[i]>ma),ma=max(ma,arr[i]),ans.pb('0');
		else if(t=b-a+cnt-(arr[i]>ma),t>=0&&query(max(ma,arr[i])+1,n+1,1,n+1,1,t&1)>=t)
			a+=(arr[i]>ma),ma=max(ma,arr[i]),ans.pb('0');
		else
			b+=(arr[i]>mb),mb=max(mb,arr[i]),ans.pb('1');
	}
	cout << ans << "\n";
}

Measured memory_bytes: 7812
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
public class Main{
	static BufferedReader br;
	static int cin() throws Exception
	{
		return Integer.valueOf(br.readLine().replaceAll("\\s", ""));
	}
	static int[] split() throws Exception
	{
		String[] cmd=br.readLine().split(" ");
		int[] ans=new int[cmd.length];
		for(int i=0;i<cmd.length;i++)
		{
			ans[i]=Integer.valueOf(cmd[i]);
		}                                              
		return ans;
	} 
	static long mod=1000000007;
	static long power(long x,long y) 
    { 
        long res = 1; 
        x = x % mod; 
        while (y > 0) { 
            if (y % 2 == 1) 
                res = (res * x) % mod; 
            y = y >> 1;
            x = (x * x) % mod; 
        } 
        return res%mod; 
    } 
    static long modInverse(long n) 
    { 
        return power(n, mod-2); 
    } 
    public static void main(String[] args) throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        String s=br.readLine();
        int ans=0;
        for(int i=0;i<3;i++)
        {
        	if(s.charAt(i)=='S')
        		continue;
        	int cnt=1;
        	for(int j=i+1;j<3;j++)
        	{
        		if(s.charAt(j)=='R')
        			cnt++;
        		else
        			break;
        	}
        	ans=Math.max(ans, cnt);
        }
        System.out.println(ans);
    }
}

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

int main(){
    int t;
    while(cin>>t&&t){
        int n,s,f,sum=0;
        cin>>n;
        for(int i=0;i<n;i++){
            cin>>s>>f;
            sum+=f-s;
        }
        if(sum>=t)cout<<"OK"<<endl;
        else cout<<t-sum<<endl;
    }
    return 0;
}

Measured memory_bytes: 3084
import java.util.Scanner


import scala.io.StdIn._

object Main extends App {

  val Array(n,m) = readLine().split(" ").map(_.toInt)
  val A = readLine().split(" ").map(_.toInt)

  def solve() = {
    val border = A.sum.toDouble / (4 * m)
    val cnt = A.count(_ >= border)
    if(cnt >= m) "Yes" else "No"
  }

  println(solve())

}



Measured memory_bytes: 55080
#include<iostream>

int main(){
	int arr[1000001] = {0, 1, 1, 1, 1, 1};
	for(int i=6;i<=1000000;i++){
		if((i%2 == 0 && arr[i/2]) ||
			 (i%3 == 0 && arr[i/3]) ||
			 (i%5 == 0 && arr[i/5])){
			arr[i] = 1;
		}else{
			arr[i] = 0;
		}
	}

	int m, n;
	while(std::cin >> m >> n, m){
		int res = 0;
		while(m <= n){
			if(arr[m]){
				res++;
			}
			m++;
		}
		std::cout << res << std::endl;
	}
}

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

int main(){
    int N,K,count;
    cin>>N>>K;
    vector<int> vec(N,0);
    count=0;
  
for(int i=0;i<K;i++){
  int d;
  cin>>d;
  for(int j=0;j<d;j++){
      int a;
      cin>>a;
      vec.at(a-1)+=1;
  }
}

for(int i=0;i<N;i++){
    if(vec.at(i)==0){
    count++;
    }
}

    cout<<count<<endl;    
}

Measured memory_bytes: 3632
def main():
    while True:
        H, W = map(int, input().split())
        if H == 0 and W == 0:
            break
        for i in range(H):
            col = ''
            for j in range(W):
                if i % 2 == 0:
                    if j % 2 == 0:
                        col += '#'
                    else:
                        col += '.'
                else:
                    if j % 2 == 0:
                        col += '.'
                    else:
                        col += '#'
            print(col)
        print()


main()



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

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

const long long MOD = 1000000007;

int main(){
  ll n;
  cin >> n;
  cout << ceil(n/2.0) << endl;
}


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

typedef long long int lli;
typedef unsigned long long int ulli;
typedef pair<int,int> pii;
typedef priority_queue< int, vector< int >, greater< int > >  minHeap;

#define ones(x) __builtin_popcount(x)
#define onesl(x) __builtin_popcountl(x)
#define onesll(x) __builtin_popcountll(x)

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define scn(n) scanf("%d",&n)
#define scnll(n) scanf("%lld",&n)
#define scn2(n,m) scanf("%d%d",&n,&m)
#define scn3(n,m,w) scanf("%d%d%d",&n,&m,&w)
#define scn2ll(n,m) scanf("%lld%lld",&n,&m)
#define atoz(v) v.begin(),v.end()
#define ratoz(v) v.rbegin(),v.rend()
#define Fill(a,v) memset(a,v,sizeof(a))
#define fi first
#define se second
#define inf 1e9
#define pi acos(-1.0)
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define mod 1000000007
#define FastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define bug(x) cerr << __LINE__ << " says: " << #x << " = " << (x) << "\n"

int Set(int N,int pos)
{
    return N=N | (1<<pos);
}
int reset(int N,int pos)
{
    return N = N & ~(1<<pos);
}
bool check(int N,int pos)
{
    return (bool)(N & (1<<pos));
}

inline int addmod(lli x,lli y)
{
    return (x%mod + y%mod)%mod;
}
inline int submod(lli x,lli y)
{
    return (x%mod - y%mod + mod)%mod;
}
inline int mulmod(lli x,lli y)
{
    return (x%mod * y%mod)%mod;
}


inline int nextSubMask(int i, int mask)
{
    return (i-1)&mask;   /// returns next  submask
}

template<typename T>
void we_r_done(T mssg)
{
    cout<<mssg;
    exit(0);
}


int main()
{
    ///freopen("output.txt","w",stdout);
    //freopen("input.txt","r",stdin);
    FastIO;

    int H,n;
    while(cin>>H>>n){
        int a[n],b[n];
        for(int i=0; i<n; i++) cin>>a[i]>>b[i];
        vector<lli>dp(H+5,0);
        for(int i=1; i<=H; i++){
            dp[i] = 1e18;
            for(int j=0; j<n; j++){

                dp[i] = min(dp[i] , dp[max(0,i-a[j])] + b[j]);
            }
        }
        cout<<dp[H]<<endl;
    }


    return 0;
}

///sin and cos expect input in radians not degrees. so use , sin(degrees * pi / 180)
///using bs = bitset<MX>; // how many distinct number can be form?
///sort(atoz(v), [](const data x, const data y){return (x.a==y.a?x.b>y.b : x.a<y.a);});


Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
 
const int INF = 100000000;
int a[101][101];

void solve(int n) {
  
  for(int i = 0 ; i < n ; i++)
    for(int j = 0 ; j < n ; j++)
      a[i][j] = INF;
  
  for(int i = 0 ; i < n ; i++) {
    int r, k;
    cin >> r >> k;
    for(int j = 0 ; j < k ; j++) {
      int t;
      cin >> t;
      a[r-1][t-1] = 1;
    }
  }
  
  for(int k = 0 ; k < n ; k++)
    for(int i = 0 ; i < n ; i++)
      for(int j = 0 ; j < n ; j++)
	a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
  
  int m;
  cin >> m;
  for(int i = 0 ; i < m ; i++) {
    int s, d, v;
    cin >> s >> d >> v;
    if(a[s-1][d-1]+1 > v) cout << "NA" << endl;
    else cout << a[s-1][d-1]+1 << endl;
  }
}

int main() {
  int n;
  while(cin >> n) {
    solve(n);
  }
  return 0;
}

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

#define REP(i, n) for(int (i)=0;(i)<(n);++(i))
#define REPV(iter, v) for(auto (iter)=(v).begin(); (iter)!=(v).end();++(iter))
#define ALL(v) (v).begin(),(v).end()

#define MOD 1000000007

using namespace std;

typedef long long ll;

int main()
{
    ll N, W;
    cin >> N >> W;
    vector<ll> w(N), v(N);
    REP(i, N) cin >> w[i] >> v[i];

    map<ll, ll> dp[N + 1];
    dp[0][0] = 0;
    for (ll i = 1; i <= N; ++i)
    {
        for (ll j = 0; j < i; ++j)
        {
            for (ll k = w[0] * j; k <= w[0] * j + 3 * j; ++k)
            {
                if (dp[i - 1].find(k) != dp[i - 1].end())
                {
                    if (dp[i - 1].find(k + w[i - 1]) != dp[i - 1].end())
                    {
                        dp[i][k + w[i - 1]] = max(dp[i - 1][k + w[i - 1]], dp[i - 1][k] + v[i - 1]);
                    }
                    else
                    {
                        dp[i][k + w[i - 1]] = dp[i - 1][k] + v[i - 1];
                    }

                    dp[i][k] = max(dp[i - 1][k], dp[i][k]);
                }
            }
        }
    }
    ll ans = 0;
    REPV(it, dp[N])
    {
        if (it->first <= W)
        {
            ans = max(ans, it->second);
        }
    }

    cout << ans << endl;
}


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

using namespace std;

int main()
{
    int a,b,c,k,n,i,ans=0,cnt=0;
    scanf("%d%d%d%d",&a,&b,&c,&k);
    while(1){
        if(b<=a){
            b=b*2;
            cnt++;
        }
        else break;
    }
    while(1){
        if(c<=b){
            c=c*2;
            cnt++;
        }
        else break;
    }
    if(cnt<=k) printf("Yes\n");
    else printf("No\n");

}


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

int main(){
    int N,L;
    cin >> N >> L;
    int ans = 0;
    for (int i = 1; i <= N; i++) {
        ans += L + i - 1;
    }
    if(L >= 0) {
        cout << ans - L  << "\n"; 
    }else{
        if(N > abs(L)) {
            cout << ans << "\n"; 
        }else{
            cout << ans - (N + L - 1) << "\n";
        }
    }
}

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

using namespace std;

const double EPS = 1e-8;
const double INF = 1e12;
typedef complex<double> P;
namespace std {
  bool operator < (const P& a, const P& b) {
      return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
    }
}
double cross(const P& a, const P& b) {
  return imag(conj(a)*b);
}
double dot(const P& a, const P& b) {
  return real(conj(a)*b);
}

struct L : public vector<P> {
  L(const P &a, const P &b) {
      push_back(a); push_back(b);
    }
};

P projection(const L &l, const P &p) {
  double t = dot(p-l[0], l[0]-l[1]) / norm(l[0]-l[1]);
  return l[0] + t*(l[0]-l[1]);
}

int main(){
    double x1,y1,x2,y2,xq,yq;
    while(scanf("%lf,%lf,%lf,%lf,%lf,%lf", &x1,&y1,&x2,&y2,&xq,&yq) != EOF){
        P a(x1,y1), b(x2, y2);
        L l(a, b);
        P p(xq, yq);

        P q = projection(l, p);
        if(p.real() < q.real()) p.real() += (q.real()-p.real())*2;
        else p.real() -= (p.real()-q.real())*2;
        if(p.imag() < q.imag()) p.imag() += (q.imag()-p.imag())*2;
        else p.imag() -= (p.imag()-q.imag())*2;
        printf("%lf %lf\n", p.real(), p.imag());
    }
}

Measured memory_bytes: 1264
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

func main() {
	sc.Split(bufio.ScanWords)
	n := nextInt()
	a := nextInts(n)
	sort.Sort(sort.Reverse(sort.IntSlice(a)))
	ans := 0
	for i := range a {
		if i&1 == 0 {
			ans += a[i]
		} else {
			ans -= a[i]
		}
	}
	puts(ans)
	wt.Flush()
}

var (
	sc  = bufio.NewScanner(os.Stdin)
	rdr = bufio.NewReaderSize(os.Stdin, 1000000)
	wt  = bufio.NewWriter(os.Stdout)
)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	i, _ := strconv.Atoi(next())
	return i
}

func nextFloat64() float64 {
	f, _ := strconv.ParseFloat(next(), 64)
	return f
}

func nextInts(n int) []int {
	slice := make([]int, n)
	for i := 0; i < n; i++ {
		slice[i] = nextInt()
	}
	return slice
}

func nextMega() string {
	buf := make([]byte, 0, 1000000)
	for {
		l, p, _ := rdr.ReadLine()
		buf = append(buf, l...)
		if !p {
			break
		}
	}
	return string(buf)
}

func putf(format string, a ...interface{}) {
	fmt.Fprintf(wt, format, a...)
}

func puts(a ...interface{}) {
	fmt.Fprintln(wt, a...)
}


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

#define rep(i,begin,end) for(int i=begin; i<end; i++)
#define revrep(i,begin,end) for(int i=begin; i>end; i--)
#define lld long long int

int main(){
    int n;
    scanf("%d", &n);
    int f = 1;
    rep(i, 0, n){
        int a;
        scanf("%d", &a);
        if(a%2 == 0){
            if(a%3 != 0 && a%5 != 0){
                f = 0;
            }
        }
    }
    printf(f ? "APPROVED" : "DENIED");

    return 0;
}

Measured memory_bytes: 128
#include<iostream>

using namespace std;

int main(void) {
    int N, flag=0;
    int max_idx=1, max_div = 0, temp_num = 0, counter=0;

    cin >> N;

    for (int i = 1; i <= N; i++) {

        temp_num = i;
        flag = 1;
        while(flag) {
            if (temp_num % 2 == 0) {
                temp_num = temp_num / 2;
                counter += 1;
            }
            else {
                if (counter > max_div) {
                    max_div = counter;
                    max_idx = i;
                }
                counter = 0;
                flag = 0;
            }
        }
    }

    cout << max_idx << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
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<P,int> 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=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

template <class T>
class RMQ{
	private:
	int n;
	vector<T> rmq;
	T dfs(int a,int b,int k,int l,int r){
		if(r<=a||b<=l) return INF;
		if(a<=l&&r<=b) return rmq[k];
		int m=(l+r)/2;
		return min(dfs(a,b,k*2+1,l,m),dfs(a,b,k*2+2,m,r));
	}
	public:
	RMQ(int n_){
		n=1;
		while(n<n_) n*=2;
		rmq=vector<T>(2*n-1,inf);
	}
	void Update(int k,T x){
		k+=n-1;
		rmq[k]=x;
		while(k>0){
			k=(k-1)/2;
			rmq[k]=min(rmq[k*2+1],rmq[k*2+2]);
		}
	}
	T Query(int a,int b){
		return dfs(a,b,0,0,n);
	}
	T Open(int k){
		return rmq[k+n-1];
	}
};

ll n,m,t;
vl a;

int main(){
	cin>>n>>m>>t;
	a=vl(n);
	for(int i=0;i<n;i++) cin>>a[i];
	RMQ<ll> r(n+1),R(n+1);
	r.Update(0,0);
	R.Update(0,-2*a[0]);
	for(int i=0;i<n;i++){
		int it=lower_bound(a.begin(),a.end(),a[i]-t/2)-a.begin();
		ll res=min(R.Query(0,it)+2*a[i],r.Query(it,i+1)+t);
		r.Update(i+1,res);
		if(i!=n-1) R.Update(i+1,res-2*a[i+1]);
	}
	cout<<r.Open(n)+m<<endl;
}

Measured memory_bytes: 5248
#include<bits/stdc++.h>
#define X first
#define Y second
#define pb emplace_back
#define FOR(i,a,b) for(int (i)=(a);i<(b);++(i))
#define EFOR(i,a,b) for(int (i)=(a);i<=(b);++(i))
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define rreps(X,S,Y) for (int (X) = (Y)-1;(X) >= (S);--(X))
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define eb emplace_back
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef ll LL;
typedef pii PII;
typedef pll PLL;
template<class T> using vv=vector<vector<T>>;
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}
const ll MOD=1e9+7;

int N;
int A[114514];
const char *win[] = {"First", "Second"};

int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a%b);
}

void Eval(int v) {
  //printf("v: %d\n", v);
  //printf("A: ");
  //rep(i, N) {
  //  printf("%d ", A[i]);
  //}puts("");

  int res = 1 - N%2;

  int cnt = 0;
  int m = 0;
  bool has_one = false;
  rep(i, N) {
    cnt += A[i]%2;
    has_one |= (A[i] == 1);
    m ^= A[i]%2;
  }

  if (res == m && (N > 2 || cnt < 2)) {
    puts(win[v]);
    return;
  } else if (has_one || cnt > 1) {
    puts(win[v^1]);
    return;
  }

  if (cnt == 2) {
    assert(N == 2);
    assert(A[0]%2 == 1);
    assert(A[0] > 1);
    A[0]--;
  } else {
    assert(cnt == 1);
  
    int num = 0;
    int g = 0;
    rep(i, N) {
      assert(A[i] != 1);
      if (A[i]%2 == 1) {
        A[i]--;
        num++;
      }
      g = gcd(g, A[i]);
    }
    assert(num == 1);
    assert(g > 1);
    rep(i, N) {
      A[i] /= g;
    }
  }
  Eval(v^1);
}

int main() {
  scanf("%d", &N);
  rep(i, N) {
    scanf("%d", &A[i]);
  }

  if (N == 1) {
    puts(win[A[0] == 1]);
    return 0;
  }

  Eval(0);
}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int inf = 1e9;

struct MincostFlow{
    struct edge{
        int to, rev;
        int cap, cost;
        edge(int to, int rev, int cap, int cost)
            :to(to),rev(rev),cap(cap),cost(cost){}
        edge(){}
    };
    
    int n;
    vector<vector<edge>> graph;

    MincostFlow(int n):n(n){
        graph.resize(n);
    }
    void add_edge(int from, int to, int cap, int cost){
        graph[from].emplace_back(to, graph[to].size(), cap, cost);
        graph[to].emplace_back(from, (int)graph[from].size()-1, 0, -cost);
    }
    int exec(int s, int g, int f){
        int res = 0;
        while(f > 0){
            vector<int> prevv(n), preve(n);
            vector<int> mincost(n, inf);
            mincost[s] = 0;
            while(1){
                bool update = false;
                for(int i=0; i<n; i++){
                    if(mincost[i] == inf) continue;
                    for(int j=0; j<(int)graph[i].size(); j++){
                        edge &e = graph[i][j];
                        if(e.cap>0 && mincost[i] +e.cost < mincost[e.to]){
                            mincost[e.to] = mincost[i] +e.cost;
                            prevv[e.to] = i;
                            preve[e.to] = j;
                            update = true;
                        }
                    }
                }
                if(!update) break;
            }
            if(mincost[g] == inf){
                return -1;
            }
         
            int d = f;
            for(int v=g; v!=s; v=prevv[v]){
                d = min(d, graph[prevv[v]][preve[v]].cap);
            }
            f -= d;
            res += d*mincost[g];
            for(int v=g; v!=s; v=prevv[v]){
                edge &e = graph[prevv[v]][preve[v]];
                e.cap -= d;
                graph[v][e.rev].cap += d;
            }
        }
        return res;
    }
};

int main(){
    while(1){
        int n;
        cin >> n;
        if(n == 0) break;

        vector<vector<int>> len(n, vector<int>(3));
        for(int i=0; i<n; i++){
            for(int j=0; j<3; j++){
                cin >> len[i][j];
            }
            sort(len[i].begin(), len[i].end());
        }
        MincostFlow mcf(2*n +2);
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                bool ok = true;
                for(int k=0; k<3; k++){
                    if(len[i][k] >= len[j][k]) ok = false;
                }
                if(ok){
                    mcf.add_edge(i, n+j, 1, 0);
                }
            }
        }
        for(int i=0; i<n; i++){
            mcf.add_edge(2*n, i, 1, 0);
            mcf.add_edge(n+i, 2*n+1, 1, 0);
            mcf.add_edge(i, 2*n+1, 1, len[i][0]*len[i][1]*len[i][2]);
        }
        cout << mcf.exec(2*n, 2*n+1, n) << endl;
    }
    return 0;
}



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

int main(){
  int n,ans;
  double sum=0;
  int a[10000];
  while(1){
    cin>>n;
    if(n==0) break;
    sum=ans=0;
    for(int i=0;i<10000;i++) a[i]=0;
    for(int i=0;i<n;i++){
      cin>>a[i];
      sum+=a[i];
    }
    sum/=(double)n;
    for(int i=0;i<n;i++){
      if(sum>=a[i]){
	ans++;
      }
    }
    cout<<ans<<endl;
  }
  return 0;
}



Measured memory_bytes: 3048
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define ALL(c) (c).begin(), (c).end()
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())

using namespace std;
typedef long long ll;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const int INF = (1 << 29);
const long long INFL = (1LL<<60);
const double eps = (1e-9);

int main(int argc, char* argv[])
{
  vector<int> v(3);
  rep(i, 3) {
    cin >> v[i];
  }

  int ans = 0;

  // 偶奇を揃える
  if (v[0] % 2 != v[1] % 2 && v[0] % 2 != v[2] % 2) {
    v[1]++;
    v[2]++;
    ans++;
  } else if (v[1] % 2 != v[0] % 2 && v[1] % 2 != v[2] % 2) {
    v[0]++;
    v[2]++;
    ans++;
  } else if (v[2] % 2 != v[0] % 2 && v[2] % 2 != v[1] % 2) {
    v[0]++;
    v[1]++;
    ans++;
  }

  // 一番大きいものに値を揃える
  sort(ALL(v));
  ans += (v[2] - v[0]) / 2;
  ans += (v[2] - v[1]) / 2;

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<set>
#include<algorithm>
#include<cstring>

using namespace std;


int main() {
	int n;
	cin >> n;
	int t1, t2, x1, x2, y1, y2, d;
	t2 = 0;
	x2 = 0;
	y2 = 0;
	for (int i = 0; i < n; i++) {
		t1 = t2;
		x1 = x2;
		y1 = y2;
		cin >> t2 >> x2 >> y2;
		d = t2 - t1 - abs(x1 - x2) - abs(y1 - y2);
		if (d % 2 != 0 || d < 0) {
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	return 0;
}


Measured memory_bytes: 256