akhauriyash/Code-Regression huggingface dataset:
import array
import collections


Edge = collections.namedtuple("Edge", "start end weight")


class UnionFind(object):

    def __init__(self, number_of_nodes):  # 初期化
        self.par = array.array("L", range(number_of_nodes))
        self.rank = array.array("L", (0 for i in range(number_of_nodes)))

    def root(self, node):  # 根を求める
        if self.par[node] == node:
            return node
        else:
            r = self.root(self.par[node])
            self.par[node] = r  # 経路圧縮
            return r

    def in_the_same_set(self, node1, node2):  # 同じ集合に属するか
        return self.root(node1) == self.root(node2)

    def unite(self, node1, node2):  # 属する集合を併合
        x = self.root(node1)
        y = self.root(node2)
        if x == y:
            pass
        elif self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


# Kruskal法により最小全域木を求める
def compute_mst_kruskal(max_v, edges):
    edges.sort(key=lambda edge: edge.weight)
    uf = UnionFind(max_v)
    mst = []
    for edge in edges:
        if not uf.in_the_same_set(edge.start, edge.end):
            uf.unite(edge.start, edge.end)
            mst.append(edge)
    return mst


def main():
    n = int(input())
    XY = [list(map(int, input().split())) + [i] for i in range(n)]
    XY.sort()
    edges = []
    for (x1, y1, i1), (x2, y2, i2) in zip(XY, XY[1:]):
        edges.append(Edge(i1, i2, min(abs(x1 - x2), abs(y1 - y2))))
    XY.sort(key=lambda x:x[1] )
    for (x1, y1, i1), (x2, y2, i2) in zip(XY, XY[1:]):
        edges.append(Edge(i1, i2, min(abs(x1 - x2), abs(y1 - y2))))
    
    mst = compute_mst_kruskal(n, edges)
    print(sum(edge.weight for edge in mst))


if __name__ == '__main__':
    main()
    



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

using namespace std;

int main()
{
    vector<int> L = { 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51 };
    int K;

    cin >> K;

    cout << L[K-1] << endl;
}
  

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

class Main {

	private static class Edge {
		public int to, id;

		public Edge(int to, int id) {
			this.to = to;
			this.id = id;
		}
	}

	private static List<Edge>[] G;

	private static List<Integer> dfs(int v, int t, int p) {
		if (v == t) return new ArrayList<>();
		for (Edge e : G[v]) {
			if (e.to == p) continue;
			List<Integer> a = dfs(e.to, t, v);
			if (a != null) {
				a.add(e.id);
				return a;
			}
		}
		return null;
	}

	public static void main(String[] args) throws Exception {
		final Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		G = new ArrayList[N];
		for (int i = 0; i < N; i++) {
			G[i] = new ArrayList<>();
		}

		for (int i = 0; i < N - 1; i++) {
			int a = sc.nextInt() - 1;
			int b = sc.nextInt() - 1;
			G[a].add(new Edge(b, i));
			G[b].add(new Edge(a, i));
		}

		int M = sc.nextInt();
		long[] s = new long[M];
		for (int i = 0; i < M; i++) {
			int a = sc.nextInt() - 1;
			int b = sc.nextInt() - 1;
			List<Integer> ids = dfs(a, b, -1);
			assert ids != null;
			for (Integer id : ids) {
				s[i] |= 1L << id;
			}
		}

		long answer = 0;
		for (int i = 0; i < 1 << M; i++) {
			long mask = 0;
			for (int j = 0; j < M; j++) {
				if (((i >> j) & 1) == 1) {
					mask |= s[j];
				}

				int white = Long.bitCount(mask);
				long x = 1L << (N - 1 - white);
				if (Long.bitCount(i) % 2 == 0) {
					answer += x;
				} else {
					answer -= x;
				}
			}
		}

		System.out.println(answer);
	}
}


Measured memory_bytes: 25300
// agrawal117
// segment tree

#include<bits/stdc++.h>
#define mod 1000000007
#define endl '\n'
typedef long long int ll ;
using namespace std;
#define  MAX 200005
ll arr[MAX];
ll tree[4*MAX];
ll temp[MAX];
ll N=MAX-2;
ll combine(ll a,ll b)					// 1 based indexing remember;
{
	return max(a,b);
}

ll query(ll start,ll end,ll node,ll l,ll r)
{
	if(start>r || l>end) {				//no overlap case  return that value which does not affect the ans 
		return 0;							// as in case of sum we can return 0;
	}
	else if(l<=start && r>=end) {
		return tree[node];           // case of fully overlap
	}
	else{
		ll mid=(start+end)>>1;								//partial overlap so call both children
		ll child1=query(start,mid,2*node,l,r);
		ll child2=query(mid+1,end,(2*node)+1,l,r);
		return combine(child1,child2);
	}
}

void update(ll start,ll end,ll node,ll idx,ll value)
{
	 if(start==end){
		tree[node]=value;
		return;
	}
	ll mid=(start+end)>>1;	
	if(start<=idx && idx<=mid){
	 update(start,mid,2*node,idx,value);
	}
	 else{
		update(mid+1,end,(2*node)+1,idx,value);
	 }
	tree[node]=combine(tree[2*node],tree[(2*node)+1]);
}
ll ans_mp[MAX];
vector<ll> v[MAX];
vector<ll> fck[MAX];
ll dp[MAX];
void dfs(int node,int par)
{
    ll val=query(1,N,1,1,arr[node]-1);
    ll x=max(1LL,val+1);
    update(1,N,1,arr[node],x);
    fck[arr[node]].push_back(x);
    ans_mp[node]=max(x,ans_mp[par]);
    for(auto i: v[node])
    {
        if(i^ par) dfs(i,node);
    }
    fck[arr[node]].pop_back();
    update(1,N,1,arr[node],fck[arr[node]].back());
}
int main()
{
	ll n;
	cin>>n;
	map<ll,ll> mp;
	for(ll i=1;i<=n;i++)  { cin>>temp[i]; mp[temp[i]]++; }
	ll cnt=1; 
	for(auto  & i: mp)
	{
	    i.second=cnt++;
	}
	for(int i=1;i<=n;i++) arr[i]=mp[temp[i]];
	for(int i=1;i<=N;i++) fck[i].push_back(0);
	for(int i=1;i<=n-1;i++){
	    ll a, b ; cin>>a>>b;
	    v[a].push_back(b);
	    v[b].push_back(a);
	}
	dfs(1,1);
	for(int i=1;i<=n;i++) cout<<ans_mp[i]<<endl;
	
}














Measured memory_bytes: 56308
#include <bits/stdc++.h>
#define FI first
#define SE second
#define PB push_back
#define ll long long
#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 YES(i) cout<<(i?"YES":"NO")<<endl
#define Yes(i) cout<<(i?"Yes":"No")<<endl
#define co(i) cout<<(i)<<endl
#define fcout cout<<fixed<<setprecision(10)
#define uni(i) i.erase(unique(i.begin(), i.end()), i.end());
#define all(i) i.begin(),i.end()
#define pint pair<int, int>
#define vint vector<int>
using namespace std;

const int INF=1e9+7;
const int MOD=1e9+7;
//const int MOD=998244353;
int a[100000][3], dp[100000][3];

int main(){
	int n; cin>>n;
	FOR(i,0,n){
		cin>>a[i][0]>>a[i][1]>>a[i][2];
	}
	FOR(i,0,n){
		if(i==0) FOR(j,0,3) dp[i][j]=a[i][j];
		else{
			FOR(j,0,3){
				int M=-INF;
				FOR(k,0,3){
					if(j!=k) M=max(M,dp[i-1][k]+a[i][j]);
				}
				dp[i][j]=M;
			}
		}
	}
	int M=-INF;
	FOR(i,0,3) M=max(M,dp[n-1][i]);
	co(M);
}


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

  for (int i = 0; i < N; i++) {
    int l, r;
    cin >> l >> r;
    
    SUM += r - l + 1;
  }
  cout << SUM << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <algorithm>       // for next_permutation
#include <vector>
#include <queue>
#include <bits/stl_numeric.h>

#define DEBUG 0
#define REP(i, n) for (long long i = 0; i < (n); i++) 
using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
static const ll MOD = 1000000007;
static const ll INF = 1000000000000000000LL;

unsigned gcd(unsigned a, unsigned b) {
  if(a < b) return gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

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

int main() {

    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, M;
    cin >> N >> M;

    vector <ll> a(N);
    ll amax = 0;

    REP(i, N)
    {
        cin >> a[i];
        amax = max(amax, a[i]);
    }
    ll wa = a[0];
    int wa2 = 0;



    for(int i = 1; i < N; ++i)
    {
        wa = lcm(wa, a[i]);
        if(wa >= MOD * 2)
        {
            cout << 0 << endl;
            return 0;
        }


    }

    //lcmの2が複数含まれてたらおわり
    //それぞれの2の個数が一致していないといけない
    int cnt1 = 0;
    while(a[0] % 2 == 0)
    {
        ++cnt1;
        a[0] /= 2;
    }
    for(int i = 1; i < N; ++i)
    {
        int cnt2 = 0;
        while(a[i] % 2 == 0)
        {
            ++cnt2;
            a[i] /= 2;
        }

        if(cnt1 != cnt2)
        {
            cout << 0 << endl;
            return 0;
        }
    }

    ll res;

    M += (wa / 2);
    res = M / wa;

    cout << res << endl;

    return 0;
}
 


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#define rep(i, n) for(i = 0; i < n; i++)
#define int long long
using namespace std;

int n;
int a[200000];
vector<int> et[200000];

int INF = 1e+10;
int dp[200001];	//dp[length] = min_value
int ans[200001];
void dfs(int p, int v, int len) {
	int pos = lower_bound(dp, dp + len, a[v]) - dp;
	int tmp = dp[pos];
	int nlen = len;
	if (pos == len) { nlen = len + 1; }
	dp[pos] = a[v];
	
	ans[v] = nlen;
	int i;
	rep(i, et[v].size()) {
		int nv = et[v][i];
		if (nv == p) continue;
		dfs(v, nv, nlen);
	}
	dp[pos] = tmp;
}

signed main() {
	int i;
	
	cin >> n;
	rep(i, n) cin >> a[i];
	rep(i, n - 1) {
		int u, v;
		cin >> u >> v;
		u--; v--;
		et[u].push_back(v);
		et[v].push_back(u);
	}
	
	rep(i, n + 1) dp[i] = INF;
	dfs(-1, 0, 0);
	rep(i, n) cout << ans[i]  << endl;
	return 0;
}


Measured memory_bytes: 33596
#include"bits/stdc++.h"
#include<cassert>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
const long long inf = 1ll << 62;
typedef pair<int, int> P;
typedef pair<P, int> PP;
int b[100006], l[100006], u[100006];

int dif(int n, int x) {
	return max((x - b[n])*l[n], (x - b[n])*u[n]);
}

signed main() {
	int n, x; cin >> n >> x;
	rep(i, n) {
		cin >> b[i] >> l[i] >> u[i];
	}
	int alt = -1, aut = n*x + 1;

	while (aut - alt > 1) {
		int mi = (aut + alt) / 2;
		int score = 0;
		int maxscore;
		vector<P>R;
		rep(i, n) {
			R.push_back(P((x - b[i])*u[i] + l[i] * b[i], i));
			score -= l[i] * b[i];
		}
		sort(R.begin(), R.end());
		reverse(R.begin(), R.end());
		rep(i, mi / x) {
			P p = R[i];
			score += p.first;
		}
		maxscore = score;
		int m = mi%x;
		for (int i = mi / x; i < n; i++) {
			int now = R[i].second;
			int ms = dif(now,m) + l[now] * b[now];
			maxscore = max(maxscore, score + ms);
		}
		if (mi != n*x) {
			score += R[mi / x].first;
			rep(i, mi / x) {
				int ns = score - R[i].first;
				int now = R[i].second;
				int ms = dif(now,m) + l[now] * b[now];
				maxscore = max(maxscore, ns + ms);
			}
		}
		if (maxscore  >= 0)aut = mi;
		else alt = mi;
	}
	cout << aut << endl;
}


Measured memory_bytes: 6788
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll n,k,i,j,r,a,f,l;
    vector<ll>v,v1;
    cin>>n>>k;
    for(i=0;i<n;i++)
    {
        cin>>a;
        v.push_back(a);
    }
    f=0;
    l=k;
    for(i=0;i<n-k;i++)
    {
        if(v[f]<v[l])
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
        f++,l++;
    }
}


Measured memory_bytes: 5300
import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);


    public static void main(String[] args) {
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int d = sc.nextInt();
        int i = 0;
        while (a > 0 && c > 0) {
            if (i % 2 == 0) {
                c -= b;
            } else {
                a -= d;
            }
            i++;
        }
        if (a > 0) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }

    }
}


Measured memory_bytes: 27080
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<utility>
#include<string>
#include<stack>
#include<queue>
#include<set>
#include<math.h>
#include <map>
using namespace std;
typedef long long int ll;
#define repi(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,a) repi(i,0,a)
#define all(u) u.begin(),u.end()
#define pl pair<ll,ll>
#define fi first
#define se second
#define inf 1000000007

ll N,M;
vector <pl> city;
vector<ll> Data[100010];

ll keta(ll n){
    ll res = 0;
    while(n / 10 != 0){
        res++;
        n /= 10;
    }
    return res;
}

int main() {
    scanf("%lld%lld",&N,&M);
    rep(i,M){
        ll P,Y; scanf("%lld%lld",&P,&Y);
        pl temp; temp.fi = P; temp.se = Y;
        city.push_back(temp);
        Data[P].push_back(Y);
    }
    rep(i,100010){
        if (Data[i].size() != 0){
            sort(Data[i].begin(),Data[i].end());
        }
    }
    rep(i,M){
        ll x;
        ll f = city[i].fi;
        ll s = city[i].se;
        x = lower_bound(Data[f]. begin(),Data[f].end(),s)-Data[f].begin()+1;
        string str;
        string strr;
        ll k = keta(f);
        ll K = keta(x);
        rep(j,6-k-1) str += "0";
        rep(j,6-K-1) strr += "0";
        cout << str << city[i].fi << strr << x << endl;
        
    }
    return 0;
}


Measured memory_bytes: 8560
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <deque>
#include <iomanip>
#include <cstdio>
#include <stack>
#include <numeric>

using namespace std;
typedef  long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define  MP make_pair
#define  PB push_back
#define inf  1000000007
#define rep(i,n) for(int i=0;i<(int)(n);++i)
//size有り
class UnionFind {
private:
    int sz;
    vector<int> par, size_;
public:
    UnionFind(){}
    UnionFind(int node_size) : sz(node_size), par(sz), size_(sz, 1){
        iota(par.begin(), par.end(), 0);
    }
    int find(int x){
        if(par[x] == x) return x;
        else return par[x] = find(par[x]);
    }
    void unite(int x,int y){
        x = find(x), y = find(y);
        if(x == y) return;
        if(size_[x] < size_[y]) swap(x,y);
        par[y] = x;
        size_[x] += size_[y];
    }
    int size(int x){
        x = find(x);
        return size_[x];
    }
    bool same(int x,int y){
        return find(x) == find(y);
    }
};

int main(){
    int n;
    cin >> n;
    UnionFind uf(n+1),uf2(n+1);
    int k,l;
    cin >> k >> l;
    rep(tt,k){
        int a,b;
        cin >> a >> b;
        uf.unite(a,b);
    }
    rep(tt,l){
        int a,b;
        cin >> a >> b;
        uf2.unite(a,b);
    }
    map<ll,int> mp;
    rep(i,n){
        mp[(ll)uf.find(i+1)*((ll)uf2.find(i+1)+inf)]++;
    }
    rep(i,n){
        cout << mp[(ll)uf.find(i+1)*((ll)uf2.find(i+1)+inf)] << " ";
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 15104
#include <bits/stdc++.h>
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; }
#define all(x) (x).begin(),(x).end()
#define pll pair<ll,ll>
#define pii pair<int,int>
#define rep(i,n) for(int i=0;i<n;i++)
#define For(i,a,b) for(int i=a;i<b;i++)
#define sz(x) ((ll)(x).size())
#define pb push_back
#define mp make_pair
#define bit(n) (1LL<<(n))
#define F first
#define S second
#define debug(x) cerr << x << endl
#define Complex complex<double>
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const ll INF = 1LL<<60;
const ll mod = (int)1e9 + 7;

/*
テストケース全てに目を通す
テストケースが2個以下だったらなんかある
N最小のコーナーケースがないか調べる
制約をしっかりと確認する（1からNまでの順列、全て異なる値などの制約も含め）
制約のn*mとn,mを読み違えない
操作の逆順を考える
オーバーフローしないか確かめる
Codeforcesではscanfを使う
modの引き算には+modをする
エラー出力は消す
エラー出力を消せ！！！！！
数値の区切り位置を誤読しない
木はn-1ノード
関数単位で調べる
cout << fixed;
cout << setprecision(n) << ans;
 */

int main() {
    string s;
    cin >> s;
    if(s[2]==s[3] && s[4]==s[5])cout << "Yes";
    else cout << "No";



    
}

/*
*/



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
    string s;
    cin >> s;
    string key = "keyence";
    int n = s.size();
    for (int i = 0; i <= n - 7; i++) {
        if (i == 0) {
            if (s == key) {
                cout << "YES" << endl;
                return 0;
            }
            continue;
        }
        for (int j = 0; j <= n - i; j++) {
            string t;
            int rem = i;
            bool flag = true;
            for (int k = 0; k < n; k++) {
                if (!flag) rem--;
                if (k == j) {
                    rem--;
                    flag = false;
                }
                if (flag) t += s[k];
                if (rem == 0) {
                    flag = true;
                }
            }
            if (t == key) {
                cout << "YES" << endl;
                return 0;
            }
        }
    }
    cout << "NO" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
using namespace std;
int main(void){
    int x = 0;
    cin >> x;
    x = x / 100;
    char S[106];
    S[0] = 'a';
    S[1] = 'i';
    S[2] = '1';
    S[3] = '3';
    S[4] = '3';
    S[5] = '3';
    for(int i = 0; i < x; i++){
        S[i + 6] = '3';
    }
    for(int i = 0; i < x+6; i++){
        printf("%c", S[i]);
    }
    putchar('\n');
    return 0;
}



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

#define rep(i,b) for(long long i = 0; i < (b); i++)
#define all(a) a.begin(),a.end()
#define allr(a) a.rbegin(),a.rend()
using ll = long long;

ll lcm(ll a,ll b){
	
	return (a*b)/(__gcd(a,b));
}


void solve() 
{ 
int n,k;
cin>>n>>k;
vector<int> v(n);
rep(i,n){
	cin>>v[i];
}
sort(all(v));
if(k>=n){
	cout<<0;
	return ;
}
ll sum=0;
for(int i=0;i<n-k;i++){
	sum=sum+v[i];
}
cout<<sum;
}
int main(){


		solve();
		cout<<endl;
		


	
					
}
		

	

		

 



Measured memory_bytes: 4048
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
#define INF 1145141919810893364
//#define INF 810114514
#define PI 3.141592653589
typedef long long ll;
typedef pair<ll,ll> PP;
#define int ll
#define setdouble setprecision
#define REP(i,n) for(int i=0;i<(n);++i)
#define OREP(i,n) for(int i=1;i<=(n);++i)
#define RREP(i,n) for(int i=(n)-1;i>=0;--i)
#define GOODBYE do { cout << "0" << endl; return 0; } while (false)
#define MM <<" "<<
#define Endl endl
#define debug false
#define debug2 false

signed main(void){
    int N,K;
    int d,a;
    int snuke[104]={};
    int Ans=0;
    
    cin >> N >> K;
    REP(i,K){
        cin >> d;
        REP(j,d){
            cin >> a;
            a--;
            snuke[a]++;
        }
    }
    
    REP(i,N){
        if(snuke[i]==0)Ans++;
        //cout << snuke[i] << " ";
    }
    cout << Ans << endl;
    
    return 0;
}




Measured memory_bytes: 3616
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
#include <tuple>
//#include <bits/stdc++.h>
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define FOR(i,i0,n) for(int (i)=(i0);(i)<(n);(i)++)
#define FORR(i,i0,n) for(int (i)=(n)-1; (i)>=(i0);(i)--)
#define SORT(x) sort(x.begin(),x.end())
#define rn return
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
typedef std::pair<int,int> P;
using namespace std;
using ll = long long;




int main(){
    
    int h,w,k;
    cin >> h >> w >> k;
    vector<vector<int>> choco(h,vector<int>(w,0));
    rep(i,h){
        string s;
        cin >> s;
        rep(j,w){
        if (s[j]=='1')  choco[i][j] = 1;
        }
    }
    int ans = (int)1e8;
    for(int i = 0; i < (1<<(h-1));i++){
        
        
        
        vector<int> rowcut;
        rowcut.pb(0);
        for(int j = 0; j < h-1; j++){
            int cut = (((1<<j)&i) > 0);
            if (cut) rowcut.push_back(j+1);
        }
        rowcut.pb(h);
        
        int cuts = (int) rowcut.size();
        int cand = 0;
        
//        rep(j,cuts){
//            cout << rowcut[j];
//        }
//        cout << endl;
        
        map<int,int> counter;
        int col = 0;
        int looping = 0;
        int CUT = 0;
        int prev = 0;
        
        while(col < w){
            if (col == prev) looping = 1;
            prev = col;
            rep(j,cuts-1){
                for(int r = rowcut[j]; r < rowcut[j+1];r++){
                    counter[j] += choco[r][col];
                }
                if(counter[j] > k){
                    CUT = 1;
                }
            }
            if (CUT == 0) {col++; looping = 0;}
            else{
                if (looping) {cand = (int) 1e9;break;}
                map<int,int> tmp;
                counter = tmp;
                cand++;
                CUT = 0;
            }
        }

        cand += cuts-2;
        //cout << "            CAND " << cand << endl;
        ans = min(ans,cand);
    }
    cout << ans;
}



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

int main(){
  int N,M;
  cin>>N>>M;
  vector<int> X(M);
  for(int i=0;i<M;i++){
    cin>>X.at(i);
  }
  sort(X.begin(),X.end());
  vector<int> diff(M-1);
  for(int i=0;i<M-1;i++){
    diff.at(i)=X.at(i+1)-X.at(i);
  }
  sort(diff.begin(),diff.end());
  int ans=0;
  for(int i=0;i<M-N;i++){
    ans+=diff.at(i);
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n , k;
    cin >> n >> k;
    while(n!=0|| k!=0){
    vector<int>a(n);
    for(int i = 0;i < n;i++){
      cin >> a.at(i);
    }
   vector<int>S(n+1);
   S.at(0) = 0;
   for(int i = 0;i < n;i++){
     S.at(i+1) = S.at(i) + a.at(i);
   }
   int ans = 0;
   for(int i = 0;i+k < n+1;i++){
     if(S.at(i+k)-S.at(i) > ans)
     ans = S.at(i+k) - S.at(i);
   }
   cout << ans << endl;
   cin >> n >> k;
    }
 }


Measured memory_bytes: 3548
// #include <algorithm>
#include <stdio.h>
#include <vector>
#include <math.h>
#include <deque> 
#include <iostream>
using namespace std;

vector<unsigned int> Parent;
unsigned int queries;

// Sliding Window Minimum
void swm(vector<int> & elements, const int winsize){
  deque< pair<int, int> > window;
  int fb = 0; // first buffer
  for(int i = 0; i < elements.size() ; i++){
    while(!window.empty() && window.back().first >= elements[i] ){
      window.pop_back();
    }
    window.push_back(make_pair(elements[i], i));

    while(window.front().second <= i - winsize){
      window.pop_front();
    }
    fb++;
    if(fb >= winsize){
      printf("%d" , window.front().first);
      if(i < elements.size()-1){
        printf(" ");
      }
    }
  }
  printf("\n");
}

void ass(vector<int> v){
  int i = 0;
  for(const auto& e: v){
    printf("[%d]=%d\n" ,i ,e ); 
    i++;
  }
}

int main(){
	int N, L;
  scanf("%d %d" ,&N, &L);
  vector<int> elements(N);
  for(int i = 0 ; i < N; i++){
    int v;
    scanf("%d" ,&v );
		elements[i] = v;
  }
  swm(elements, L);
  return 0;
}



Measured memory_bytes: 6780
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String s = br.readLine();
        
        int count = 0;
        int min = 100000000;
        int[] memo = new int[n];
        
        for (int i = 0; i+1 < n; i++) {
            if (s.charAt(i+1) == 'E') count++;
        }
        memo[0] = count;
        
        for (int i = 1; i < n; i++) {
            memo[i] = memo[i-1];
            if (s.charAt(i-1) == 'W') memo[i]++;
            if (s.charAt(i) == 'E') memo[i]--;
        }
        /*for (int i = 0; i < n; i++) {
            char leader = s.charAt(i);
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                char member = s.charAt(j);
                if (i > j && member == 'W') count++;
                if (i < j && member == 'E') count++;
            }
            
            min = Math.min(count, min);
            count = 0;
        }*/
        int ans = memo[0];
        for (int i = 1; i < n; i++) {
            ans = Math.min(ans, memo[i]);
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 30164
#include <algorithm>
#include <array>
#include <assert.h>
#include <chrono>
#include <bitset>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <numeric>
#include <random>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<ld> vld;
typedef vector<vector<int>> vvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<ld>> vvld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector<pll> vpll;

#ifdef OLBOEB
mt19937 rnd(228 + 1488 + 238 + 24111997 % 322);
#else
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

void print_time() {
#ifdef OLBOEB
    cout.flush();
    cerr << "\ntime: " << clock() * 1.0 / CLOCKS_PER_SEC << endl;
#endif
}

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

template<class T1, class T2>
ostream& operator<< (ostream &out, pair<T1, T2> pair) { return out << "(" << pair.first << ", " << pair.second << ")";}
template<class T> ostream& operator<<(ostream& out, vector<T> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }
template<class T> ostream& operator<<(ostream& out, set<T> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }
template<class L, class R> ostream& operator<<(ostream& out, map<L, R> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }



int main() {
    cout << fixed << setprecision(20);
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    string s;
    cin >> s;
    ll k;
    cin >> k;
    ll n = sz(s);
    ll pr = 1;
    for (ll i = 1; i < n; ++i) {
        if (s[i] == s[i - 1]) ++pr;
        else break;
    }

    ll sf = 1;
    for (ll i = n - 2; i >= 0; --i) {
        if (s[i] == s[i + 1]) ++sf;
        else break;
    }

    if (pr == n) {
        cout << (n * k / 2) << endl;
        return 0;
    }

    ll ans = 0;
    char last = '_';
    ll cnt = 0;
    for (ll i = 0; i < n; ++i) {
        if (s[i] == last) {
            ++cnt;
        } else{
            last = s[i];
            ans += cnt / 2;
            cnt = 1;
        }
    }
    ans += cnt / 2;

    if (s[0] != s[n - 1]) {
        cout << (ans * k) << endl;
        return 0;
    }

    ans *= k;

    ans -= (k - 1) * (sf / 2);
    ans -= (k - 1) * (pr / 2);
    ans += (k - 1) * ((sf + pr) / 2);

    cout << ans << endl;

    print_time();
    return 0;
}



Measured memory_bytes: 764
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
  ll k;
  cin >>k;
  ll e[k];
  for(ll i=0;i<k;i++) cin >>e[i];
  vector <pair<ll,ll>> ee;//firstに何個か、secondにその数字
 sort(e,e+k);ll c=1;
 for(ll i=0;i<k;i++){//配列の中身がそれぞれ何個あるかのカウント
  if(e[i]==e[i+1]){
    c++;
    if(i==k-2){//122333みたいなときは3のところがansに入らないので
      if(c%2==1) ee.push_back(make_pair(c,e[i]));
      break;
    }
  }
  else{
    if(c%2==1) ee.push_back(make_pair(c,e[i]));
    if(i==k-2) {
        if(c%2==1)ee.push_back(make_pair(1,e[i+1]));//112223とかのときにansに3の分を足すため
        break;
    }
    c=1;
  }
}
cout <<ee.size()<<endl;
}


Measured memory_bytes: 3188
#include "bits/stdc++.h"
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

using ll = long long;
using ii = pair<int,int>;
using vi = vector<int>;
using vii = vector<ii>;
const int oo = 1e9+7;
const int mod = 1e9+7;

vector<vi> edges;
vector<vi> dp;

int add(const int a, const int b) {
    return (a + b) % mod;
}

int mult(const int a, const int b) {
    return (ll) a * b % mod;
}

// number of ways subtree with a as root and p as parent
// can be painted with vertex a being of color c
int dfs(int a, int p, int c) {
    
    if(dp[a][c] != -1) return dp[a][c];
    
    int ans = 1;
    
    for(int b : edges[a]) if(b != p) {
         
         if(c == 0) { //white
            ans = mult(ans, add(dfs(b, a, 0), dfs(b, a, 1)));
         } else if(c == 1) {
            ans = mult(ans, dfs(b, a, 0)); // no black vertices can touch each other
         }
    }
    
    return dp[a][c] = ans;
}

int main() {
    
    int n;
    scanf("%d",&n);
    
    edges.resize(n+1);
    dp.assign(n+1, vector<int>(2, -1));
    
    for(int i = 0; i < n-1; ++i) {
        int a, b;
        scanf("%d%d",&a,&b);
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    
    int ans = dfs(1, -1, 0);
    ans = add(ans, dfs(1, -1, 1));
    
    printf("%d\n", ans);
    
    return 0;
}




Measured memory_bytes: 19584
void swap(int *a, int *b)
{
	int t;

	t = *a;
	*a = *b;
	*b = t;	
}
int main(int argc, char *argv[])
{
	int a;
	int b;
	int c;
	scanf("%d %d %d\n", &a, &b, &c);
	for (;;)
	{
		if ((a <= b) && (b <= c))
		{
			break;
		}

		if (a > b)
		{
			swap(&a, &b);
		}
		if (b > c)
		{
			swap(&b, &c);
		}
	}
	printf("%d %d %d\n", a, b, c);
	return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
using namespace std;
#define popcnt(a) __builtin_popcount(a)
#define FastIO() ios::sync_with_stdio(false), cin.tie(0);
#define IO() freopen("palindrome.in","rw",stdin)
#define error(args...)                       \
{                                            \
    cerr<<"LINE "<<__LINE__;                 \
    string _s = #args;                       \
    replace(_s.begin(), _s.end(), ',', ' '); \
    stringstream _ss(_s);                    \
    istream_iterator<string> _it(_ss);       \
    err(_it, args);                          \
    cerr<<endl;                              \
}
void err(istream_iterator<string> it)
{
} 
template <typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args)
{
  cerr<<' '<< *it << " = " << a ;
  err(++it, args...);
} 
typedef long long LL;
const LL MOD = 1e9 + 7;
const int N = 2e3+9, M = (1<<31), OO = 0x3f3f3f3f;
int main()
{
  int a,b,x,y;
  scanf("%d%d%d%d",&a,&b,&x,&y);
  
  printf("%.6lf %d",((a*1.0)/2.0)*b*1.0,(x+x==a && y+y==b));
  #ifdef _LOCAL_DEFINE
  cerr << (double)clock() * 1.0 / CLOCKS_PER_SEC << endl;
  #endif
  return 0; 
}

Measured memory_bytes: 256
N = int(input())
L = [int(x) for x in input().split()]
cnt = 0

for i in range(len(L) - 2):
    for j in range(i+1, len(L)-1):
        for k in range(j+1, len(L)):
            a = L[i]
            b = L[j]
            c = L[k]
            p = a + b > c
            q = b + c > a
            r = c + a > b
            s = a != b
            t = b != c
            u = c != a
            if p and q and r and s and t and u:
                cnt += 1
print(cnt)

Measured memory_bytes: 9148
#include<iostream>
#include<stack>
#include<cmath>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<cstdlib>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<cctype>
#include<set>
#include<climits>
#include<cassert>
#include<iterator>
#include<random>
#include<bitset>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<map>
#include<ctime>
#include<complex>
#include<functional>
#include<unordered_set>
#include<unordered_map>

using namespace std;

long long int a;
long long int b;
long long int c;

int main() {
	cin >> a >> b >> c;
	long long int al = min(c, b+a+1);
	al += b;
	printf("%lld\n", al);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T, class U> using Pa = pair<T, U>;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int K;
    cin >> K;
    ll ans = 0;
    for(int i=1;i<=K;i++) for(int j=1;j<=K;j++) for(int k=1;k<=K;k++) ans += gcd(i,gcd(j,k));
    cout << ans << "\n";
}

Measured memory_bytes: 3612
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<list>
#include<cmath>
#include<algorithm>
#define lson node<<1,st,mid
#define rson node<<1|1,mid+1,ed
#define mem(a,x) memset(a,x,sizeof(a))
#define me(a) memset(a,0,sizeof(a))
#define IOS ios::sync_with_stdio(false)
#define lowbit(x) x&(-x)
#define up(i,x,y) for(long long i=x;i<y;i++)
#define down(i,x,y) for(long long i=x;i>=y;i--)
#define in freopen("in.txt","r",stdin)
#define out freopen("out.txt","w",stdout)   
typedef long long ll;
const ll mod = 1e9+7;
const ll INF = 0x3f3f3f3f;
const ll maxn = 1e5 + 5;
const double pi = acos(-1.0);
const double eps=1e-9;
using namespace std;
ll qpow(ll a, ll b) { ll s = 1; while (b > 0) { if (b & 1)s = s * a % mod; a = a * a % mod; b >>= 1; }return s; }

 
ll poww(ll x,ll n) {
    ll res = 1;
    x%=mod;
    while (n) {
        if(n&1) res = res*x%mod;
        x = x*x %mod;
        n >>=1;
    }
    return res;
}

ll C(ll n,ll m) {
    if(n < m) return 0;
    // c(n,m) = n!/m!/(n-m)!
    ll res = 1;
    for(int i=1; i<=m; i++) {
        ll a = (n+i-m)%mod;
        ll b = i%mod;
        res = res*(a*poww(b,mod-2)%mod)%mod;
    }
    return res;
}

ll Lucas(ll n,ll m) {
    if(m == 0) return 1;
    return C(n%mod, m%mod) * Lucas(n/mod,m/mod)%mod;
}
int main()
{
	ll n,a,b;
	cin>>n>>a>>b;
    ll x,y,z;
    x=Lucas(n,a);
    y=Lucas(n,b);
    z=poww(2,n)-1;
    if(z-x-y<0) cout<<(z-x-y+mod+mod)%mod<<endl;
    else cout<<z-x-y<<endl;
}

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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define REP(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define each(i,c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define all(v) v.begin(), v.end()
#define mset(a, n) memset(a, n, sizeof(a))

typedef long long ll;

const int INF = 1000000000;
const int MOD = 1000000007;

int main () {
	string s; cin >> s;
	int b_cnt = 0, c_cnt = 0;
	REP(i, 1, s.size()) {
		if ((i > 1 && i < (int)s.size() - 1) && s[i] == 'C') b_cnt++;
		if (s[i] >= 'a' && s[i] <= 'z') c_cnt++;
	}
	
	bool a = false, b = false, c = false;
	if (s[0] == 'A') a = true;
	if (b_cnt == 1) b = true;
	if (b && c_cnt == (int)s.size() - 2) c = true;
	
	cout << (a && b && c ? "AC" : "WA") << endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PI 3.141592653589793
#define rep(i, n) for (int i = 0; i < (n); i++)
#define REP(i, a, n) for (int i = a; i < (n); i++)
#define rrep(i, n, k) for (int i = (n); i >= (k); i--);
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;}
template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<class T>vector<T> make_vector(size_t a){return vector<T>(a);}
template<class T, class... Ts>auto make_vector(size_t a, Ts... ts){return vector<decltype(make_vector<T>(ts...))>(a, make_vector<T>(ts...));}
const int MOD = 1e9+ 7;
const int INF = 2e18;

struct info {
    int a, b, c;
};

signed main() {
    int N, Ma, Mb;
    cin >> N >> Ma >> Mb;
    vector<vector<vector<int>>> dp(N + 1, vector<vector<int>>(501, vector<int>(501, INF)));
    vector<info> store(N + 1);
    for (int i = 1; i <= N; i++) cin >> store[i].a >> store[i].b >> store[i].c;
    dp[0][0][0] = 0;
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= 500; j++) {
            for (int k = 0; k <= 500; k++) {
                dp[i][j][k] = dp[i - 1][j][k];
                if (j - store[i].a >= 0 && k - store[i].b >= 0) dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j - store[i].a][k - store[i].b] + store[i].c);
                // if (j % Ma == 0 && k % Mb == 0) cout << i << " " << j << " " << k << endl;
            }
        }
    }
    int ans = INF;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= 500; j++) {
            for (int k = 1; k <= 500; k++) {
                if (Mb * j == Ma * k) ans = min(ans, dp[i][j][k]);
            }
        }
    }
    cout << (ans == INF ? -1 : ans) << endl;
}


Measured memory_bytes: 83328
import java.util.Scanner;

/**
 * Created by codoge on 2017/6/11.
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int r = scanner.nextInt();
        int g = scanner.nextInt();
        int b = scanner.nextInt();
        if (canDivide4(r, g, b)) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }

    private static boolean canDivide4(int r, int g, int b) {
        if (g % 2 == 0) {
            return b % 4 == 0;
        } else {
            return (b+2) % 4 == 0;
        }
    }
}


Measured memory_bytes: 21588
//#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<utility>
#include<algorithm>
#include<cstring>
#include<sstream>
#include <iomanip>

using namespace std;

typedef long long ll ;
typedef double db;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector< pair<int,int> > vii;
const double pi = 2*acos(0) ;

#define pf		  	printf
#define sf			  scanf
#define pb(a)         push_back(a)
#define mp			make_pair
#define fi			 first
#define se			 second
#define for0(i,n)        for(int i=0;i<n;i++)
#define for1(i,n)        for(int i=1;i<=n;i++)
#define forab(i,a,b)       for(int i=a;i<=b;i++)
#define lcm(a, b)     ((a)*((b)/gcd(a,b)))
#define sq(a)		   (a)*(a)
#define nw				"\n"
#define abs(x)		fabs(x)
#define pcase(z,x)    cout<<"Case "<<z<<": "<<x<<"\n"

int main()
{
	int i,j,n,c=0,m=0;
	cin>>n;
	vi ar(n);
	for0(i,n) cin>>ar[i];
	for1(i,n-1){
		if(ar[i]>ar[i-1]){
			m = max(m,c);
			c=0;
			}
		else c++;
		}
	m = max(c,m);
	cout<<m<<nw;
	return 0;
}

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

int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> room(n+1);
    rep(i,m){
        int s,t;
        cin >> s >> t;
        room[s].emplace_back(t);
        room[t].emplace_back(s);
    }
    vector<int> sign(n+1, 0);
    sign[1] = 1;

    queue<int> q;
    q.push(1);
    while(q.size()){
        int now = q.front();
        q.pop();
        for(int i : room[now]){
            if(!sign[i]){
                q.push(i);
                sign[i] = now;
            }
        }
    }

    cout << "Yes" << endl;
    rep2(i,2,n+1) cout << sign[i] << endl;


    return 0;
}

Measured memory_bytes: 10148
package main

import "fmt"

func min(a ...int) int {
	m := a[0]
	for i, v := range a {
		if i == 0 {
			continue
		}
		if m > v {
			m = v
		}
	}
	return m
}

func main() {
	// Code for A - Airplane
	var P, Q, R int
	fmt.Scan(&P, &Q, &R)

	fmt.Println(min(P+Q, Q+R, R+P))
}


Measured memory_bytes: 1768
#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 200000;
const int MAXM = 200000;

int N, M;
long long A[MAXN];
int L[MAXM], R[MAXM];

int pre[MAXN + 1];
long long dp[MAXN + 1];

int main()
{
	scanf("%d%d", &N, &M);
	for (int i = 0; i < N; ++i) {
		scanf("%lld", &(A[i]));
	}
	for (int i = 0; i < M; ++i) {
		scanf("%d%d", &(L[i]), &(R[i]));
	}

	for (int i = 1; i <= N; ++i) {
		pre[i] = i - 1;
	}
	for (int i = 0; i < M; ++i) {
		pre[R[i]] = min(pre[R[i]], L[i] - 1);
	}
	for (int i = N - 1; i >= 1; --i) {
		pre[i] = min(pre[i], pre[i + 1]);
	}

	dp[0] = 0;
	for (int i = 1; i <= N; ++i) {
		dp[i] = max(dp[i - 1], dp[pre[i]] + A[i - 1]);
	}

	printf("%lld\n", dp[N]);
	return 0;
}


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

using namespace std;

using ll = long long;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s, t;
    cin >> s >> t;
    vector<int> cnt1(26, 0), cnt2(26, 0);
    for (char& c : s) cnt1[c - 'a']++;
    for (char& c : t) cnt2[c - 'a']++;
    sort(cnt1.begin(), cnt1.end());
    sort(cnt2.begin(), cnt2.end());
    for (int i = 0; i < 26; i++) {
        if (cnt1[i] != cnt2[i]) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 916
# パス(edge)： N−1 個   距離1
# スターグラフ： N−1C2個 最短距離 2
# 完全グラフ：0 個
import itertools
N, K = map(int, input().split())
MAX = (N-1)*(N-2)//2
if K > MAX:
  print(-1)
  exit()

#1つの頂点を真ん中に固定し,それからスターグラフになるように作成
edge = [(1, n) for n in range(2, N+1)]
edge += list(itertools.combinations(range(2, N+1),2))[:MAX-K]

print(len(edge))
for x, y in edge:
  print(x,y)

Measured memory_bytes: 3992
A,B,K=input().split(" ")
A=int(A)
B=int(B)
K=int(K)

if A-K>=0:
    ans1=A-K
    ans2=B
else:
    if B-(K-A)<=0:
        ans1=0
        ans2=0
    else:
        ans1=0
        ans2=B-(K-A)

print(ans1,ans2)

Measured memory_bytes: 38384
#include<bits/stdc++.h>
using namespace std;
#define sc scanf
#define pr printf
#define pb push_back
#define ll long long int
#define rp
int main()
{
    ll a,b;
    cin>>a>>b;
    if(a<=9&& b<=9)
        cout<<a*b<<endl;
    else
        cout<<"-1"<<endl;

    return 0;
}

Measured memory_bytes: 256
#define FASTIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//#define BZ
//#define PBDS
//#define POINT

#ifndef BZ
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("no-stack-protector")
#pragma GCC target ("tune=native")
//#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize ("conserve-stack")
//#pragma GCC optimize ("no-stack-limit")
#endif

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using str = string;
using pll = pair<ll, ll>;

#ifdef POINT
using point = complex<ll>;
#define x real
#define y imag
#endif

#ifdef PBDS
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
//using namespace __gnu_pbds::detail;
template <class T>
using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#endif

#define INF 0x7fffffffffffffffLL
#define BASE 1000000007LL // 3 * 10**9 + 19 // 998244353 - rev == pow(n + m, BASE - 2)
#define MAX(type) std::numeric_limits<type>::max()
#define MIN(type) std::numeric_limits<type>::min()

#define LOG(v) cout << #v << " " << v << "\n";

#define pb push_back
#define eb emplace_back
//#define all(c) c.begin(), c.end()
//#define rall(c) c.rbegin(), c.rend()
#define F first
#define S second
#define forEach(c) for (auto &it : c)
#define loop while (true)
#define mp make_pair
#define mt make_tuple

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

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

inline ll divUp(ll a, ll b) {
	return (a + b - 1)/b;
}

void solve() {
	ll a, b;
	cin >> a >> b;
	if (a < 10 && b < 10) {
		cout << a * b << "\n";
	} else {
		cout << "-1\n";
	}
}

//#define LOCAL

int main() {
	FASTIO
#ifdef LOCAL
	auto start = std::chrono::system_clock::now();
#endif
	solve();
#ifdef LOCAL
	auto end = std::chrono::system_clock::now();
	std::chrono::duration<ld> elapsed_seconds = end - start;
	cerr << "\ntime: " << elapsed_seconds.count() << " s\n";
#endif
	return 0;
}


Measured memory_bytes: 256
from collections import defaultdict

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
      return self.parents[x]

  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x == y:
      return
    if self.parents[x] > self.parents[y]:
      x, y = y, x
    self.parents[x] += self.parents[y]
    self.parents[y] = x

  def size(self, x):
    return -self.parents[self.find(x)]

  def same(self, x, y):
    return self.find(x) == self.find(y)

  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]

  def group_count(self):
    return len(self.roots())

  def all_group_members(self):
    ret = defaultdict(list)
    for i in range(self.n):
      ret[self.find(i)].append(i)
    return ret

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, K = map(int, input().split())
P = list(map(lambda x: int(x)-1, input().split()))
C = list(map(int, input().split()))

uf = UnionFind(N)

for i in range(N):
  uf.union(i, P[i])

D = uf.all_group_members()
E = defaultdict(list)
F = defaultdict(int)

Num = [0]*N

for root in uf.roots():
  i = root
  n = 0
  E[root].append(0)
  while P[i] != root:
    i = P[i]
    n += 1
    Num[i] = n
    E[root].append(E[root][-1] + C[i])
  E[root].append(E[root][-1] + C[root])
  F[root] = n + 1
  i = root
  while P[i] != root:
    i = P[i]
    E[root].append(E[root][-1] + C[i])
  E[root].append(E[root][-1] + C[root])

#print(Num, E, F, sep="\n")
ans = -float("inf")

for root, L in E.items():
  loop, k = divmod(K, F[root])
  if k == 0:
    loop -= 1
    k += F[root]
  temp = 0
  if L[-1] >= 0:
    temp += (L[-1]//2) * loop
  else:
    if loop >= 1:
      k = F[root]
  for i in range(F[root]):
    for j in range(i+1, i+k+1):
      ans = max(ans, temp + E[root][j] - E[root][i])

print(ans)

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

using LL = long long;

#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define FOR(i, a, b) for (int(i) = (a); (i) < (b); ++(i))
#define RFOR(i, a, b) for (int(i) = (a); (i) > (b); --(i))
#define SORT(x) sort(ALL((x)))
#define RSORT(x) sort(RALL((x)))
#define SZ(x) (int)(x).size()
#define debug(x) cerr << #x << " : " << x << '\n'

const int INF = 1e9;
const int MOD = 1e9 + 7;
const LL LINF = 1e18;

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

  string ans;
  int X, A, B;
  cin >> X >> A >> B;

  if (A >= B) {
    ans = "delicious";
  } else {
    if ((X + A) >= B) {
      ans = "safe";
    } else {
      ans = "dangerous";
    }
  }

  cout << ans << '\n';

  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <cmath>
#include <cassert>
#include <unordered_map>
#define int long long

using namespace std;

typedef pair<int, int> pa;
typedef long long ll;
typedef long double ld;

int gcd(int a, int b) {
    if (b > a) swap(a, b);
    while (b) {
        int c = a % b;
        a = b;
        b = c;
    }
    return a;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n;
    cin >> n;
    int sm = 0;
    for (int a = 1; a <= n; ++a)
        for (int b = 1; b <= n; ++b)
            for (int c = 1; c <= n; ++c) {
                sm += gcd(gcd(a, b), c);
            }
    cout << sm;
}

Measured memory_bytes: 3620