akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#include<functional>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cassert>
#include<ctime>
using namespace std;

#define mind(a,b) (a>b?b:a)
#define maxd(a,b) (a>b?a:b)
#define absd(x) (x<0?-(x):x)
#define pow2(x) ((x)*(x))
#define rep(i,n) for(int i=0; i<n; ++i)
#define repr(i,n) for(int i=n-1; i>=0; --i)
#define repl(i,s,n) for(int i=s; i<=n; ++i)
#define replr(i,s,n) for(int i=n; i>=s; --i)
#define repf(i,s,n,j) for(int i=s; i<=n; i+=j)
#define repe(e,obj) for(auto e : obj)

#define SP << " " <<
#define COL << " : " <<
#define COM << ", " <<
#define ARR << " -> " <<
#define PNT(STR) cout << STR << endl
#define POS(X,Y) "(" << X << ", " << Y << ")"
#define DEB(A) " (" << #A << ") " << A
#define DEBREP(i,n,val) for(int i=0; i<n; ++i) cout << val << " "; cout << endl
#define ALL(V) (V).begin(), (V).end()
#define INF 1000000007
#define INFLL 1000000000000000007LL
#define EPS 1e-9

typedef unsigned int uint;
typedef unsigned long ulong;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define P_TYPE int
typedef pair<P_TYPE, P_TYPE> P;
typedef pair<P, P_TYPE> PI;
typedef pair<P_TYPE, P> IP;
typedef pair<P, P> PP;
typedef priority_queue<P, vector<P>, greater<P> > pvqueue;

#define N 404

int n;
ll a[N], b[N];

ll memo[N][N];
ll dfs(int p, int q) {
  ll r = INFLL;
  if(p+1 == q) {
    return 0;
  }
  if(memo[p][q] != -1) {
    return memo[p][q];
  }
  repl(k, p+1, q-1) {
    r = min(r, dfs(p, k)+dfs(k, q));
  }
  return memo[p][q] = r + b[q] - b[p];
}

int main() {
  cin >> n;
  rep(i, n) cin >> a[i];
  rep(i, n) b[i+1] = b[i] + a[i];
  rep(i, n+1) rep(j, n+1) memo[i][j] = -1;
  cout << dfs(0, n) << endl;
  return 0;
}

Measured memory_bytes: 1664
n, k = (int(v) for v in input().split())
x = [int(v) for v in input().split()]

m = 99999999999999999999
for l in range(n-k+1):
    r = l + k - 1
    m = min(m, abs(x[l]) + abs(x[r] - x[l]))
    m = min(m, abs(x[r]) + abs(x[l] - x[r]))
print(m)

Measured memory_bytes: 14384
using System;
using System.Linq;
using System.Collections.Generic;

using E = System.Linq.Enumerable;

public class Program
{
    const int Mod = (int)1e9 + 7;

    public static void Main()
    {
        var nm = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();
        var n = nm[0];
        var m = nm[1];
        var ss = new int[m];
        for (int i = 0; i < ss.Length; i++)
        {
            ss[i] = int.Parse(Console.ReadLine());
        }

        var dp = new long[2] { 1, 0 };
        int k = 0;
        int j = 0;
        for (int i = 0; i <= n; i++)
        {
            if (j < ss.Length && ss[j] == i + 1)
            {
                dp[k ^ 1] = 0;
                j++;
            }
            else
            {
                dp[k ^ 1] = (dp[k] + dp[k ^ 1]) % Mod;
            }

            k ^= 1;
        }

        Console.WriteLine(dp[k ^ 1]);
    }
}


Measured memory_bytes: 13536
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):

    A = [0] + A + [0]
    cost = 0
    for i in range(1, len(A)):
        cost += abs(A[i]-A[i-1])
    # print(cost)

    x = sorted(A)

    for i in range(1,len(A)-1):
        if((A[i-1] <= A[i] <= A[i+1]) or (A[i-1] >= A[i] >= A[i+1])):
            print(cost)
        else:
            print(cost-2*min(abs(A[i+1]-A[i]),abs(A[i]-A[i-1])))


    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()


Measured memory_bytes: 16712
using System;
using System.Linq;
using System.Collections.Generic;
using System.Numerics;
using static System.Console;

class Program {
    static Scanner sc = new Scanner();

    internal static void Main(string[] args) {
        var N = sc.nextInt();
        var a = sc.ArrayInt(N);
        var lst = new List<int>();

        var free = 0;
        for (int i = 0; i < N; i++) {
            if (a[i] >= 3200) {
                free++;
                continue;
            }
            lst.Add(a[i] / 400);
        }
        lst = lst.Distinct().ToList();
        Write(Math.Max(lst.Count(), 1) + " ");
        WriteLine(lst.Count + free);
    }
}




class Scanner {
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner() {
        s = new string[0];
        i = 0;
    }

    public string next() {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int nextInt() {
        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0) {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++) {
            Array[i] = nextInt() + add;
        }
        return Array;
    }

    public long nextLong() {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0) {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++) {
            Array[i] = nextLong() + add;
        }
        return Array;
    }

    public double nextDouble() {
        return double.Parse(next());
    }

    public double[] ArrayDouble(int N, double add = 0) {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++) {
            Array[i] = nextDouble() + add;
        }
        return Array;
    }
}

Measured memory_bytes: 13280
n = int(input())
s = input()

cnt = 1
cp = s[0]
for i in range(1, n):
  if s[i] != cp:
#    print ('CNT INC at ' + str(s[i]))
    cnt += 1
  cp = s[i]
#  print ('CP=' + str(cp))

print (cnt)

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

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    int a,b;
    cin>>a>>b;
    int areaw,areac,u,l;
    areaw=a*a;
    areac=(b*a)+(b*a);
    if(areac>areaw)
    {
        cout<<0<<"\n";
    }
    else
        {u=areaw-areac;
        l=u/a;
        cout<<l<<"\n";
        }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
 
typedef long long ll;
#define READ(a) int a; cin >> a;
#define READARR(a, n) int a[(n) + 1]; FOR(i, 1, (n)) {cin >> a[i];}
#define READMAT(a, n, m) int a[n + 1][m + 1]; FOR(i, 1, n) {FOR(j, 1, m) cin >> a[i][j];}
#define pb(x) push_back(x)
#define vi vector <int>
#define pi pair <int, int>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
const ll inf = 1e18;
const ll mod = 1e9 + 7;
 
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n, a, b;
	cin >> n >> a >> b;
	cout << min(n*a, b);
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#define long long int int
using namespace std;

const int maxk = 18;

class edge{
public:
  int t,c,l;

  edge(int to, int color, int length) : t(to),c(color),l(length) {}
};

int depth[100005];
int parent[maxk + 1][100005];
vector<edge> g[100005];
int dist[100005];

void dfs(int v, int prev, int d) {
  depth[v] = d;
  parent[0][v] = prev;
  
  for(int i = 0; i < g[v].size(); i++) {
    int u = g[v][i].t;
    if(u != prev) {
      dist[u] = dist[v] + g[v][i].l;
      dfs(u,v,d+1);
    }
  }
  
  return;
}

  

void init(int V) {
  dfs(0,-1,0);
  
  for(int k = 0; k < maxk; k++) {
    for(int i = 0; i < V; i++) {
      if(parent[k][i] < 0) parent[k+1][i] = -1;
      else parent[k+1][i] = parent[k][parent[k][i]];
    }
  }
  return;
}

int lca(int u, int v) {
  if(depth[u] > depth[v]) swap(u,v);
  for(int k = 0; k < maxk; k++) {
    if((depth[v] - depth[u]) >> k & 1) {
      v = parent[k][v];
    }
  }
  if(u == v) return u;
  for(int k = maxk - 1; k >= 0; k--) {
    if(parent[k][u] != parent[k][v]) {
      u = parent[k][u];
      v = parent[k][v];
    }
  }
  return parent[0][u];
}


int n,q;

typedef pair<int,int> P;
map<int,P> s[100005];

int C[100005];
int D[100005];


void dfs2(int v, int prev) {
 
  for(auto itr = s[v].begin(); itr != s[v].end(); ++itr) {
    int u = itr->first;
    itr->second.first = C[u];
    itr->second.second = D[u];
    
  }

  for(int i = 0; i < g[v].size(); i++) {
    int u = g[v][i].t;
    if(u != prev) {
      C[g[v][i].c]++;
      D[g[v][i].c] += g[v][i].l;
      dfs2(u,v);
      C[g[v][i].c]--;
      D[g[v][i].c] -= g[v][i].l;
    }
  }
  
}

int x[100005];
int y[100005];
int u[100005];
int v[100005];

signed main() {
  cin >> n >> q;



  for(int i = 0; i < n - 1; i++) {
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    a--,b--;
    g[a].push_back(edge(b,c,d));
    g[b].push_back(edge(a,c,d));
  }

    init(n);
 
  for(int i = 0; i < q; i++) {
    cin >> x[i] >> y[i] >> u[i] >> v[i];
    u[i]--,v[i]--;
   
    s[u[i]][x[i]] = P(0,0);
    s[v[i]][x[i]] = P(0,0);
    int t = lca(u[i],v[i]);
    s[t][x[i]] = P(0,0);
  }
  dfs2(0,-1);

  for(int i = 0; i < q; i++) {
    int tmp = s[u[i]][x[i]].first * y[i];
    int tmp2 = s[v[i]][x[i]].first * y[i];
    int tmp3 = s[lca(u[i],v[i])][x[i]].first * y[i];

    int tmp4 = s[u[i]][x[i]].second;
    int tmp5 = s[v[i]][x[i]].second;
    int tmp6 = s[lca(u[i],v[i])][x[i]].second;
    
    int di = dist[u[i]] + dist[v[i]] - 2 * dist[lca(u[i],v[i])];
    int di2 = tmp4 + tmp5 - 2 * tmp6;
    int di3 = tmp + tmp2 - 2 * tmp3;
    
    
    cout << di - di2 + di3 << endl;
    
  }
}
			      


Measured memory_bytes: 40120
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<math.h>
#include<tuple>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	cout << max(max(a, b), c) - min(min(a, b), c) << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long a[100005],b[100005];
bool cmp(int x,int y)
{
    return x>y;
}
int main()
{
    long long n,h;
    while(cin>>n>>h){
        for(int i=0;i<n;i++){
            cin>>a[i]>>b[i];
        }
        sort(a,a+n,cmp);
        long long maxn=a[0],s=0;
        sort(b,b+n,cmp);
        for(int i=0;i<n;i++){
            if(b[i]>=maxn&&h>=maxn){
                h-=b[i];
                s++;
            }
        }
        if(h>=0) s+=ceil(h*1.0/maxn);
        cout<<s<<endl;
    }
    return 0;
}


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

public class Main {
	static int mod = (int) 1e9 + 7;
	static int DX[] = { -1, 0, 1, 0 }, DY[] = { 0, -1, 0, 1 };

	public static void main(String[] args) {
		FastScanner fs = new FastScanner(System.in);
		String s = fs.next();
		for(int i=0;i<s.length()-1;i++) {
			if(s.charAt(i)==s.charAt(i+1)) {
				System.out.println("Bad");
				return;
			}
		}
		System.out.println("Good");
	}
}

//高速なScanner
class FastScanner {
	private BufferedReader reader = null;
	private StringTokenizer tokenizer = null;

	public FastScanner(InputStream in) {
		reader = new BufferedReader(new InputStreamReader(in));
		tokenizer = null;
	}

	public String next() {
		if (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				tokenizer = new StringTokenizer(reader.readLine());
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}

	public String nextLine() {
		if (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				return reader.readLine();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken("\n");
	}

	public long nextLong() {
		return Long.parseLong(next());
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}

	public int[] nextIntArray(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = nextInt();
		return a;
	}

	public long[] nextLongArray(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = nextLong();
		return a;
	}
}

Measured memory_bytes: 22484
#include <bits/stdc++.h>
using namespace std;
int main() {
	int n, t;
	long long int x = 0;
	cin >> n >> t;
	vector <int> arr(n);

	for(int i = 0; i < n; i++) cin >> arr[i];
	for(int i = 0; i < n - 1; i++) {
		if(arr[i] + t <= arr[i + 1]) {
			x += t;
		} else {
			x += arr[i + 1] - arr[i];
		}
	}
	x += t;
	cout << x << endl;

	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int a, b;
    cin >> a >> b;
    if(a <= 5)
        cout << 0 << endl;
    else if(a <= 12)
        cout << b / 2 << endl;
    else
        cout << b << endl;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
Bridge = []
for i in range(M):
    a, b = map(int, input().split())
    Bridge.append((a, b))
now = -10000000000
Bridge.sort(key=lambda x: x[1])
ans = 0

for i in range(M):
    if Bridge[i][0] >= now:
        ans += 1
        now = Bridge[i][1]

print(ans)

Measured memory_bytes: 56792
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define repone(i,n) for(int i=1;i<(int)(n);++i)
#define repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define Rep(j,n) for(int j=0;j<(int)(n);++j)
#define Repo(j,o,n) for(int j=o;j<(int)(n);++j)
#define Repone(j,n) for(int j=1;j<(int)(n);++j)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define int long long
#define pb(a) push_back(a)
#define eraser(v,i) (v).erase(v.begin()+(i))
#define pbpair(a,b) push_back(make_pair(a,b))
#define MOD 1000000007
#define MODB 998244353
#define INF 9223372036854775807
signed main()
{
  double x=0,y=1,z=0,w=0,n=0,m=0;
  double a=0,b=0;
  std::cin >> x;
  std::vector<pair<double,double> > v(x);
for(int i=x;i>0;i--){
  y*=i;
  z+=i;
}
z-=x;
  rep(i,x){
    std::cin >> v[i].first>>v[i].second;
  }
  n = y*(x-1)/z;
  rep(i,x){
    Repo(j,i+1,x){
      a+=sqrt((v[i].first-v[j].first)*(v[i].first-v[j].first)+(v[i].second-v[j].second)*(v[i].second-v[j].second));
    }
  }
  printf("%.15f\n",a*(double)n/(double)y);
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#define rep(i,n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i < (n); i++)
#define repm(i, m, n) for (int i = (m); i < (n); i++)
#define rep_rev(i, n) for (int i = int (n); i >= 0; i--)
typedef long long ll;
using namespace std;

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

	if (a > 9 || b > 9) {
		cout << -1 << endl;
		return 0;
	}

	cout << a * b << endl;

	return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

using ll = long long;
using P = pair<int, int>;
using T = tuple<int, int, int>;

template <class T> inline T chmax(T &a, const T b) {return a = (a < b) ? b : a;}
template <class T> inline T chmin(T &a, const T b) {return a = (a > b) ? b : a;}

constexpr int MOD = 1e9 + 7;
constexpr int inf = 1e9;
constexpr long long INF = 1e18;
constexpr double pi = acos(-1);
constexpr double EPS = 1e-10;

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

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

    int ans = 0;
    string s, t; cin>>s>>t;
    for(int i=0; i<3; i++){
        ans += (s[i] == t[i]);
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
import collections
n,p=map(int,input().split())
def prime_factors(n):
  i=2
  factors=[]
  while i**2<=n:
    if n%i!=0:
      i+=1
    else:
      n//=i
      factors.append(i)
  if n>1:
    factors.append(n)
  return factors
c=collections.Counter(prime_factors(p))
ans=1
for pp in c.keys():
  ans*=pp**(c[pp]//n)
print(ans)

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

int main(){
  int x,y,z;
  cin >> x >> y;
  z = y-2*x;
  if(z>=0 && z%2==0 && 4*x>=y){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 3632
#include<stdio.h>
int h,w;
char a[105][105];
int main(){
	scanf("%d %d ",&h, &w);
	if(h == 0 && w == 0){
		printf("#");
		return 0;
	}
	for( int i = 1 ; i <= h ; i++){
		scanf("%s",a[i] + 1);
		a[i][0] = '#';
		a[i][w + 1] = '#';
		a[i][w + 2] = '\0';
	}
	for( int i = 0 ; i <= h+1 ; i++){
		if(i != 0 && i != h+1)
			for(int j = 0 ; a[i][j] != '\0'; j++)
			printf("%c",a[i][j]);
		else
			for(int j = 0 ; j <= w+1 ; j++)printf("#");

		if(i != h+1)printf("\n");
	}
}


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

S = input()

if S[0] == "A" and S[2:-1].count("C") == 1:
    S = list(S)
    for i in range(len(S)):
        if not S[i].islower() and S[i] != "A" and S[i] != "C":
            print("WA")
            exit()
    print("AC")
else:
    print("WA")

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

using namespace std; 

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef vector<PII> VPII;
typedef long long LL;
typedef priority_queue<int> PQ_DESC;
typedef priority_queue<int, vector<int>, greater<int>> PQ_ASC;
typedef priority_queue<PII> PQ_DESC_PII;
typedef priority_queue<PII, vector<PII>, greater<PII>> PQ_ASC_PII;

#define ALL(c) (c).begin(),(c).end()
#define PB push_back
#define MP make_pair
#define SORT_ASC(c) sort(ALL(c))
#define SORT_DESC(c) sort(ALL(c), greater<typeof(*((c).begin()))>())
#define SIZE(a) int((a).size())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ROF(i,a,b) for(int i=(b-1);i>=(a);--i)
#define REP(i,n) FOR(i,0,n)
#define PER(i,n) ROF(i,0,n)

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int LARGE_INT = 1e9+100;
const int INF = 2e9+100;
const LL INF_LL = (LL)INF * 300 * 300;
const int MOD = 1e9+7;

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

LL modpow(LL a, LL n) {
    LL res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}


void Main()
{
    int n;cin>>n;
    deque<int> q;

    REP(i,n){
        int a;cin>>a;
        if(i%2 == 0){
            q.push_back(a);
        }
        else{
            q.push_front(a);
        }
    }

    REP(i,n){
        if(i!=0){
            cout<<" ";
        }
        if(n%2 == 0){
            cout << q.front();
            q.pop_front();
        }
        else{
            cout << q.back();
            q.pop_back();
        }
    }
    cout<<endl;



	return;
}

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

Measured memory_bytes: 3072
/*
 * 17-1-22_AGC009_B.cpp
 *
 *  Created on: 2017/01/22
 *      Author: ryoma
 */

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;

int N;
int a[100010];
int dp[100010];
vector<int> g[100010];

bool compare(const int l,const int r){
	return dp[l]>dp[r];
}

int dfs(int v){
	if(g[v].empty())
		return dp[v] = 0;
	for(auto u:g[v]){
		dfs(u);
	}
	sort(g[v].begin(),g[v].end(),compare);
	int res=-1;
	for(int i=0;i<(int)g[v].size();i++){
		res = max(res,dp[g[v][i]] + i+1);
	}
	return dp[v] = res;
}

int main(){
	cin >> N;
	for(int i=1;i<N;i++){
		cin >> a[i];
		a[i]--;
		g[a[i]].push_back(i);
	}
	int ans = dfs(0);
	cout << ans <<endl;
	return 0;
}




Measured memory_bytes: 11136
# import 周り
from fractions import gcd

# 定数関係
mod = 10 ** 9 + 7

# 補助関数
def inv(a):
    b, u, v = mod, 1, 0
    while b != 0:
        t = a // b
        a, b = b, a - t * b
        u, v = v, u - t * v
    return u

if __name__ == '__main__':
    #入力関係
    n = int(input())
    A = list(map(int, input().split()))

    U, V = 0, 1
    for ele in A:
      V = V * ele // gcd(V, ele) # LCMを計算
      U += inv(ele)
    V %= mod
    print(U * V % mod)


Measured memory_bytes: 6112
N = int(input())
A = list(map(int, input().split()))

a1, a2, a4 = 0, 0, 0
for a in A:
  if a % 2 == 0:
    if a % 4 == 0:
      a4 += 1
    else:
      a2 += 1
  else:
    a1 += 1
#print("a1, a2, a4:", a1, a2, a4)

if a4 >= a1:
  print("Yes")
else:
  if a1 - a4 == 1:
    if a2 == 0:
      print("Yes")
    else:
      print("No")
  else:
    print("No")

Measured memory_bytes: 62576
import sys
# sys.stdin = open('input.txt')

n = int(input())
matrix = [[0]*n for i in range(n)]
for i in range(n):
    u, k, *v = map(int, input().split())
    for j in v:
        matrix[i][j-1] = 1
for line in matrix:
    line = list(map(str, line))
    print(' '.join(line))


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

#define INF (1e9+5)
using namespace std;
typedef long long ll;

ll mod = 998244353;
int a[100005];

int main() {
  int n;
  scanf("%d", &n);
  for (int i=0; i<n; i++) {
    int x;
    scanf("%d", &x);
    if ((i==0 && (x!=0)) || ((i!=0) && (x==0))) {
      printf("0\n");
      return 0;
    }
    a[x]++;
  }

  ll ans=1;
  for (int i=1; i<n+1; i++) {
    ll pls = 1;
    for (int j=0; j<a[i]; j++) {
      pls = (pls * a[i-1]) % mod;
    }
    ans = (ans * pls) % mod;
  }

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


Measured memory_bytes: 640
s=input()
n=len(s)
l=[0]*(n+1)
ans=0
c=1
ll=[]
for i in range(1,n):
    if s[i]==s[i-1]:
        c+=1
    else:
        ll.append((c,i,s[i-1]))
        c=1


for x,y,h in ll:
    if h=="<":
        l[y]=max(l[y],x)
    else:
        l[y-x]=max(l[y-x],x)


for i in range(n):
    if s[i]=="<":
        if l[i]>=l[i+1]:
            l[i+1]=l[i]+1

for i in range(n-1,-1,-1):
    if s[i]==">":
        if l[i]<=l[i+1]:
            l[i]=l[i+1]+1

print(sum(l))


Measured memory_bytes: 90056
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
 
using namespace std;
 
#define FOR(i,k,n) for(int i=(k); i<(int)n; ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
 
template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cout<<*i<<" "; cout<<endl; }
 
typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
struct order{
  string dealer, type, commodity;
  int price;
  order(string d, string t, string c, int p) :
    dealer(d), type(t), commodity(c), price(p) {}
};
 
order parse(){
  string d, t, c;
  int p;
  cin>>d>>t>>c>>p;
  return order(d, t, c, p);
}
 
int main(){
  int N;
  while(cin>>N && N){
    vector<order> orders;
    map<string, int> d_buy;
    map<string, int> d_sell;
    map<string, vector<int> > c_trade;
    REP(i, N){
      order od = parse();
      vector<order>::iterator tr_i = orders.end();
      d_buy[od.dealer] += 0;
      d_sell[od.dealer] += 0;
      if(od.type == "BUY"){
        FORIT(it, orders){
          if((it->type == "SELL" && it->commodity == od.commodity && it->price <= od.price && it->dealer != od.dealer)
              && (tr_i == orders.end() || tr_i->price > it->price)){
            tr_i = it;
          }
        }
        if(tr_i != orders.end()){
          int price = (od.price + tr_i->price) / 2;
          //printf("%s buy %s from %s by %d yen\n", od.dealer.c_str(), od.commodity.c_str(), tr_i->dealer.c_str(), price);
          d_buy[od.dealer] += price;
          d_sell[tr_i->dealer] += price;
          c_trade[od.commodity].push_back(price);
          orders.erase(tr_i);
        }else{
          orders.push_back(od);
        }
      }else{
        FORIT(it, orders){
          if((it->type == "BUY" && it->commodity == od.commodity && it->price >= od.price && it->dealer != od.dealer)
              && (tr_i == orders.end() || tr_i->price < it->price)){
            tr_i = it;
          }
        }
        if(tr_i != orders.end()){
          int price = (od.price + tr_i->price) / 2;
          //printf("%s sell %s to %s by %d yen\n", od.dealer.c_str(), od.commodity.c_str(), tr_i->dealer.c_str(), price);
          d_sell[od.dealer] += price;
          d_buy[tr_i->dealer] += price;
          c_trade[od.commodity].push_back(price);
          orders.erase(tr_i);
        }else{
          orders.push_back(od);
        }
      }
    }
    //cout<<"-"<<endl;
    FORIT(it, c_trade){
      string name = it->first;
      vector<int> v = it->second;
      sort(v.begin(), v.end());
      int a = v.front();
      int c = v.back();
      int b = 0;
      REP(i, v.size()) b += v[i];
      b /= v.size();
      printf("%s %d %d %d\n", name.c_str(), a, b, c);
    }
    cout<<"--"<<endl;
    FORIT(it, d_sell){
      string name = it->first;
      printf("%s %d %d\n", name.c_str(), d_buy[it->first], it->second);
    }
    cout<<"----------"<<endl;
  }
}


Measured memory_bytes: 3280
#include <bits/stdc++.h>
#include <string>
#include <algorithm>
#include <string.h>
#include <ctype.h>
#include <math.h>
#include <float.h>
#include <iomanip>
#include <iostream>
using namespace std;
 
int main(){

    string S, temp="ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ",ans="";
    int N;

    cin>>N>>S;

    for(int i=0;i<S.length();i++){

        for(int j=0;j<26;j++){
            if(S[i]==temp[j]){
                ans+=temp[j+N];
                break;
            }
        }
    }

    cout <<ans<<endl;
    
    return 0;

}

Measured memory_bytes: 256
n = int(input())

res = []
for i in range(n):
  city, value = input().split()
  value = int(value)
  res.append([city, value, i+1])
res_s = sorted(res, key = lambda x: (x[0], -x[1]))
for i in range(n):
  print(res_s[i][2])


Measured memory_bytes: 62732
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }

int main() {
	int N; int K;
	while (~scanf("%d%d", &N, &K)) {
		vector<int> a(N);
		for (int i = 0; i < N; ++i)
			scanf("%d", &a[i]);
		vector<ll> sum(N + 1), possum(N + 1);
		rep(i, N) {
			sum[i + 1] = sum[i] + a[i];
			possum[i + 1] = possum[i] + max(a[i], 0);
		}
		ll ans = 0;
		rer(i, 0, N - K) {
			amax(ans, possum[i] + (possum[N] - possum[i + K]));
			amax(ans, possum[i] + (sum[i + K] - sum[i]) + (possum[N] - possum[i + K]));
		}
		printf("%lld\n", ans);
	}
	return 0;
}


Measured memory_bytes: 2176
using System;
using static System.Console;
using static System.Math;
using System.Numerics;
using System.Collections.Generic;
using System.Linq;


public class Program
{
    public static void Main(string[] args)
    {
        bool end = false;
        long a = myRead.readLong();
        string ans = "";
        for (int i = -120; i < 120; i++)
        {
            long A = MyMath.Pow(i, 5);
            for (int j = -120; j < 120; j++)
            {
                long B = MyMath.Pow(j, 5);
                if (A - B == a)
                {
                    ans += i + " " + j;
                    end = true;
                    break;
                }
            }
            if (end == true)
                break;
        }
        WriteLine(ans);
        Out.Flush();
    }
}
public static class myRead
{
    public static int readInt() { return int.Parse(ReadLine()); }
    public static long readLong() { return long.Parse(ReadLine()); }
    public static string reatStr() { return ReadLine(); }
    public static int[] readIntArray() { return ReadLine().Split(' ').Select(int.Parse).ToArray(); }
    public static long[] readLongArray() { return ReadLine().Split(' ').Select(long.Parse).ToArray(); }
    public static string[] readStrArray() { return ReadLine().Split(' '); }
}


public static class MyMath
{
    public static long Factorical(long n)
    { return n <= 1 ? 1L : n * Factorical(n - 1); }
    public static long Permutation(long n, long m)
    { return m == 0 ? 1L : (m == n) ? Permutation(n, m - 1) : n * Permutation(n - 1, m - 1); }
    public static long Combination(long n, long m)
    { return n - m > m ? Permutation(n, m) / Factorical(m) : Permutation(n, n - m) / Factorical(n - m); }
    public static long Gcd(long n, long m)
    { return n % m == 0 ? m : Gcd(m, n % m); }
    public static long Lcm(long n, long m)
    { return n * m / Gcd(n, m); }
    public static long Pow(long n, long m)
    { return m == 0 ? 1L : m == 1 ? n : n * Pow(n, m - 1); }
}




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

int main(){
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    long long int ans1,ans2,ans3,ans4,ans;
    ans1=a;ans2=a;ans3=b;ans4=b;
    ans1*=c;
    ans2*=d;
    ans3*=c;
    ans4*=d;
    ans=ans1;
    if(ans2>ans)    ans=ans2;
    if(ans3>ans)    ans=ans3;
    if(ans4>ans)    ans=ans4;

    cout << ans << endl;
    return 0;



}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
      
int main() {
  int N, n1, n2, n3, n4;
  cin >> N;
      
  n1 = N / 1000;
  n2 = (N - n1 * 1000) / 100;
  n3 = (N - n1 * 1000 - n2 * 100) / 10;
  n4 = N - n1 * 1000 - n2 * 100 - n3 * 10;
     
  if (n1 == n2 && n2 == n3) {
  cout << "Yes" << endl;
  }
  
  else if (n2 == n3 && n3 == n4) {
    cout << "Yes" << endl;
  }
  
  else {
    cout << "No" << endl;
  }
  
}


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

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double dd;
#define clr(n, r) memset(n,r,sizeof(n))
#define endl "\n"
typedef bitset<11> MASK;
typedef pair<int, int> ii;
typedef vector<int> vii;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<vector<int>> vvi;
#define all(v) v.begin(),v.end()

int main() {
    std::ios_base::sync_with_stdio(false);
//        freopen("scratch.txt", "r", stdin);
    int n;cin>>n;
    if(n%1000)cout<<1000-(n%1000);
    else cout<<0
    ;
}

Measured memory_bytes: 3628
#include<stdio.h>
int main(){
  
  int stack[200],i=0,j=0,k=0,num[10],n=0,max=0,calStack;
   char c;
   
   for(i=0;i<200;i++){
     stack[i]=0;
   }
   i=0;
   while(1){
     
     c = getchar(); 
     
     if(c>='0' && c<='9'){
       num[i] = c - 48;
        i++;
	//  printf("%d\n",i);
     }
     else if(c == ' ' && i>0){
      
       if(i > 1){
	 
       for(j = 0; j < i-1; j++){
	 n = num[j]*10;
	 for(k=i-j-2;k > 0 ;k--){

	   n = n*10;
	   //  printf("%d\n",n);
	 }// printf("%d\n",n);
	 stack[max]+=n;
	 
       }
       }
       stack[max]+=num[i-1];
     
       // printf("%d\n",stack[max]);   
       i=0;
       max++;
     }
     else if (c == '+'){
       calStack = stack[max - 2] + stack[max - 1];
       stack[max-1]=0;
       stack[max-2]=calStack;
       max--;
     }
     
     else if (c == '-'){
       calStack = stack[max - 2] - stack[max - 1];
       stack[max-1]=0;
       stack[max-2]=calStack;
       max--;
     }
     
     else if (c == '*'){
       calStack = stack[max - 2] * stack[max - 1];
       stack[max-1]=0;
       stack[max-2]=calStack;
       max--;
    }
     else if(c=='\n'){
       break;
     }

   }
     printf("%d\n",stack[max-1]);
    
     
   return 0;
 
     
}

Measured memory_bytes: 524
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

const int MOD = 1e9 + 7;
const int iINF = 1000000000;
const long long int llINF = 1000000000000000000;

using namespace std;
using ll = long long int;
using P = pair<int, int>;
using edge = struct {
  int to;
  int cost;
};
#define REP(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define ALL(a) (a).begin(), (a).end()
#define MAX(vec) *std::max_element(vec.begin(), vec.end());
#define MIN(vec) *std::min_element(vec.begin(), vec.end());
#define MAXI(vec)                                                              \
  std::distance(vec.begin(), *std::max_element(vec.begin(), vec.end()));
#define MINI(vec)                                                              \
  std::distance(vec.begin(), *std::min_element(vec.begin(), vec.end()));
#define BIT(n, num) std::bitset<(n)>((num)).to_string()

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

template <typename T, typename U> U read(ll V, T a, U b) {
  REP(i, V) {
    cin >> a;
    b.push_back(a);
  }
  return b;
}

int main() {
  ll N, M, C = 0;
  vector<ll> A;
  A.push_back(0);
  cin >> N >> M;
  map<ll, ll> B;
  B.insert(make_pair(0, 0));
  B[0]++;
  REP(i, N) {
    ll po;
    cin >> po;
    A.push_back((A.back() + po) % M);
    if (B.count(A.back()) == 0)
      B.insert(make_pair(A.back(), 0));
    B[A.back()]++;
  }
  for (auto b : B) {
    C += b.second * (b.second - 1) / 2;
  }
  cout << C << endl;

  return 0;
}


Measured memory_bytes: 5240
#include <bits/stdc++.h>
using namespace std;
#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

const i64 INFT = 1LL << 60LL;

int N;
i64 H[5050], P[5050];

i64 dp[5050][5050];

void chmin(i64& a, i64 b) { a = min(a, b); }

int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) scanf("%lld%lld", H + i, P + i);

	vector<pair<i64, pair<i64, i64> > > ppl;
	for (int i = 0; i < N; ++i) ppl.push_back({ H[i] + P[i], {H[i], P[i]} });
	sort(ppl.begin(), ppl.end());

	for (int i = 0; i < N; ++i) {
		H[i] = ppl[i].second.first;
		P[i] = ppl[i].second.second;
	}

	for (int i = 0; i <= N; ++i) {
		for (int j = 0; j <= N; ++j) dp[i][j] = INFT;
	}
	dp[0][0] = 0;

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j <= i; ++j) {
			chmin(dp[i + 1][j], dp[i][j]);
			if (dp[i][j] <= H[i]) chmin(dp[i + 1][j + 1], dp[i][j] + P[i]);
		}
	}

	for (int i = N; i >= 0; --i) {
		if (dp[N][i] < (1LL << 40LL)) {
			printf("%d\n", i);
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 199232
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using P = pair<ll,ll>;
const ll mod = 1e9+7;
#define ALL(x) (x).begin(),(x).end()
#define pow(x,y) modpow(x,y)
#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define REPS(i,n) for(ll (i)=1;(i)<=(n);(i)++)
#define RREP(i,n) for(ll (i)=(n-1);(i)>=0;(i)--)
#define RREPS(i,n) for(ll (i)=(n);(i)>0;(i)--)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());

template<class T> inline void chmin(T& a, T b){
    if (a > b){
        a = b;
    }
}

template<class T> inline void chmax(T& a, T b){
    if (a < b){
        a = b;
    }
}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(10);
    ll N;
    cin >> N;
    vector<ll> A(N);
    vector<ll> B(N);
    REP(i,N){
        cin >> A[i];
        B[i] = -A[i]+i;
    }
    sort(ALL(B));
    ll count = 0;
    REP(i,N){
        count+=upper_bound(ALL(B),A[i]+i) - lower_bound(ALL(B),A[i]+i);
    }
    cout << count << "\n";
}


Measured memory_bytes: 6364
#include <bits/stdc++.h>  // ver1.9.4
#define int long long
#define ALL(v) (v).begin(),(v).end()
#define Vi vector<int>
#define pb push_back
#define mp make_pair
#define cYES cout<<"YES"<<endl
#define cNO cout<<"NO"<<endl
#define cYes cout<<"Yes"<<endl
#define cNo cout<<"No"<<endl
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repeq(i,a,b) for(int i=a;i<=b;i++)
#define repr(i,a,b) for(int i=a;i>b;i--)
#define repreq(i,a,b) for(int i=a;i>=b;i--)
#define leng(n) (int)(log10(n)+1)
#define Vout(a) rep(i,0,a.size()-1)cout<<a[i]<<' ';cout<<a[a.size()-1]<<endl;
#define INF 9000000000000000000  //  9.0 * 10^18
#define MOD 1000000007  //  10^9 + 7
using namespace std;

signed main() {
  cout << fixed << setprecision(15);
  int n;
  cin >> n;
  n *= 2;
  Vi a(n);
  rep(i,0,n) cin >> a[i];
  int ans=0;
  sort(ALL(a));
  rep(i,0,n){
    if(i%2==0) ans += a[i];
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int n;
  cin>>n;
  int r[n];
  for(int i=0;i<n;i++) cin>>r[i];
  int ans=r[1]-r[0],tmp=r[0];
  for(int i=1;i<n;i++){
    ans=max(ans,r[i]-tmp);
    tmp=min(tmp,r[i]);
  }
  cout<<ans<<endl;
  return 0;
}

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

const char wall = '#';
vector<vector<char>> fields;
vector<vector<bool>> used;
vector<vector<ll>> dist;
const int dx[4] = {0, -1, 0, 1};
const int dy[4] = {1, 0, -1, 0};

vector<ll> A;
// vectorのリサイズ
// A.resize(N);

ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return b/gcd(a,b)*b;}

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

  ll a, b, k;
  cin >> a >> b >> k;
  if (k-a > 0){
    cout << 0 << " " << max(ll(0), b - (k-a)) << endl;
  } else {
    cout << a-k << " " << b << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(){
  int a,b,c,k;
  scanf("%d%d%d%d",&a,&b,&c,&k);
  
  int ans = 0;
  
  if(k <= a){
    // 1 だけをつかえたら全部 1
    ans = k;
    k = 0;
  }else{ 
    //他のも使わないといけない
    //とりあえず使えるだけ 1 を使う
    ans = a;
    k -= a;
  }
  
  //のこりはとりあえず使えるだけ 0 を使ったことにする
  k -= b;
  
  //まだ使わないといけなかったら
  if(k>0){
    //仕方ないので -1 を使う
    ans -= k;
  }
  
  printf("%d\n",ans);
}


Measured memory_bytes: 1696
#include<iostream>
using namespace std;
int n,a[2000];
bool solve(int i,int m)
{
    if(m==0) return true;
    if(i>=n) return false;
    int res=solve(i+1,m)||solve(i+1,m-a[i]);
    return res;
}
int main()
{
    int q,m,i;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>a[i];
    }
    cin>>q;
    for(i=0;i<q;i++)
    {
        cin>>m;
        if(solve(0,m))
        cout<<"yes"<<endl;
        else
        cout<<"no"<<endl; 
    }
    return 0;
}



Measured memory_bytes: 3120
s=input()
n=int(input())
if len(s)==1:print(n//2);exit()
if len(set(s))==1:print(len(s)*n//2);exit()
c=1
l=[]
for x in range(1,len(s)):
    if s[x-1]==s[x]:
        c+=1
        if x==len(s)-1:l.append(c)
    else:l.append(c);c=1

t=0
if s[0]==s[-1] and l[0]%2==1 and l[-1]%2==1:t=n-1
print(sum([i//2 for i in l])*n+t)

Measured memory_bytes: 9156
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <numeric>
#include <iterator>

using namespace std;

typedef unsigned int UI;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int,int> PII;
typedef istringstream ISS;
typedef ostringstream OSS;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )

#define EACH( it, c ) for ( auto it = c.begin(); it != c.end(); ++it )
#define ALL( c ) (c).begin(), (c).end()

#define PB( n ) push_back( n )
#define MP( a, b ) make_pair( ( a ), ( b ) )
#define EXIST( c, e ) ( (c).find( e ) != (c).end() )

#define fst first
#define snd second

#define DUMP( x ) cerr << #x << " = " << ( x ) << endl
#define DEBUG( x ) cerr << __FILE__ << ":" << __LINE__ << ": " << #x << " = " << ( x ) << endl

bool check( const VI &as, int m, int width )
{
	int sum = 0, res = 1;
	REP( i, 0, as.size() )
	{
		if ( width < as[i] )
		{
			return false;
		}

		if ( sum + as[i] <= width )
		{
			sum += as[i];
		}
		else
		{
			sum = as[i];
			res++;
		}
	}

	return res <= m;
}

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

	while ( true )
	{
		int m, n;
		cin >> m >> n;

		if ( !( m | n ) )
		{
			break;
		}

		VI as( n );
		FOR( a, as )
		{
			cin >> a;
		}

		int lb = 1, ub = 1500000;
		while ( lb + 1 < ub )
		{
			int mid = ( lb + ub ) / 2;

			if ( check( as, m, mid ) )
			{
				ub = mid;
			}
			else
			{
				lb = mid;
			}
		}

		cout << ub << endl;
	}	

	return 0;

}

Measured memory_bytes: 1196
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int number_n, number_m, i, j = 0;
    number_n = Integer.parseInt(sc.next());
    number_m = Integer.parseInt(sc.next());
    int[] stage = new int[number_n+1];
    int[] broken_stage = new int[number_m+1];
    broken_stage[0] = 0;
    for(i = 0; i < number_m; i++) {
      broken_stage[i] = Integer.parseInt(sc.next());
    }
    stage[0] = 1;
    stage[1] = (broken_stage[0] == 1)? 0 : 1;
    for(i = 2; i <= number_n; i++) {
      stage[i] = (stage[i-1] + stage[i-2]);
      for(; j < number_m; j++) {
        if(broken_stage[j] < i) {
          continue;
        } else if(broken_stage[j] > i) {
          break;
        } else {
          stage[i] = 0;
          break;
        }
      }
      if(stage[i] > 1000000007) stage[i] -= 1000000007;
    }
    System.out.println(stage[number_n]);
  }
}


Measured memory_bytes: 46260
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (long long i = 0; i < (long long) (n); ++i)
#define pb emplace_back
#define endl '\n'

template<typename T> void _dbg(const char*_s,T _h) { cerr<<_s<<" = "<<_h<<"\n"; }

template<typename T, typename... Ts> void _dbg(const char*_s,T _h,Ts... _t) {
    for(int _b=0;((_b+=*_s=='(')-=*_s==')')!=0||*_s!=',';)cerr<<*_s++;
    cerr<<" = "<<_h<<",";_dbg(_s+1,_t...);
}

#define int long long

#ifdef LOCAL
    #define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
    #define dbg(...)
#endif

const int N = 500 * 1000 + 17;
const int MOD = 1000 * 1000 * 1000 + 7;

string s;

bool read() {
    if (!(cin >> s))
        return false;

    return true;
}

void solve(int id = 0) {
    if (count(s.begin(), s.end(), '7')) 
        cout << "Yes\n";
    else
        cout << "No\n";
}

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

    int T;
    T = 1;

    while (read())
        solve(T++);

    return 0;
}



Measured memory_bytes: 3656
#include<bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define M (L+R)/2
#define N 500009
#define inf 99999999999
#define ll long long
#define mod 1000000007
using namespace std;
ll H,ans,sum;
void go(ll x,ll p){
	if(x==0)return;
	ans+=p;
	go(x/2,p*2);
}
int main(){

	ios::sync_with_stdio(0);
	
	cin>>H;
	go(H,1);
	cout<<ans<<endl;
	return 0;
}



Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
	let c: String = read();
    println!("{}", (c.chars().next().unwrap() as u8 + 1) as char);
}

Measured memory_bytes: 4352
from decimal import *

N,K = map(int,input().split())

A = list(map(int,input().split()))
visit = [0]*N
fi = [1]
st = 0
visit[0] = 1
p = A[0]
for i in range(N):
  fi.append(p)
  if visit[p-1] == 0:
    visit[p-1] = i+2
    p = A[p-1]
  else:
    
    st = i
    break
    
loop = []
loop.append(p)
q = p
while 1:
  if q == A[p-1]:
    break
  loop.append(A[p-1])
  p = A[p-1]
st-=len(loop)
fi = fi[:len(fi)-len(loop)-1]
if K - st> 0:
  k = (K - st) % len(loop)
  print(loop[k-1])
else:
  print(fi[K])

Measured memory_bytes: 34176
#[allow(unused_macros)]
macro_rules! input {
    ( $($t:ty),* ) => {{
        let mut s = String::new();
        std::io::stdin().read_line(&mut s);
        let mut splits = s.trim().split_whitespace();
        ($( { splits.next().unwrap().parse::<$t>().unwrap() },)*)
    }}
}


#[allow(unused_macros)]
macro_rules! invec {
    ( $ t : ty ) => {{
        let mut s = String::new();
        match std::io::stdin().read_line(&mut s) {
            Ok(0) => Vec::<$t>::new(),
            Ok(n) => s
                .trim()
                .split_whitespace()
                .map(|s| s.parse::<$t>().unwrap())
                .collect::<Vec<$t>>(),
            Err(_) => Vec::<$t>::new(),
        }
    }};
}

#[allow(unused_must_use)]
#[allow(unused_variables)]
fn solve() {
    let (n,) = input!(usize);
    let a = invec!(u32);

    let mut count = 0;
    for i in 0..n {
        if a[i] != (i + 1) as u32 {
            count += 1;
        }
    }

    if count == 0 || count == 2 {
        println!("YES");
    } else {
        println!("NO");
    }
}

fn main() {
    solve();
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
#define endl "\n"
#define pii pair<int,int> 
#define ff first
#define ss second
#define mii map<int,int>
#define si set<int>
#define sti stack<int>
#define qi queue<int>
#define vi vector<int>
#define pq priority_queue<int>
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const int M=1e9+7;
const int inf=1e18;

int32_t main(){
	IOS;
	int n; cin>>n;
	map<string,int> m;
	int tot=0;
	for(int i=0;i<n;i++){
		string s;int t;
		cin>>s>>t;
		tot+=t;
		m[s]=tot;
	}
	string x;
	cin>>x;
	cout<<tot-m[x]<<endl;
} 

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

using namespace std;
const int N=1e5+5;
vector<int>adj[N];
int dp[N];
bool vis[N];
int dfs(int u){
    vis[u]=true;
    if(adj[u].size()==0){
        return 0;
    }
    for(int i=0;i<adj[u].size();i++){
            int v=adj[u][i];
        if(!vis[v]){
          dp[u]=max(dfs(v)+1,dp[u]);
        }
        else{
          dp[u]=max(dp[v]+1,dp[u]);
        }
    }
    return dp[u];
}
int main()
{
    int n,m;

    cin>>n>>m;

    for(int i=1;i<=m;i++){
      int u,v;
      cin>>u>>v;
      adj[u].push_back(v);
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            dfs(i);
        }
       // cout<<dp[i]<<endl;
    }
    int res=0;
    for(int i=1;i<=n;i++){
        res=max(res,dp[i]);
    }
    //res+=1;
    cout<<res<<endl;
    return 0;
}



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

long long powint(long long x,long long t){
  long long res=1;
  for (int i = 0; i < t; i++) {
    res*=x;
  }
  if(t==0)res=1;
  return res;
}

int main() {
  long long a,b,res=0;
  long long ai,bi;
  cin >> a >> b;
  for(long long i=1;i<42;i++){
    ai=(a%powint(2,i+1))/powint(2,i);
    bi=(b%powint(2,i+1))/powint(2,i);
    if(ai==1 && a%2==0)ai=0;
    if(bi==1 && b%2!=0)bi=0;
    if(ai!=bi)res+=powint(2,i);
  }
  res+=((b+1)/2-a/2)%2;
  cout << res << endl;
}



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

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

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

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

  int a;
  int mn = -1;
  rep(i, N) {
    cin >> a;

    int c = 0;
    while(a % 2 == 0) {
      a /= 2;
      c++;
    }

    if (mn == -1 || mn > c) mn = c;
  }

  cout << mn << endl;

  return 0;
}


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

int main() {
    string s,t;
    cin>>s>>t;
    if(s==t.substr(0,t.size()-1)){
        cout << "Yes" <<endl;
    }else{
        cout << "No" <<endl;
    }
}

Measured memory_bytes: 3632