akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        int n;
        try (Scanner cin = new Scanner(System.in)) {
            n = cin.nextInt();
        }
        int minsum = Integer.MAX_VALUE;
        for (int a = 1; a <= n / 2; a++) {
            int min = digitsSum(a) + digitsSum(n-a);
            minsum = Math.min(minsum, min);
        }

        System.out.println(minsum);
    }

    static int digitsSum(int x) {
        int t = x;
        int s = 0;
        while(t > 0) {
            s += t % 10;
            t = t / 10;
        }
        return s;
    }
}


Measured memory_bytes: 24276
<?php

$input = trim(fgets(STDIN));

$arr = [$input[0]];
$tmp = '';
for($i = 1;$i < strlen($input);$i++) {
  $m = count($arr);
  $tmp .= $input[$i];

  if($arr[$m - 1] === $tmp) {

  } else {
    $arr[] = $tmp;
    $tmp = '';
  }
}

echo count($arr)."\n";

Measured memory_bytes: 19316
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=1e6+10;
int n,k,c,ans[maxn],num;
char s[maxn];
bool f[maxn];
int main()
{
	scanf("%d%d%d%s",&n,&k,&c,s+1); int lc=0;
	for (int i=1;i<=n;i++) if (s[i]=='o') {lc=i; break;}
	num=1; ans[num]=lc;
	for (int i=lc+1;i<=n;i++)
	if (s[i]=='o' && i-lc-1>=c && num<k) {num++; ans[num]=i; lc=i;}
	for (int i=n;i>=1;i--) if (s[i]=='o') {lc=i; break;}
	num=k; lc=1e9;
	for (int i=n;i>=1;i--)
	if (s[i]=='o' && lc-i-1>=c && num) {if (i==ans[num]) f[i]=1; num--; lc=i;}
	for (int i=1;i<=n;i++) if (f[i]) printf("%d\n",i);
return 0;
}

Measured memory_bytes: 4096
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <math.h> // sqrt
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    vector<long long> high(N);
    for (int i = 0; i < N; i++) {
        cin >> high.at(i);
    }
    vector<vector<int>> road(M, vector<int>(2));
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < 2; j++) {
            cin >> road.at(i).at(j);
        }
    }
    vector<bool> bit(N, true);
    int ha, hb;
    for (int i = 0; i < M; i++) {
        ha = road.at(i).at(0) - 1;
        hb = road.at(i).at(1) - 1;
        if (high.at(ha) <= high.at(hb)) {
            bit.at(ha) = false;
        }
        if (high.at(hb) <= high.at(ha)) {
            bit.at(hb) = false;
        }
    }
    int ans = 0;
    for (int i = 0; i < N; i++) {
        if (bit.at(i)) {
            ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 9508
p=list("MARCH")
d=[0]*5
n=int(input())
for i in range(n):
    r=input()
    q=r[0]
    if r[0] in p:
        d[p.index(r[0])]+=1
c=0
for i in range(3):
    for j in range(i+1,4):
        for s in range(j+1,5):
            c+=d[i]*d[j]*d[s]
print(c)

Measured memory_bytes: 3060
from collections import Counter
n, k = map(int, input().split())
a = Counter([int(x) for x in input().split()])
all_balls = len(a)

result = 0
for _, x in reversed(a.most_common()):
  if k >= all_balls:
    break
  result += x
  all_balls -= 1

print(result)

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

#define dump(...) cout<<"# "<<#__VA_ARGS__<<'='<<(__VA_ARGS__)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}

template<typename Tuple>
void print_tuple(ostream&,const Tuple&){}
template<typename Car,typename... Cdr,typename Tuple>
void print_tuple(ostream& os,const Tuple& t){
	print_tuple<Cdr...>(os,t);
	os<<(sizeof...(Cdr)?",":"")<<get<sizeof...(Cdr)>(t);
}
template<typename... Args>
ostream& operator<<(ostream& os,const tuple<Args...>& t){
	print_tuple<Args...>(os<<'(',t);
	return os<<')';
}

template<typename Ch,typename Tr,typename C,typename=decltype(begin(C()))>
basic_ostream<Ch,Tr>& operator<<(basic_ostream<Ch,Tr>& os,const C& c){
	os<<'[';
	for(auto i=begin(c);i!=end(c);++i)
		os<<(i==begin(c)?"":" ")<<*i;
	return os<<']';
}

constexpr int INF=1e9;
constexpr int MOD=1e9+7;
constexpr double EPS=1e-9;

struct UnionFind{
	vi data;
	UnionFind(int n):data(n,-1){}
	int Find(int i){
		return data[i]<0?i:(data[i]=Find(data[i]));
	}
	bool Unite(int a,int b){
		a=Find(a),b=Find(b);
		if(a==b) return false;
		if(-data[a]<-data[b]) swap(a,b);
		data[a]+=data[b];
		data[b]=a;
		return true;
	}
	int Size(int i){
		return -data[Find(i)];
	}
};

struct Edge{
	int src,dst,weight;
	Edge(){}
	Edge(int s,int d,int w):src(s),dst(d),weight(w){}
};
typedef vector<vector<Edge>> Graph;

int main()
{
	for(int n,m;cin>>n>>m && n|m;){
		vector<Edge> es;
		int neg=0;
		rep(i,m){
			int u,v,w; cin>>u>>v>>w;
			if(w<=0) neg+=w;
			else es.emplace_back(u,v,w);
		}
		m=es.size();
		
		int res=INF;
		{
			UnionFind uf(n);
			int cc=n;
			rep(i,m)
				cc-=uf.Unite(es[i].src,es[i].dst);
			if(cc>=2) res=0;
		}
		{
			rep(i,m){
				vi use(m,1); use[i]=0;
				UnionFind uf(n);
				int cc=n;
				rep(j,m) if(use[j])
					cc-=uf.Unite(es[j].src,es[j].dst);
				if(cc>=2) res=min(res,es[i].weight);
			}
		}
		{
			rep(i,m) repi(j,i+1,m){
				vi use(m,1); use[i]=use[j]=0;
				UnionFind uf(n);
				int cc=n;
				rep(k,m) if(use[k])
					cc-=uf.Unite(es[k].src,es[k].dst);
				if(cc>=2) res=min(res,es[i].weight+es[j].weight);
			}
		}
		cout<<neg+res<<endl;
	}
}

Measured memory_bytes: 1200
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
#define ll long long 
int x;
int main(){
    scanf("%d",&x);
    for (int i=1;i<=360;++i){
        if (i*x%360==0){
            cout<<i<<endl;
            break;
        }
    }
    return 0;
}

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

int main()
{
	int n;
	scanf("%d", &n);
	int count{};
	for (int i{}; i < n; i++)
	{
		char s;
		scanf(" %c", &s);
		if (s == 'R') count++;
	}
	if (count > n - count) puts("Yes");
	else puts("No");

	return 0;
}

Measured memory_bytes: 256
using System;
using System.Diagnostics;
using System.IO;
using System.Text;
using System.Linq;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args) {
#if DEBUG
        MyDebugger.Test(process, "../TextFile1.txt");
        //MyDebugger.Test(process, "../TextFile2.txt");
        //MyDebugger.MakeTestCase("../TextFile2.txt");
#else
        object ret = process(new StreamReader(Console.OpenStandardInput()));
        Console.WriteLine(ret);
#endif
    }

    static object process(TextReader input) {
        var spl   = input.ReadLine().Split(' ');
        var a     = int.Parse(spl[0]);
        var b     = int.Parse(spl[1]);

        return (a + b - 1) / b;
    }
}

Measured memory_bytes: 13140
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define int long long int
#define pb push_back
#define fi first
#define se second
#define fr(i, a, b) for(int i = a; i <= b; i++)
#define all(x) x.begin(), x.end()
#define IO ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
const int mod = 1e9 + 7;
const int mod1 = 998244353;
typedef long double f80;
#ifndef LOCAL
#define endl '\n'
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r){
    uniform_int_distribution<int> uid(l, r);
    return uid(rng);
}
const int N = 1e6 + 5;
string s;
int cnt[N], pre[N], val[N], preval[N];
void solve(){
    int n;
    cin >> n;
    cin >> s;
    s = "0" + s;
    for(int i = n; i >= 1; i--){
        pre[i] = pre[i + 1] + (s[i] == 'M');
        if(s[i] == 'D'){
            val[i] = pre[i];
        }
        cnt[i] = cnt[i + 1] + (s[i] == 'D');
    }
    for(int i = n; i >= 1; i--){
        preval[i] = preval[i + 1] + val[i];
    }
    int q;
    cin >> q;
    while(q--){
        int ans = 0;
        int k;
        cin >> k;
        fr(i, 1, n){
            if(s[i] == 'C'){
                int j = max((int)1, i - k + 1);
                int vall = preval[j] - (cnt[j] - cnt[i]) * pre[i] - preval[i];
                ans += vall;
            }
        }
        cout << ans << endl;
    }
}
signed main()
{
    IO;
    #ifdef LOCAL
        freopen("inp.txt", "r", stdin);
        // freopen("out.txt", "w", stdout);
    #endif
    clock_t clk = clock();
    int t = 1;
    // cin >> t;
    fr(i, 1, t){
        solve();
    }
    cerr << endl << setprecision(10) << fixed << (double)(clock() - clk) / CLOCKS_PER_SEC;
    return 0;
};

Measured memory_bytes: 32584
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define vl vector<long long int>
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vb vector<bool>
#define vvl vector<vector<ll> >
#define vvi vector<vector<int> >
#define pl pair<ll,ll>
#define pb push_back
#define PI 3.14159265
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define fri(s,n) for(int i=s;i<n;i++)
#define frj(s,n) for(int j=s;j<n;j++)
#define T(i) int i=1;cin>>i;while(i--)
#define vsi vector<set<int> >
#define pii pair<int,int>
#define inf 1e9
#define vpii vector<pair<int,int> >


ll power(ll a,ll b){
    if(b==0)
        return 1;
    if(b&1)
        return a*power(a,b-1);
    ll temp=power(a,b/2);
    return temp*temp;
    }
bool mycompare(ll a,ll b){
    return a>b;
    }
int dp[22][(1<<22)];
int n;
int solve(vvi &relation,int wset,int men){
	if(men==n+1){
      if(wset==0)
        return 1;
      return 0;}
  	if(dp[men][wset]!=-1)
      	return dp[men][wset];
  	int ans=0;
  	for(int w=0;w<n;w++){
    	bool present=(1<<w)&wset;
      	if(present && relation[men][w+1]==1){
          ans+=solve(relation,wset^(1<<w),men+1);
          ans%=mod;
    }}
     return dp[men][wset]=ans;
}

int main(){
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    cin>>n;
    vvi relation(n+1,vi(n+1));
  	memset(dp,-1,sizeof dp);
  	for(int i=1;i<=n;i++){
      	for(int j=1;j<=n;j++){
          	cin>>relation[i][j];}}
  	cout<<solve(relation,(1<<n)-1,1);



}


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

#define ll long long
#define vecll vector<long long>
#define vec2ll vector<vector<long long>>
#define vecbool vector<bool>
#define vecpairll vector<pair<long long,long long>>
#define forll(s,a,b) for(long long s = a;s < b;s++)
#define forllde(s,a) for(long long s = a;s > 0;s--)


int main()
{
  ll n, p;
  string s, t;
  cin >> n >> s >> t;
  forll(i, 0, t.size()){
	if(t.substr(0, t.size()-i) == s.substr(i)){
	  p = i;
	  break;
	}
  }
  cout << s.size() + p << endl;
}


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

int N, K;
vector<int> d;
vector<vector<int>> A;

int main()
{
	cin >> N >> K;
	d.resize(K); 
	A.resize(K, vector<int>());
	for (int i = 0; i < K; i++)
	{
		cin >> d[i];
		A[i].resize(d[i]);
		for (int j = 0; j < d[i]; j++)
		{
			cin >> A[i][j];
		}
	}

	int ans = 0;
	for (int i = 1; i <= N; i++)
	{
		bool have = false; //haveは変数
		for (auto v : A)
		{
			for (auto p : v)
			{
				if (p == i)have = true;
			}
		}
		if (!have) ans++;
	}
	cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 3628
import java.util.Scanner;
public class Main{
 public static void main(String[] args){
   Scanner sc = new Scanner(System.in);
   int n = sc.nextInt();
   String X = sc.next();
   String Y = sc.next();
   
   String ans = "";

   for(int i = 0;i<n;i++)
   {
     ans+=X.substring(i,i+1)+Y.substring(i,i+1);
   }
   
     System.out.println(ans);
   
 }
}

Measured memory_bytes: 21844
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#include <utility>

#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cstdint>

using namespace std;

typedef long long ll;

int w,h;
char m[22][22];

void rec(int x,int y) {
	if(m[x][y] == '.') {
		m[x][y] = '!';
		rec(x+1,y);
		rec(x-1,y);
		rec(x,y+1);
		rec(x,y-1);
	}
}

int main() {
	while(1) {
		cin >> w >> h;
		if(!(w | h)) break;
		string s;
		for(int i = 0;i < 22;i++)for(int j = 0;j < 22;j++) m[i][j] = '#';
		for(int y = 1;y <= h;y++) {
			cin >> s;
			for(int x = 1;x <= w;x++) {
				m[x][y] = s[x-1];
			}
		}
		for(int x = 0;x < 22;x++)for(int y = 0;y < 22;y++) 
			if(m[x][y] == '@') {
				m[x][y] = '.';
				rec(x,y);
			}
		int cnt = 0;
		for(int x = 0;x < 22;x++)for(int y = 0;y < 22;y++) 
			if(m[x][y] == '!') cnt++;
		cout << cnt << endl;
	}
}


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

using namespace std;

int main(){
    long long N,M;
    cin >> N >> M ;
    long long sum[N+1] = {};
    for(long long i=1; i<N+1; i++){
        long long a;
        cin >> a;
        sum[i] = (sum[i-1]+a) % M;
    }
    sort(sum,sum+N+1);
    long long ans = 0;
    long long t = 1;
    long long u = sum[0];
    long long count = 1;
    while(t < N+1){
        if(sum[t] == u){
            count++;
            t++;
        }
        else{
            ans += (count-1)*count/2;
            u = sum[t];
            count = 1;
            t++;
        }
    }
    ans += (count-1)*count/2;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int>pii;
const int maxn=1e5+100;

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(0);
    int arr[3];
    cin>>arr[0]>>arr[1]>>arr[2];
    sort(arr, arr+3);
    cout<<arr[2]-arr[0]<<"\n";
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)

ll gcd(ll a, ll b){
    if(a < b) return gcd(b, a);
    ll r = a % b;
    while(r != 0){
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}
ll lcm(ll a, ll b){
    ll ret = (a * b)/gcd(a,b);
    return ret;
}

int main(){
    ll K;
    cin >> K;
    ll ans = 0;
    rep(a, 1, K+1){
        rep(b, 1, K+1){
            rep(c, 1, K+1){
                ll tmp = gcd(a, b);
                ans += gcd(tmp, c);
            }
        }
    }

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

Measured memory_bytes: 3636
D = int(input())
C = list(map(int, input().split()))
S = [tuple(map(int, input().split())) for _ in range(D)]
Z = 26

last = [-1] * Z
ans = 0
T = []
for d in range(D):
    maxScore = -float('inf')
    cand = 0
    for i in range(26):
        tmp = last[i]
        last[i] = d
        up = S[d][i]
        down = sum(C[j] * (d - last[j]) for j in range(Z))
        score = up - down
        if maxScore < score:
            cand = i
            maxScore = score
        last[i] = tmp
    T.append(cand + 1)
print(*T, sep='\n')


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

using ll = long long;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;
using vint = vector<int>;
using vll = vector<ll>;
using uint = unsigned int;
using ull = unsigned long long;

template<typename T> using uset = unordered_set<T>;
template<typename T1, typename T2> using umap = unordered_map<T1, T2>;

constexpr int INF = (1 << 30) - 1;
constexpr ll LLINF = 1LL << 60;
constexpr int dy[] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr char el = '\n';
constexpr int mod = 1000000007;

template<typename T> T gcd(T a, T b) { return (b ? gcd(b, a % b) : a); }
template<typename T> T lcm(T a, T b) { return (a / gcd(a, b) * b); }
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }

template<typename T>
ostream& operator <<(ostream &os, vector<T> &v) {
	for (auto &u : v) os << u << el;
	return (os);
}

template<typename T>
istream& operator >>(istream &is, vector<T> &v) {
	for (auto &u : v) is >> u;
	return (is);
}

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

	int Q; cin >> Q;
	while (Q--) {
		int K; cin >> K;
		ll ans = 0ll;

		ll mnum = 0, dnum = 0, pot = 0;
		for (int i = 0; i < N; i++) {
			if (S[i] == 'D') dnum++;
			if (S[i] == 'M') pot += dnum, mnum++;
			if (S[i] == 'C') ans += pot;
			if (i >= K - 1) {
				if (S[i-K+1] == 'D') pot -= mnum, dnum--;
				if (S[i-K+1] == 'M') mnum--;
			}
		}

		cout << ans << el;
	}
	
	return (0);
}

Measured memory_bytes: 1412
import heapq
import math

N, M = map(int, input().split())
A = list(map(int, input().split()))

B = [-A[i] for i in range(N)]
heapq.heapify(B)
while M:
    p = heapq.heappop(B)
    p /= 2
    heapq.heappush(B, p)
    M -= 1

ans = 0
for i in range(N):
    ans += math.floor(-B[i])
print(ans)


Measured memory_bytes: 93072
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#include <map>

#define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl;
#define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl;

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

int N;
int A[200000], B[200000];

int cnta[200000], cntb[200000];
int ans[200000];
P p[200000];

set<int> rem, used;

vector<int> va[200000];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(10) << fixed;
    cin >> N;
    for(int i = 0; i < N; i++) {
        cin >> A[i]; A[i]--;
        cnta[A[i]]++;
        rem.insert(i);
        va[A[i]].push_back(i);
    }
    for(int i = 0; i < N; i++) {
        cin >> B[i]; B[i]--;
        cntb[B[i]]++;
    }
    for(int i = 0; i < N; i++){
        if(cnta[i]+cntb[i] > N){
            cout << "No" << endl;
            return 0;
        }
        p[i] = P(cnta[i]+cntb[i], i);
    }
    sort(p, p+N, greater<P>());
    for(int i_ = 0; i_ < N; i_++){
        vector<int> to_erase;
        auto it = rem.begin();
        int i = p[i_].second;
        for(int j = 0; j < cntb[i]; j++){
            bool find = false;
            while(true){
                if(it == rem.end()) break;
                if(A[*it] != i){
                    to_erase.push_back(*it);
                    it++;
                    find = true;
                    break;
                }
                it++;
            }
            if(!find){
                int tmp = *(used.begin());
                ans[tmp] = i;
                used.erase(tmp);
            }
        }
        for(int j : to_erase){
            ans[j] = i;
            rem.erase(j);
        }
        for(int j : va[i]){
            if(rem.count(j) > 0){
                rem.erase(j);
                used.insert(j);
            }
        }
    }
    cout << "Yes" << endl;
    for(int i = 0; i < N; i++) cout << ans[i]+1 << ' ';
    cout << endl;
}

Measured memory_bytes: 29396
#include <stdio.h>
#include <algorithm>
using namespace std;
using ll = long long;

void solve();
int main() {
	solve();
#ifdef DBG
	while (true);
#endif
}

class STree {
private:
	constexpr static int size = 131072;
	ll data[size * 2 - 1];
public:
	STree() {
		for (int i = 0; i < size * 2 - 1; i++)
			data[i] = 0x8000000000000000ll;
	}
	void update(int i, long long x) {
		i += size - 1;
		data[i] = x;
		while (i > 0) {
			i = (i - 1) / 2;
			data[i] = max(data[i * 2 + 1], data[i * 2 + 2]);
		}
	}
	ll querry(int a, int b, int k = 0, int l = 0, int r = size) {
		if (r <= a || b <= l)
			return 0x8000000000000000ll;
		if (a <= l && r <= b) {
			return data[k];
		}
		else {
			long long vl = querry(a, b, k * 2 + 1, l, (l + r) / 2);
			long long vr = querry(a, b, k * 2 + 2, (l + r) / 2, r);
			return max(vl, vr);
		}
	}
};
void solve() {
	ll n, c, x[100002], u[100002];
	scanf("%lld %lld", &n, &c);
	for (int i = 1; i <= n; i++)
		scanf("%lld %lld", x + i, u + i);
	x[0] = 0, u[0] = 0;
	u[n + 1] = c, x[n + 1] = 0;

	ll cum_calorie;
	STree dp_r, dp_l;
	ll dp_rr[100002], dp_lr[100002];

	cum_calorie = 0;
	dp_r.update(0, 0);
	dp_rr[0] = 0;
	for (int i = 1; i <= n; i++) {
		cum_calorie += u[i];
		dp_r.update(i, cum_calorie - x[i]);
		dp_rr[i] = cum_calorie - x[i] * 2;
	}

	cum_calorie = 0;
	dp_l.update(n + 1, 0);
	dp_lr[n + 1] = 0;
	for (int i = n; 1 <= i; i--) {
		cum_calorie += u[i];
		dp_l.update(i, cum_calorie - (c - x[i]));
		dp_lr[i] = cum_calorie - (c - x[i]) * 2;
	}

	ll maxv = max(dp_r.querry(0, n + 1), dp_l.querry(1, n + 2));
	for (int r = 0; r <= n; r++)
		maxv = max(maxv, dp_rr[r] + dp_l.querry(r + 1, n + 2));
	for (int l = n + 1; 1 <= l; l--)
		maxv = max(maxv, dp_lr[l] + dp_r.querry(0, l));
	printf("%lld\n", maxv);
}

Measured memory_bytes: 7424
import numpy as np  

n, w = map(int, input().split())
dp = np.full(n*1000+1, float('inf'))
dp[0] = 0

for _ in range(n):
    weight, value = map(int, input().split())
    dp[value:] = np.minimum(dp[value:], dp[:-value] + weight) 

print(np.max(np.where(dp <= w)))



Measured memory_bytes: 14912
#include<bits/stdc++.h>
using namespace std;
long long int n,k;
vector<long long int> v;

bool checker(long long int x)
{
    vector<long long int> temp;
    long long int i;
    for(i=0;i<n;i++)
    {
        temp.push_back(v[i]%x);
    }
    sort(temp.begin(),temp.end());
    long long int l=0,r=temp.size()-1;

    long long int rem=0,req=0;

    while(l<=r)
    {
        if(rem<=0)
        {
            rem+=temp[l];
            req+=temp[l];
            l++;
        }
        else
        {
            rem-=x-temp[r];
            req+=x-temp[r];
            r--;
        }
    }

    if(rem!=0||req>2*k)
        return false;
    return true;
}

int main()
{
    cin>>n>>k;
    long long int sum=0,i;

    for(i=0;i<n;i++)
    {
        long long int y;
        cin>>y;
        v.push_back(y);
        sum+=y;
    }

    long long int ans=1;

    for(i=1;i*i<=sum;i++)
    {
        if(sum%i==0)
        {
            if(checker(i))
                ans=max(ans,i);
            if(checker(sum/i))
                ans=max(ans,sum/i);
        }
    }

    cout<<ans;
}


Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
using namespace std;
int A,N,P;
long long int x=1,y=0,z;

int main(){
 cin>>N>>P;
 for(int i=0;i<N;i++){
   cin>>A;
   if(A%2){
     z=y;
     y+=x;
     x+=z;
   }
  else{
    x*=2;
    y*=2;
  }
 }
 if(P) cout<<y<<endl;
 else cout<<x<<endl;
 return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define all(c) (c).begin(),(c).end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define TRACE
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

const ll inf = 2e18;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n;
	cin >> n;
	int a[n + 1], b[n + 1], c[n + 1];
	for(int i = 1; i <= n; i++) {
		cin >> a[i] >> b[i] >> c[i];
	}
	int dp[n + 1][3];
	dp[0][0] = dp[0][1] = dp[0][2] = 0;
	for(int i = 1; i <= n; i++) {
		dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + a[i];
		dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + b[i];
		dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + c[i];
	}
	cout << max({dp[n][0], dp[n][1], dp[n][2]});

	return 0;
}

Measured memory_bytes: 8240
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(ll i=(n)-1;i>=0;i--)
#define range(i,a,n) for(ll i=(a);i<(n);i++)
#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI (3.1415926535897932384)

int dx[]={1,0,-1,0,1,-1,-1,1},dy[]={0,1,0,-1,1,1,-1,-1};
template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S sum(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
int sgn(const double&r){return (r>EPS)-(r<-EPS);} // a>0  : sgn(a)>0
int sgn(const double&a,const double&b){return sgn(a-b);} // b<=c : sgn(b,c)<=0

template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>void tf(bool b,S t,T f){if(b)puta(t);else puta(f);}
void YN(bool b){tf(b,"YES","NO");}
void Yn(bool b){tf(b,"Yes","No");}
void yn(bool b){tf(b,"yes","no");}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1;for(auto s:t){os<<(a?"":" ")<<s;a=0;}return os;}
template<class S>auto&operator>>(istream&is,vector<S>&t){for(S&a:t)cin>>a;return is;}

/*他のライブラリを入れる場所*/


int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n;
	cin>>n;
	vl a(n);cin>>a;
	ll cnt=0,ans=0;
	rep(i,n-1){
		if(a[i]>=a[i+1]){
			cnt++;
		}else{
			chmax(ans,cnt);
			cnt=0;
		}
	}
	puta(max(ans,cnt));
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define fi			first
#define se			second
#define fz(i,a,b)	for(int i=a;i<=b;i++)
#define fd(i,a,b)	for(int i=a;i>=b;i--)
#define foreach(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define all(a)		a.begin(),a.end()
#define fill0(a)	memset(a,0,sizeof(a))
#define fill1(a)	memset(a,-1,sizeof(a))
#define fillbig(a)	memset(a,0x3f,sizeof(a))
#define fillsmall(a) memset(a,0xcf,sizeof(a))
#define y1			y1010101010101
#define y0			y0101010101010
#define int long long
typedef pair<int,int> pii;
inline int read(){
	int x=0,neg=1;char c=getchar();
	while(!isdigit(c)){
		if(c=='-')	neg=-1;
		c=getchar();
	}
	while(isdigit(c))	x=x*10+c-'0',c=getchar();
	return x*neg;
}
const int MOD=1e9+7;
int n,sum[500005];
int dp[500005],z[500005];
int s1[500005],s2[500005];
int pos[1048577],pre[500005];
signed main(){
	n=read();
	fz(i,1,n)	sum[i]=read(),sum[i]^=sum[i-1];
	fill1(pos);
//	fz(i,1,n)	printf("%lld ",sum[i]);puts("");
	z[0]=1;
	fz(i,1,n){
		if(sum[i])	z[i]=z[i-1];
		else		z[i]=z[i-1]+1;
	}
	pos[0]=0;
//	cerr<<clock()<<endl;
	fz(i,1,n){
		pre[i]=pos[sum[i]];
		pos[sum[i]]=i;
	}
	dp[0]=1;
	s1[0]=1;
	s2[0]=1;
	fz(i,1,n){
		if(pre[i]==-1){
			dp[i]=1;
			s1[i]=dp[i];
			s2[i]=dp[i]*z[i]%MOD;
		}
		else{
			int sum1=s1[pre[i]],sum2=s2[pre[i]];
			dp[i]=(z[i-1]*sum1-sum2+MOD+1)%MOD;
			s1[i]=(dp[i]+sum1)%MOD;
			s2[i]=(dp[i]*z[i]+sum2)%MOD;
		}
//		printf("%lld ",dp[i]);
	}
	if(sum[n]!=0)	printf("%lld\n",dp[n]);
	else{
		int ans=0;
		fz(i,1,n)	if(sum[i])	ans=(ans+dp[i])%MOD;
		ans=(ans+dp[n])%MOD;
		printf("%lld\n",ans);
	}
	return 0;
}
/*
2 0 0 2 2 0 2 0 0 0 2
dp[i]=sigma dp[j]*(z[i-1]-z[j]) (a[j]=a[i])
dp[i]=sigma dp[j]*z[i-1]-dp[j]*z[j]

1 3 0

24
1 2 5 3 3 6 1 1 8 8 0 3 3 4 6 6 4 0 7 2 5 4 6 2

7
1 2 3 4 5 6 7

8
1 2 3 0 4 5 6 7

10
1 4 3 6 0 7 7 5 3 6
*/

Measured memory_bytes: 35364
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define REP(i, b, n) for (Int i = b; i < Int(n); i++)
#define rep(i, n) REP(i, 0, n)
using namespace std;
using Int = long long;
Int inf = 1000000000000000001LL;
using vi = vector<Int>;
using vvi = vector<vi>;

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

int main() {
    int N,T,A;

    cin >>N>>T>>A;
    Int ans =inf;
    vi H = vi(N);
    rep(i,N){
        cin >> H[i];
    }
    Int minT = inf;

    rep(i,N){
        Int tmp = T*1000-H[i]*6;
        Int now_diff = abs(A*1000-tmp);
        if(minT>now_diff){
            ans = i+1;
        }
        minT = min(minT,abs(A*1000-tmp)) ;
    }


    cout << ans;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <string>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <vector>
using namespace std;

#define Nmax 3003
#define modulo 998244353

int N, S;
int A[Nmax], cnt[Nmax][Nmax];

int main() {
    cin >> N >> S;
    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
    }
    
    int total = 0;
    for (int i = 1; i <= N; ++i) {
        cnt[i-1][0] = i;
        for (int j = 1; j < A[i]; ++j)
            cnt[i][j] = cnt[i-1][j];
        for (int j = A[i]; j <= S; ++j) {
            cnt[i][j] = ((long long)cnt[i-1][j] + cnt[i-1][j - A[i]]) % modulo;
        }
        total += cnt[i][S];
        total %= modulo;
    }
    
    cout << total;
    
    return 0;
}



Measured memory_bytes: 35456
///Astalavista Code........~CodeSlayer007
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define Br cout<<endl;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define int long long
#define double long double
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define PT(x) cout << (#x) << " is " << (x) << endl;
#define SPD_emergency ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
const int M = 1e9 + 7;
int IM = 1e17;
void PV(vi v) { for (int i = 0 ; i < v.size() ; i++) cout << v[i] << " "; cout << endl;}
void PA(int v[], int n) {for (int i = 0 ; i < n ; i++)cout << v[i] << " " ; cout << endl;}
void IN(int a[], int n) {for (int i = 0; i < n; i++)cin >> a[i];}
inline void PTN(int n = 1, int a = 0, int b = 0, int c = 0) { if (n--)cout << a << " "; if (n--)cout << b << " "; if (n--)cout << c << " "; cout << endl; }
inline void open() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}
// <-------------------------------------------------------------------------------------------------------------------------------------------------------------------------> Ignore This--> insert tuple first second push_back string continue make_pair break deque stack queue sort reverse accumulate  count lower_bound upper_bound next_permutation copy_n __builtin_popcount make_tuple
// <========================================================================================================================================================================

signed  main() {
    SPD_emergency

    // int t; cin >> t; int tt = 1; while (t--)
    {
        int n, m;
        cin >> n >> m;
        int a[n + 10];
        IN(a, n);
        vi v(n, 1);
        int i, j, k , l;
        while (m--) {
            cin >> i >> j;
            if (a[i-1] > a[j-1])
                v[j-1] = 0;
            else
                v[i-1] = 0;
            if( a[i-1] == a[j-1] )
                v[i-1] = v[j-1] =0;
        }
        int ans = 0;
        for (auto i : v) {
            ans += i;
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 4784
a = [int(x) for x in input().split()]
s = 0
if a[0] <= a[1]:
    s = a[0]
    if a[1] <= a[2]:
        s += a[1]
    else:
        s += a[2]
else:
    s = a[1]
    if a[0] <= a[2]:
        s += a[0]
    else:
        s += a[2]
print(s)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
typedef pair<ll,ll> P;
#define Mod 1000000007
using VP = vector<P>; using VVP = vector<VP>;
using VI = vector<ll>; using VVI = vector<VI>; using VVVI = vector<VVI>;
#define INF 1234567890


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

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

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
const int N = 1e6 + 1000;
int n,a[N],sum[N],s[2];
int check(int x)
{
	int k = 0;
	for(int i = 2;i <= n;i += 2)
		if(sum[i - 1] - k >= x) k = min(sum[i],k); 
	return sum[n] - k >= x;
}
signed main()
{
	n = read();
	for(int i = 1;i <= n;i ++) s[i & 1] += (a[i] = read());
	if((n & 1) == 0) {cout << max(s[0],s[1]) << " " << min(s[0],s[1]); return 0;}
	else
	{
		for(int i = 1;i <= n;i ++) sum[i] = sum[i - 1] + (i & 1 ? a[i] : -a[i]);
		int l = 0,r = s[0] + s[1],mid,ans = 0;
		while(l <= r)
		{
			mid = (l + r) >> 1;
			if(check(mid)) {ans = mid; l = mid + 1;}
			else r = mid - 1;
		}
		cout << s[0] + ans << " " << s[1] - ans;
	}
}

Measured memory_bytes: 8448
using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Linq;
using System.Numerics;

namespace AtCoderWorkspace
{
    public class Solver
    {
        public void Solve()
        {
            var cin = new Scanner();
            var a = cin.ArrayInt(3);
            var ans = 0;
            for (int i = a[0]; i <=a[1]; i++)
            {
                if (i % a[2] == 0) ans++;
            }
            Console.WriteLine(ans);
        }
    }

    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 int[] DPArrayInt(int N, int ex)
        {
            int[] Array = new int[N + ex];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextInt();
            }
            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 long[] DPArrayLong(int N, int ex)
        {
            long[] Array = new long[N + ex];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextLong();
            }
            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;
        }
    }

    class Program
    {
        static void Main(string[] s) => new Solver().Solve();
    }
}


Measured memory_bytes: 27536
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 0x3f3f3f3f;
const ll maxn= 1e5+10;
int main(){
	ll a,b,c,d;
	cin>>a>>b>>c>>d;
	if(a>d){
		cout<<d<<"\n";
	}else if(a+b>d){
		cout<<a<<"\n";
	}else{
		cout<<a-(d-a-b)<<"\n";
	} 


	return 0;
}


Measured memory_bytes: 3608
n = int(input())
r = []
if n%2==0:
    c = 1
else: 
    c = 0
for i in range(1, n+1):
    for j in range(i+1, n+1):
        if n-i+c == j:
            continue
        else:
            r.append([i, j])
print(len(r))
for i in r:
    print(*i)

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

int main() {
    stack<ll> s;
    char input[100];
    while( scanf("%s", input) != EOF) {
        ll s1, s2;
        switch( input[0] ) {
            case '+': 
                s1 = s.top();s.pop();
                s2 = s.top();s.pop();
                s.push(s1+s2);
                break;
            case '-': 
                s1 = s.top();s.pop();
                s2 = s.top();s.pop();
                s.push(s2-s1);
                break;
            case '*': 
                s1 = s.top();s.pop();
                s2 = s.top();s.pop();
                s.push(s1*s2);
                break;
            default:
                s.push(atoi(input));
                break;
        }
    }

    cout << s.top() << endl;
    return 0;
}



Measured memory_bytes: 3264
n,m,q= map(int,input().split())
dataList = [[0 for xIndex in range(n+1)]for yIndex in range(n+1)]

for i in range(m):
    xTemp,yTemp = map(int,input().split())
    dataList[yTemp][xTemp]+=1
pqList=[list(map(lambda x:int(x),input().split()))for i in range(q)]
for yIndex in range(1,n+1):
    for xIndex in range(1,n+1):
        dataList[yIndex][xIndex]+=dataList[yIndex][xIndex-1]
for yIndex in range(1,n+1):
    for xIndex in range(1,n+1):
        dataList[yIndex][xIndex]+=dataList[yIndex-1][xIndex]

for pq in pqList:
    p = pq[0]-1
    q = pq[1]
    print(dataList[q][q]+dataList[p][p]-dataList[p][q]-dataList[q][p])

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

from collections import deque
w=[0]*n
for i in range(1,n):
    if s[i-1]=='W':
        w[i]=w[i-1]+1
    else:
        w[i]=w[i-1]
e=[0]*n

for j in range(n-2,-1,-1):
    if s[j+1]=='E':
        e[j]=e[j+1]+1
    else:
        e[j]=e[j+1]

ans=10**9

for k in range(n):
    ans =min(ans,e[k]+w[k])

print(ans)

Measured memory_bytes: 17864
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		int Inf = (int)1e9;
		int Tot = 4000;
		int ofs = Tot/2;	// ± Tot/2 くらいに収まる
		
		int[][] dp = new int[N][];
		for(int i=0;i<N;i++){
			dp[i] = new int[Tot];
			for(int j=0;j<Tot;j++){
				dp[i][j] = Inf;
			}
		}
		
		// Ma * b - Mb * a を キーにdpする．加法的．
		
		
		for(int i=0;i<N;i++){
			int key = Ma * B[i] - Mb * A[i];
			dp[i][key + ofs] = Math.Min(dp[i][key + ofs],C[i]);
			if(i > 0){
				for(int j=0;j<Tot;j++){
					if(dp[i-1][j] == Inf) continue;
					dp[i][j] = Math.Min(dp[i][j],dp[i-1][j]);
					int pre = j - ofs;
					dp[i][(pre + key) + ofs] = Math.Min(dp[i][(pre + key) + ofs],dp[i-1][j]+C[i]);
				}
			}
		}
		
		Console.WriteLine(dp[N-1][0 + ofs] == Inf ? -1 : dp[N-1][0 + ofs]);
	}
	
	
	int N,Ma,Mb;
	int[] A,B,C;
	public Sol(){
		var d = ria();
		N = d[0]; Ma = d[1]; Mb = d[2];
		A = new int[N];
		B = new int[N];
		C = new int[N];
		for(int i=0;i<N;i++){
			d = ria();
			A[i] = d[0]; B[i] = d[1]; C[i] = d[2];
		}
		
		
	}

	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}


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

#define int long long

#define ii pair<int,int>
#define fi first
#define sc second

#define all(x) (x).begin(),(x).end()

int mypow(int a, int b) {
  if (b == 0) return 1;
  if (b % 2) return a * mypow(a, b / 2) * mypow(a, b / 2);
  return mypow(a, b / 2) * mypow(a, b / 2);
}

signed main() {
#ifdef _DEBUG
  // freopen("in" , "r", stdin );
  // freopen("out", "w", stdout);
#endif
  // ios::sync_with_stdio(0); cin.tie(0);
  int n;
  cin >> n;
  int ans = 1;
  for (int i = 2; i * i <= n; i++) {
    int t = i * i;
    while (t * i <= n) t *= i;
    ans = max(ans, t);
  }
  cout << ans << '\n';
}


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

int main() {
    int D,G;
    cin >> D >> G;
    int p[110];
    int c[110];
    for(int i=0; i<D; i++) cin >> p[i] >> c[i];
    int ans,a,b,tmp;
    ans=1100;
    for(int i=0; i<(1<<D); ++i){
        a=b=tmp=0;
        for(int j=0; j<D; ++j){
            if ((i>>j)%2==1){
                tmp+=p[j]*(j+1)*100+c[j];
                a+=p[j];
            }
            else{
                b=j;
            }
        }
        if(G<=tmp+(p[b]-1)*(b+1)*100){
            a+=(max(G-tmp,0)+((b+1)*100-1))/((b+1)*100);
            ans=min(ans,a);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define all(x) (x).begin(), (x).end()
#define PI 3.14159265358979323846264338327950L
using namespace std;
typedef long long ll;
typedef long double ld;
int main() {
    ll x;
    cin>>x;
    ll time=0,sum=0;
    while(sum<x){
        sum+=time+1;
        time++;
    }
    cout<<time;
}

Measured memory_bytes: 3580
# include <bits/stdc++.h>
# define rep(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
# define reps(i, n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
# define rrep(i, n) for(int i=((int)(n)-1); i>=0; --i)
# define rreps(i, n) for(int i=((int)(n)); i>0; --i)
# define range_for(i, b, e) for(int i=(b), i##_len=(e); i<=i##_len; ++i)
# define ALL(x) (x).begin(), (x).end()
# define RALL(x) (x).rbegin(), (x).rend()
# define pb push_back
# define len(x) ((int)(x).size())
# define optimize_cin() cin.tie(0); ios::sync_with_stdio(false)
# define debug(x) std::cerr<<#x<<": "<<(x)<<endl;
# define LINT_MAX (LONG_LONG_MAX)
# define cauto const auto
using namespace std;
using lint = long long;
template <class Type> inline constexpr bool InRange(const Type& x, const Type& i, const Type& a) { return (i <= x) && (x <= a); }
template<class Integer>bool chmax(Integer &a, const Integer &b) { if (a<b) { a=b; return 1; } return 0; }
template<class Integer>bool chmin(Integer &a, const Integer &b) { if (b<a) { a=b; return 1; } return 0; }
template<class Integer>bool IsOdd(Integer &n) { return n & 1; }
template<class Integer>bool IsEven(Integer &n) { return !(n & 1); }
int ctoi(const char c) { return ('0' <= c && c <= '9') ? (c - '0') : -1; }
string YesNo(bool b) { return b ? "Yes" : "No"; }
string YESNO(bool b) { return b ? "YES" : "NO"; }
string yesno(bool b) { return b ? "yes" : "no"; }
static const lint MOD9 = (lint)1e9+7;
int dy[4] = {0, 1, 0, -1};
int dx[4] = {1, 0, -1, 0};

// 整数の桁数を返す ( log(N) )
template <class Integer> Integer GetDigit(Integer n) {
    Integer d = 0;
    while (n) {
        n /= 10;
        d++;
    }
    return d;
}

// 素数かどうかを返す ( O(sqrt(N)) )
template <class Integer>
constexpr bool IsPrime(const Integer n) noexcept {
    if (n < 4) return n == 2 || n == 3;
    if (n % 2 == 0 || n % 3 == 0 || (n % 6 != 1 && n % 6 != 5)) return false;
    for (Integer i = 5; i * i <= n; i += 6) if (n % i == 0 || n % (i + 2) == 0) return false;
    return true;
}


int main()
{
    lint N; cin >> N;
    string S; cin >> S;
    map<char, lint> sum;
    sum['R'] = count(ALL(S), 'R');
    sum['G'] = count(ALL(S), 'G');
    sum['B'] = count(ALL(S), 'B');

    lint ans = 0;
    rep (i, N-2)
    {
        if (S[i] == 'R') {
            ans += sum['G'] * sum['B'];
            sum['R']--;
        }
        else if (S[i] == 'G')
        {
            ans += sum['R'] * sum['B'];
            sum['G']--;
        }
        else if (S[i] == 'B') {
            ans += sum['R'] * sum['G'];
            sum['B']--;
        }
    }

    for (int i = 0; i < N - 2; ++i)
    {
        for (int k = 1; i+2*k < N; ++k)
        {
            if (S[i] != S[i+k] and S[i] != S[i+2*k] and S[i+k] != S[i+2*k])
            {
                ans--;
            }
        }
    }

    cout << ans << endl;

    return 0;
}


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

using namespace std;
using ll = long long;

struct UnionFind {
	private:
		vector<int> uf;
		size_t sz;

	public:
		UnionFind(size_t Size) {
			uf.assign(Size, -1);
			sz = Size;
		}

		int find(int x) { return (uf[x] < 0) ? x : uf[x] = find(uf[x]); }
		bool same(int x, int y) { return find(x) == find(y); }
		int size(int x) { return -uf[find(x)]; }
		int size() { return sz; }

		void unite(int x, int y) {
			x = find(x), y = find(y);
			if (x == y) { return; }
			--sz;

			if (uf[y] < uf[x]) { swap(x, y); }
			uf[x] += uf[y];
			uf[y] = x;
		}
};

int main() {
	int N, M;
	cin >> N >> M;
	UnionFind uf(N);
	for (int i = 0; i < M; ++i) {
		int x, y, z;
		cin >> x >> y >> z;
		uf.unite(x - 1, y - 1);
	}

	cout << uf.size() << endl;

	return 0;
}


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

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

    vector<int> p(n);
    for (int i = 0; i < n; i++)
        cin >> p[i];
    sort(p.begin(), p.end());

    int ans = 0;
    for (int i = 0; i < k; i++)
        ans += p[i];

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

Measured memory_bytes: 3588
# a1をきめればc11-a1, c12-a1, c13-a1からそれぞれb1, b2, b3が決まる
# b1, b2, b3が決まっているのでc21-b1, c22-b2, c23-b3からa2が判定できる
# 同じくa3もc31-b1, c32-b2, c33-b3から判定できる

grid = Array.new(3)
3.times do |i|
    grid[i] = gets.split.map(&:to_i)
end
flag = false
# とりうる値は0-100
0.upto(100) do |a1|
    b1, b2, b3 = grid[0][0]-a1, grid[0][1]-a1, grid[0][2]-a1
    # よくみたら問題文にa>=0, b>=0とかいう条件がない。。。
    if [b1, b2, b3].any?{|b| b<0} then
        next
    end
    if grid[1][0]-b1==grid[1][1]-b2 && grid[1][1]-b2==grid[1][2]-b3 && \
        grid[2][0]-b1==grid[2][1]-b2 && grid[2][1]-b2==grid[2][2]-b3 then
        flag = true
        break
    end
end

puts flag ? 'Yes' : 'No'

Measured memory_bytes: 1788