akhauriyash/Code-Regression huggingface dataset:
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
M = 998244353


class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res


def segfunc(x, y):
    return x + y


def main():
    N, K = map(int, readline().split())
    LR = list(list(map(int, readline().split())) for _ in range(K))
    LR.sort()

    A = [0] * (N + 1)
    A[1] = 1
    seg = SegTree(A, segfunc=segfunc, ide_ele=0)
    for i in range(2, N + 1):
        for l, r in LR:
            if i - l > 0:
                total = (seg.tree[i + seg.num] + seg.query(max(1, i - r), min(N, i - l + 1)) % M)
                seg.update(i, total)
            else:
                break
    print(seg.tree[seg.num + N] % M)


if __name__ == '__main__':
    main()


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

// #define int long long
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++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 irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

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

char G[105][105];

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  ll h,w; cin>>h>>w;
  rep(i,h) rep(j,w) cin>>G[i][j];
  
  bool ok=true;
  map<char,ll> m;
  rep(i,h){
    rep(j,w){
      m[G[i][j]]++;
    }
  }
  ll ki=0;
  ll yo=0;
  ll ni=0;
  for(auto e: m){
    if(e.second%2){
      ki++;
      m[e.first]--;
    }
    if(e.second%4==0) yo++;
    else if(e.second%2==0) ni++;
  }
  if(ki>1 || h%2==0&&w%2==0&&ki>0){
    cout<<"No"<<endl;
    return 0;
  }
  ll cnt=(h%2)*w+(w%2)*h;
  if(h==1 or w==1) cnt--;
  ll x=ki+2*ni;
  if(cnt>=x) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
constexpr int M = 1000000007;

int main() {
    int n; cin >> n;
    long long C[n];
    long long pl[n+1], pr[n+2], g[n+1], c[n+1];
    pl[0] = 1; pr[n+1] = 1;
    for (int i = 1; i <= n; i++) pl[i] = pl[i-1] * i % M;
    for (int i = n; i > 0; i--) pr[i] = pr[i+1] * i % M;
    for (int i = 1; i <= n; i++) g[i] = pl[i-1] * pr[i+1] % M;
    c[1] = 0;
    for (int i = 1; i <= n; i++) c[1] += g[i];
    c[1] %= M;
    for (int i = 2; i <= n; i++) c[i] = (c[i-1] + g[i] - g[n-i+2]) % M;
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
      long long a; cin >> a;
      ans += a * c[i] % M;
    }
    cout << (ans % M + M) % M << endl;
}


Measured memory_bytes: 3328
#include<stdio.h>
int main(void)
{
	while(1){
	int a,b=0,c=0,d=0,e=0,f=0,g=0,h,i;
	scanf("%d",&a);
	if(a==0)break;
	a=1000-a;
	if(a/500>=1){
		b=a/500;
		a%=500;
	}
		if(a/100>=1){
		c=a/100;
		a%=100;
		}
		if(a/50>=1){
		d=a/50;
		a%=50;
		}
		if(a/10>=1){
		e=a/10;
		a%=10;
		}
		if(a/5>=1){
		f=a/5;
		a%=5;
		}
		g=a/1;
		h=b+c+d+e+f+g;
	printf("%d\n",h);
	}
	return 0;
}


Measured memory_bytes: 2048
#include <bits/stdc++.h>
#define INF 1e18
#define int long long
#define Rep(i, a, n) for (int i = (a); i < (n); i++)
#define Repr(i, n, a) for (int i = (n); i >= (a); i--)
#define rep(i, n) Rep(i, 0, n)
#define repr(i, n) Repr(i, n, 0)
#define all(a) a.begin(), a.end()
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int mod = 1000000007;

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

    int n;
    cin >> n;
    vector<int> b(n);
    rep(i, n) cin >> b[i];
    vector<int> a(n);
    rep(i, n)
    {
        int cnt = 0, pos = -1;
        rep(j, n)
        {
            if (b[j] == 0)
                continue;
            cnt++;
            if (cnt == b[j])
                pos = j;
        }
        if (pos == -1)
        {
            cout << -1 << endl;
            return 0;
        }
        a[n - i - 1] = b[pos];
        b[pos] = 0;
    }
    rep(i, n) cout << a[i] << endl;
}

Measured memory_bytes: 256
#include <iostream>

#define MAX_H 64
#define MAX_W 64

using namespace std;

int main()
{
    int h, w;
    cin >> h >> w;
    char grid[MAX_H][MAX_W];
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> grid[i][j];
        }
    }

    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (grid[i][j] == '#') continue;
            int count = 0;
            for (int dy = -1; dy <= 1; dy++) {
                for (int dx = -1; dx <= 1; dx++) {
                    if (0 <= i+dy && i+dy <= h && 0 <= j+dx && j+dx <= w && grid[i+dy][j+dx]=='#') count++;
                }
            }
            grid[i][j] = (char)(count + '0');
        }
    }

    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) cout << grid[i][j];
        cout << endl;
    }
}

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

int main(){
    int n;
    cin >> n;
    int c[100][100];
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> c[i][j];
        }
    }
    long long int ans = 0;
    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            ans += min(c[i][j], c[j][i]);
        }
    }
    cout << ans << endl;
    return 0;
}

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

#define MIN_L -9223372036854775800

int main()
{
  int D;
  cin >> D;
  vector<long> C(26);
  for (int i = 0; i < 26; i++) cin >> C.at(i);
  vector<vector<long> > S(D, vector<long>(26));
  for (int i = 0; i < D; i++)
  {
    for (int j = 0; j < 26; j++) cin >> S.at(i).at(j);
  }
  long score_now = 0;
  vector<int> last(26, -1);
  int ans = 0;
  for (int i = 0; i < D; i++)
  {
    long max_sat = MIN_L;
    for (int j = 0; j < 26; j++)
    {
      long tmp = 0;
      for (int k = 0; k < 26; k++)
      {
        if (j == k) tmp += S.at(i).at(k);
        else tmp -= C.at(j) * (i - last.at(k));
      }
      if (max_sat < tmp)
      {
        max_sat = tmp;
        ans = j+1;
      }
    }
    cout << ans << endl;
  }
}


Measured memory_bytes: 3716
import sys
n, m, k = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))

a, b = [0], [0]
for i in range(n):
  a.append(a[i] + A[i])
for i in range(m):
  b.append(b[i] + B[i])

ans = 0
j = m
for i in range(n + 1):
  if a[i] > k:
    break
  while a[i] + b[j] > k:
      j -= 1
  ans = max(ans, i + j)
    
print(ans)

Measured memory_bytes: 47140
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,pii> piii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define mp make_pair
#define pb push_back
#define INF 1000000001
#define MAX_V 100000

struct st{int time,to;};
vector<st> G[MAX_V];

int main(){
	int n,m;
	cin>>n>>m;
	rep(i,m){
		int a,b,c;
		cin>>a>>b>>c;
		a--,b--;
		G[a].pb(st{c,b});
	}
	
	priority_queue<piii,vector<piii>,greater<piii> > pq;
	for(auto & edge:G[0]) pq.push(mp( edge.time,mp(0,edge.to) ));
	
	int d[MAX_V];
	rep(i,MAX_V)d[i] = INF;
	d[0]=0;
	
	while( pq.size() ){
		piii edge = pq.top();
		int time = edge.first, from = edge.second.first, to = edge.second.second;
		pq.pop();
		
		if( d[from]>time )continue;
		
		if(d[to] == INF){
			for( auto &edge : G[to] ){
				pq.push(mp( edge.time,mp(to,edge.to) ));
			}
		}
		
		if(d[to]>time) d[to] = time;
	}

	
	int ans = -1;
	rep(i,n){
		for(auto &edge:G[i]){
			if( edge.to==n-1 && d[i]<=edge.time ){
				ans = max(edge.time,ans);
			}
		}
	}
	cout<<ans<<endl;

}

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

#define int long long

using namespace std;

#ifdef LOCAL 
#include "/media/brayand/7801-B00D/debugger.h"
#else
template<typename... Args>
void db(Args... args){}
#endif

const int MOD = 1e9+7;

const int BAS = 331;

string A[30];
string rA[30];
string B[30];

const int MAXN = 2e5+100;

int mp[MAXN];
int val[MAXN];

int P[MAXN];

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

    P[0] = 1;
    for(int i = 1 ; i < MAXN ; i++)P[i] = P[i-1]*BAS%MOD;

    int N;
    cin >> N;

    for(int i = 0 ; i < N ; i++)
    {
    	int n;
    	cin >> n;
    	for(int j = 0 ; j < 30 ; j++)
    	{
    		if(n&(1<<j))A[j] += "1", rA[j] += "0";
    		else A[j] += "0", rA[j] += "1";
    	}
    }

    for(int i = 0 ; i < N ; i++)
    {
    	int n;
    	cin >> n;
    	for(int j = 0 ; j < 30 ; j++)
    	{
    		if(n&(1<<j))B[j] += "1";
    		else B[j] += "0";
    	}
    }

    for(int i = 0 ; i < 30 ; i++)
    {
    	A[i] = A[i]+A[i];
    	rA[i] = rA[i]+rA[i];
    }

    vector<pair<int,int>> res[30];

    for(int i = 0 ; i < 30 ; i++)
    {
    	int ha1[A[i].size()+1];
    	int ha2[rA[i].size()+1];
    	int hhh = 0;

    	ha1[0] = 1;
    	ha2[0] = 1;

    	for(int x = 0 ; x < A[i].size() ; x++)
    	{
    		ha1[x+1] = (ha1[x]*BAS+A[i][x])%MOD;
    	}

    	for(int x = 0 ; x < rA[i].size() ; x++)
    	{
    		ha2[x+1] = (ha2[x]*BAS+rA[i][x])%MOD;
    	}

    	for(int x = 0 ; x < B[i].size() ; x++)
    	{
    		hhh = (hhh*BAS+B[i][x])%MOD;
    	}

    	for(int x = 0 ; x < N ; x++)
    	{
    		if((ha1[x+N]+MOD-ha1[x]*P[N]%MOD)%MOD == hhh)
    		{
    			res[i].push_back({x,0});
    		}
    	}

    	for(int x = 0 ; x < N ; x++)
    	{
    		if((ha2[x+N]+MOD-ha2[x]*P[N]%MOD)%MOD == hhh)
    		{
    			res[i].push_back({x,1});
    		}
    	}

    }

    for(int i = 0 ; i < 30 ; i++)
    {
    	for(auto x : res[i])
    	{
    		mp[x.first]++;
    		val[x.first] += (x.second)*(1ll<<i);
    	}
    }

    for(int i = 0 ; i < N ; i++)
    {
    	if(mp[i] == 30)
    	{
    		cout << i << " " << val[i] << '\n';
    	}
    }

    return 0;
}

Measured memory_bytes: 156436
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
char s[100];
int main(void)
{
     scanf("%s",s);
     int i,j,k,l,n,m;
     l=strlen(s);
     for(i=0;i<l-8;i++)
          printf("%c",s[i]);
     return 0;
}


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

int	str_to_time(const string &time_str)
{
	int	hour, minute, second, time;
	hour = stoi(time_str.substr(0, 2));
	minute = stoi(time_str.substr(3, 2));
	second = stoi(time_str.substr(6, 2));
	time = hour * 3600 + minute * 60 + second;
	return time;
}

int	main()
{
	int	n;
	while (cin >> n) {
		if (n == 0) break;
		string	bgn, end;
		vector<int>	diff(24 * 3600, 0);
		for (int i = 0; i < n; ++i) {
			cin >> bgn >> end;
			diff.at(str_to_time(bgn)) += 1;
			diff.at(str_to_time(end)) -= 1;
		}
		vector<int>	cnt_vec(24 * 3600, 0);
		cnt_vec.at(0) = diff.at(0);
		for (int i = 1; i < 24 * 3600; ++i)
			cnt_vec.at(i) = cnt_vec.at(i - 1) + diff.at(i);
		cout << *max_element(cnt_vec.begin(), cnt_vec.end()) << endl;
	}
}



			




Measured memory_bytes: 3844
n  = int(input())
a = []
total = 0
for _ in range(n):
    a.append(input().strip().split())
for i in range(n):
    b = a[i]
    price = float(b[0])
    name = str(b[1])
    if name == "JPY":
        total += price
    else:
        total += price * 380000
print(total)

Measured memory_bytes: 3060
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    a,op,b=input().split()
    if op=="+":
        print(int(a)+int(b))
    else:
        print(int(a)-int(b))

main()


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

static const int N = 1000;

int main(){
    int n,commandNum,a[N],b,e,k,cnt;
    cin >> n;
    for(int i = 0;i < n;++i){
        cin >> a[i];
    }
    cin >> commandNum;
    
    for(int i = 0;i < commandNum;++i){
        cin >> b >> e >> k;
        cnt = 0;
        for(int i = b;i < e;++i){
            if(a[i] == k){
                cnt++;
            }
        }
        cout << cnt << endl;
    }
}



Measured memory_bytes: 3120
n = gets.to_i
a = gets.split.map(&:to_i)
b = gets.split.map(&:to_i)
c = gets.split.map(&:to_i)

sum = b.inject(:+)

for i in 0...n-1
  if a[i] == a[i+1] - 1
    sum += c[a[i]-1]
  end
end
puts sum

Measured memory_bytes: 1788
#include <iostream>
#include <vector>

using namespace std;

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

	vector<unsigned long long int> V(N+1);
	V.at(0) = 2;
	V.at(1) = 1;


	for (int i = 2; i <= N; i++) 
	{
		V.at(i) = V.at(i - 1) + V.at(i - 2);
	}

	cout << V.at(N) << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define LL long long
#define endl '\n'
using namespace std;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    while(cin >> n, n) {
        double s[1000];
        double ave = 0;
        for (int i = 0; i < n; i++) {
            cin >> s[i];
            ave += s[i];
        }
        ave /= n;
        double std = 0;
        for (int i = 0; i < n; i++) {
            std += pow((s[i] - ave), 2);
        }
        std = sqrt(std / n);
        printf("%lf\n", std);
    }
    return 0;
}


Measured memory_bytes: 3196
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>

#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; ++i)
#define repp(i, m, n) for(ll i = m, i##_len = (n); i < i##_len; ++i)
#define all(x) (x).begin(), (x).end()
#define clr(ar, val) memset(ar, val, sizeof(ar))
template <class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
template <class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int,int> P;
typedef long double ld;

int main(void)
{
	int n;
	string s;
	cin >> n >> s;
	int ans = 1;
	repp(i, 1, n) if (s[i] != s[i - 1]) ans++;
  cout << ans << endl;
	return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
const ll mod=1000000007;
const int MAX_N = 1000;         // n の最大値
 
// nCk を取得
double nCk(int n, int k) {
double res=1.0;
for(int i=0; i<n; i++){
res*=0.5;}
for(int i=0; i<k; i++){
res*=(double)(n-i);
res/=(double)(k-i);
}
return res;}
 
int main() {
ll n;
cin>>n;
ll k=1;
ll a = n;
while(a>0){
a -= pow(26,k);
k++;}
k--;
a = n;
for(ll i=0; i<k-1; i++){
a -= pow(26,i+1);}
ll ab[10000000]={};
ll i=0;
a--;
while(a>0){
ab[i]=a%26;
a=a/26;
i++;}
char aa;
for(ll j=k-1; j>=0; j--){
aa='a'+ab[j];
cout<<aa;}}


Measured memory_bytes: 82188
#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 <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cmath>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> b(n);
    for (int i = 0; i < n-1; i++) {
        cin >> b[i];
    }
    b[n-1] = b[n-2];
    int ans = b[0];
    for (int i = 0; i < n-1; i++) {
        ans += min(b[i],b[i+1]);
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
n = int(input())
L = [list(map(int, input().split())) for _ in range(n)]
cnt = 0
for i in range(n):
    if (cnt + L[n-i-1][0]) % L[n-i-1][1]:
        cnt += L[n-i-1][1] - (cnt + L[n-i-1][0]) % L[n-i-1][1]
print(cnt)


Measured memory_bytes: 27380
import sys

N, M = map(int, sys.stdin.readline().strip().split())

paths = []
count = {}
for _ in range(M):
    a, b = map(int, sys.stdin.readline().strip().split())
    paths.append((a, b))

    if a not in count:
        count[a] = 0
    if b not in count:
        count[b] = 0
    count[a] += 1
    count[b] += 1

for key, c in count.items():
    if c % 2 != 0:
        print("NO")
        break
else:
    print("YES")

Measured memory_bytes: 57436
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
using namespace std;
 
#ifdef LOCAL
	#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
	#define eprintf(...) 42
#endif
 
typedef long long ll;
typedef pair<int, int> pii;
#define mp make_pair
 
const int C = 100010;
const int N = 200200;
ll a[N], b[N];
 
int main()
{
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
 
	int n;
	scanf("%d", &n);
	a[C]++;
	b[C]++;
	while(n--) {
		int l, r;
		scanf("%d%d", &l, &r);
		l += C;
		r += C;
		a[l]++;
		b[r]++;
	}
	for (int i = N - 2; i >= 0; i--)
		a[i] += a[i + 1];
	for (int i = 1; i < N; i++)
		b[i] += b[i - 1];
	ll ans = 0;
	for (int i = 0; i < N - 1; i++)
		ans += min(b[i], a[i + 1]);
	printf("%lld\n", ans * 2);
 
	return 0;
}

Measured memory_bytes: 3328
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <cstring>
#include <map>

using namespace std;

typedef pair<int, int> P;

struct UF {
	int n;
	vector<int>d;
	UF() {}
	UF(int n) :n(n), d(n, -1) {}

	int root(int v) {
		if (d[v] < 0) { return v; }
		return d[v] = root(d[v]);
	}
	bool unite(int x, int y) {
		x = root(x);
		y = root(y);
		if (x == y) { return false; }
		if (size(x) < size(y)) { swap(x, y); }
		d[x] += d[y];
		d[y] = x;
		return true;
	}
	int size(int v) { return -d[root(v)]; }
};
int p[100005];
int q[100005];
int r[100005];
int s[100005];

map<int, pair<int, int> >mp1;
map<pair<int, int>, int>mp2;

int main() {

	int N, K, L;

	scanf("%d %d %d",&N,&K,&L);

	UF bus(200005);
	UF train(200005);

	int i;

	for (i = 0; i < K; i++) {
		scanf("%d %d",&p[i],&q[i]);
		bus.unite(p[i], q[i]);
	}
	for (i = 0; i < L; i++) {
		scanf("%d %d", &r[i], &s[i]);
		train.unite(r[i],s[i]);
	}

	for (i = 1; i <= N; i++) {
		int a = bus.root(i);
		int b = train.root(i);
		mp1[i] = make_pair(a,b);
		mp2[make_pair(a, b)]++;
	}
	for (i = 1; i < N; i++) {
		cout << mp2[mp1[i]] << " ";
	}
	cout << mp2[mp1[N]] << endl;

	return 0;
}

Measured memory_bytes: 27136
def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a
n,k=map(int,input().split())
t=list(map(int,input().split()))
m=max(t)
ans=t[0]
for i in t:
    ans=gcd(ans,i)
if k<=m and k%ans==0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
    

Measured memory_bytes: 14224
n, q = gets.chomp.split.map(&:to_i)
queue = []
n.times do
    tmpArr = gets.chomp.split
    tmpArr[1] = tmpArr[1].to_i
    queue.push(tmpArr)
end

ans = []
t = 0
until queue.empty? do
    work = queue.shift
    if work[1] <= q then
        work[1] +=  t
        ans.push(work)
        t += work[1] - t
    else
        work[1] -= q
        queue.push(work)
        t += q
    end
end

ans.each { |e| puts e.join(' ') }


Measured memory_bytes: 15388
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using int64 = int64_t;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)

void fastin(int64 &num) {
  bool negative = false;
  int64 c;
  num = 0;
  c = getchar_unlocked();
  if (c == '-') {
    negative = true;
    c = getchar_unlocked();
  }
  for (; (c > 47 && c < 58); c = getchar_unlocked()) num = (num << 3) + (num << 1) + c - 48;
  if (negative) num *= -1;
}

void fastout(int64 &n) {
  int64 N = n, rev, count = 0;
  rev = N;
  if (N == 0) { 
    putchar_unlocked('0');
    putchar_unlocked('\n');
    return;
  }
  while ((rev % 10) == 0) { 
    ++count; rev /= 10;
  }
  rev = 0;
  while (N != 0) { 
    rev = (rev << 3) + (rev << 1) + N % 10;
    N /= 10;
  }
  while (rev != 0) { 
    putchar_unlocked(rev % 10 + '0');
    rev /= 10;
  }
  while (count--) putchar_unlocked('0');
  putchar_unlocked('\n');
}

int main(){
    int64 n, m; fastin(n); fastin(m);
    int64 x[m];
    rep(i, m) fastin(x[i]);

    sort(x, x + m);

    int64 diff[m - 1];
    rep(i, m - 1){
        diff[i] = x[i + 1] - x[i];
    }

    sort(diff, diff + m - 1);

    int64 ans = 0;
    int range = m - n;
    for (int i = 0; i < range; ++i){
        ans += diff[i];
    }

    fastout(ans);
    
    return 0;
}


Measured memory_bytes: 1792
# ABC061D - Score Attack
import sys
input = sys.stdin.readline

def bellman_ford() -> int or None:
    dist = [float("inf")] * (N + 1)
    dist[1] = 0

    # relax edges
    for i in range(N):
        for v, u, w in E:  # w: positive -> -w
            if dist[v] - w < dist[u]:
                dist[u] = dist[v] - w
                if i == N - 1 and u == N:  # detect negative cycles
                    return None
    return dist[-1]


def main():
    global N, M, E
    # reverse weights -> shortest path problem containing negative cycles
    N, M = tuple(map(int, input().split()))  # vertices, edges
    E = tuple(tuple(map(int, input().split())) for _ in range(M))
    ans = bellman_ford()
    flg = ans is not None
    print(-ans if flg else "inf")


if __name__ == "__main__":
    main()

Measured memory_bytes: 3312
#include<iostream>
#include<string>
#include<string.h>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<map>
#include<cstdlib>
#include<vector>
#include<set>
#include<deque>
#include<queue>
#include<math.h>
#include<chrono>
#include<list>
#include<random>
#include<bitset>
#include<assert.h>
#include<ctime>
#include<cstdio>
#include <unordered_map>
using namespace std;
ifstream fi("input.txt");
ofstream fo("output.txt");
#define fast_input() {ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); }
#define ll long long
#define For(i,n) for (int(i) = 0; (i)<(n); (i)++)
#define For1(i,n) for (int(i) = 1; (i) <= (n); (i)++)
#define Forlr(i,l,r) for (int(i) = (l); (i) <= (r); (i)++)
#define Forrl(i,r,l) for (int(i) = (r); (i) >= (l); (i)--)
#define all(a) a.begin(), a.end() 
#define pb push_back
#define pp pop_back
#define mp make_pair
#define PI 3.14159265
#define putno return cout <<"NO", 0;
#define putyes return cout <<"YES", 0;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<ll> vl;
typedef map<int, int> mii;
//const ll MOD = 1e9 + 7;
const int N = 1e5 + 5;
//DSU
/*
int p[ N], r[N];
void init(int n) {
	For(i, n) {
		p[i] = i;
	}
}
int get(int x) {
	if (p[x] != x) {
		p[x] = get(p[x]);
	}
	return p[x];
}
bool uni(int x, int y) {
	x = get(x); y = get(y);
	if (x == y) {
		return false;
	}
	if (r[x] >= r[y]) {
		p[y] = x;
	}
	else {
		p[x] = y;
	}
	if (r[x] == r[y]) {
		r[x]++;
	}
	return true;
}
*/

// So mu
/*
int power(int x, unsigned int y, int p)
{
	int res = 1; // Initialize result

	x = x % p; // Update x if it is more than or
	// equal to p

	while (y > 0)
	{
		// If y is odd, multiply x with result
		if (y & 1)
			res = (res*x) % p;

		// y must be even now
		y = y >> 1; // y = y/2
		x = (x*x) % p;
	}
	return res;
}
*/

// ReadHexa
/*
bitset<16400> b[4101];
void readHexa()
{
	For(i, n)
	{
		string st;
		cin>> st;
		For(j, m/4)
		{
			int x;
			if (st[j] >= 'A' && st[j] <= 'F')
				x = st[j] - 'A' + 10;
			else x = st[j] - '0';
			for (int k = 4; k; --k, x >>= 1)
				b[i][j * 4 + k] = x & 1;
		}
	}
}
*/

// nChoosek
/*
ll nChoosek(ll n, ll k)
{
	if (k > n) return 0;
	if (k * 2 > n) k = n - k;
	if (k == 0) return 1;

	ll result = n;
	for (ll i = 2; i <= k; ++i) {
		result *= (n - i + 1);
		result /= i;
	}
	return result;
}
*/

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

/*
MIKUNO - 15/02/1999
*/
int n, m, k, cnt, rs1, q;
//	priority_queue <ll, vector<ll>, greater<ll> > q;
//ll n, m, q, k, pos, t, cnt, rs1, check;
ll maxx = -1e9, minn = 1e9;
const int maxn = 1005;
const ll MOD = 1e9 + 7;
int rs;
string t = "ACGT";
int ans[N];
int main()
{
	fast_input();
	string s;
	cin >> n >> q;
	cin >> s;
	For1(i, n - 1)
	{
		if (s[i] == 'C' && s[i - 1] == 'A')
		{
			ans[i]++;
		}
	}
	For1(i, n - 1)
		ans[i] += ans[i - 1];

	while (q--)
	{
		int l, r;
		cin >> l >> r;
		l--, r--;
		if (s[l] == 'C' && l > 0 && s[l - 1] == 'A')
			cout << ans[r] - ans[l - 1] - 1 << "\n";
		else
			cout << ans[r] - ans[l - 1] << "\n";
	}
}

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


void solve(LL N, LL M, LL X, vector<LL> A){
  LL c1=0, c2=0;
  LL i=0;
  // 0~X-1までの料金所カウント
  for(i=0;i<M;i++){
    if(A[i]>=X)break;
    else c1+=1;
  }
  // X+1~Nまでの料金所カウント
  for(;i<M;i++){
    c2+=1;
  }
  cout << min(c1,c2) << "\n";

}

// Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
  LL N;
  scanf("%lld",&N);
  LL M;
  scanf("%lld",&M);
  LL X;
  scanf("%lld",&X);
  vector<LL> A(M);
  for(int i = 0 ; i < M ; i++){
    scanf("%lld",&A[i]);
  }
  solve(N, M, X, move(A));
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <ctype.h>
int main(void){
int i,j,f;
char s[1030];
char t[3][5]={"the","this","that"};
while(fgets(s,1030,stdin)){
for(i=0;i<26;i++){
for(j=0;j<strlen(s);j++){
if(isalpha(s[j])){
if(s[j]=='z')s[j]='a';
else s[j]=(char)((int)s[j]+1);
}
}
f=0;
for(j=0;j<3;j++){
if(strstr(s,t[j])){
f=1;
break;
}
}
if(f){
printf("%s",s);
break;
}
}
}
return(0);
}

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

int main() {
  int64_t h,n,s,a;
  cin >>h >>n;
  s=0;
  for(int i=0; i<n ; i++){
    cin >>a;
    s = s + a;
  }
  cout <<(s>=h?"Yes":"No") <<endl;
  
}

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

int main() {
  string S;
  int Q;
  cin >> S >> Q;
  int T = 0, F = 0;
  string C;
  int num1 = 0;
  for (int i=0; i<Q; i++) {
    cin >> T;
    if (T==1) num1++;
    else {
      cin >> F >> C;
      if (num1%2==0) {
        if (F==1) S.insert(0, C);
        else S += C;
      }
      else {
        if (F==2) S.insert(0, C);
        else S += C;
      }
    }
  }
  if (num1%2==1) reverse(S.begin(), S.end());
  cout << S << endl;
  return 0;
}


Measured memory_bytes: 900
//A - Candy Distribution Again
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

int main()
{
	ll N, x, i;
	cin >> N >> x;
	ll a[N];
	for (i = 0; i < N; i++) {
		cin >> a[i];
	}
	sort(a, a + N);
	ll sum = 0, cnt = 0;
	for (i = 0; i < N; i++) {
		sum += a[i];
		if (sum == x) {
			cnt++;
			break;
		}
		else if(sum > x || i==N-1){
			break;
		}
		cnt++;
	}

	cout << cnt <<endl;
	return 0;
}

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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rrep(i,n,m) for(int (i)=(n);(i)<(m);(i)++)
#define esort(s) sort((s).begin(),(s).end())

typedef long long ll;
typedef pair<int,int> ipair;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;

const int INF = 1000000000;
const ll LINF = 1000000000000000000;
const double PI = acos(-1.0);
const double EPS = 1e-10;

/*
    1. 貪欲法で解ける．
    2. 後ろから最長距離を詰めるだけで良い．
*/
int main(){
    int N, M; cin>>N>>M;
    string S; cin>>S;

    stack<int> stc;
    int L=N;
    while(L>0){
        int newL=L;
        for(int i=max(0,newL-M); i<newL; i++){
            if(S[i]=='1') continue;
            stc.push(newL-i);
            newL=i;
            break;
        }
        if(newL==L){cout<<-1<<"\n";return 0;}
        L=newL;
    }
    while(!stc.empty()){
        cout<<stc.top()<<" ";
        stc.pop();
    }
    cout<<"\n";
}

Measured memory_bytes: 868
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
ll binpow(ll a, ll b)
{
	ll res = 1;
	while(b > 0)
	{
		if(b & 1)
			res = ((res % mod) * (a % mod)) % mod;
		a = ((a % mod) * (a % mod)) % mod;
		b = b >> 1;
	}
	return res;
}
int main()
{
	ll n;
	cin >> n;
	ll ans = binpow(10, n) % mod;
	ll ans1 = (2 * (binpow(9, n) % mod)) % mod;
	ans1 = ((ans1 % mod) - (binpow(8, n) % mod) + mod) % mod;
	ans = ((ans % mod) - (ans1 % mod) + mod) % mod;
	cout << (ans + mod) % mod;
	return 0;
}



Measured memory_bytes: 3500
#include<stdio.h>
#define MAX 10000
#define NIL -1

typedef struct node
{
  int p, l, r;
}Node;

Node T[MAX];
int n;

void preParse(int u)
{
  if(u==NIL) return;
  printf(" %d",u);
  preParse(T[u].l);
  preParse(T[u].r);
}

void inParse(int u)
{
  if(u==NIL) return;
  inParse(T[u].l);
  printf(" %d",u);
  inParse(T[u].r);
}

void postParse(int u)
{
    if(u==NIL) return;
  postParse(T[u].l);
  postParse(T[u].r);
  printf(" %d",u);
}

int main(){
  int i, v, l, r, root;

  scanf("%d",&n);
  for(i=0;i<n;i++)
    T[i].p=NIL;

  for(i=0;i<n;i++){
    scanf("%d %d %d",&v,&l,&r);
    T[v].l=l;
    T[v].r=r;
    if(l!=NIL)
      T[l].p=v;
    if(r!=NIL)
      T[r].p=v;
  }
  for(i=0;i<n;i++)
    if(T[i].p==NIL)root=i;

  printf("Preorder\n");
  preParse(root);
  printf("\n");
  
  printf("Inorder\n");
  inParse(root);
  printf("\n");
  
  printf("Postorder\n");
  postParse(root);
  printf("\n");
  
  return 0;
}



Measured memory_bytes: 2132
import sys
sys.setrecursionlimit(10000000)
import math
import bisect
def input():
    return sys.stdin.readline()[:-1]

n,u,v = map(int,input().split())
u-=1
v-=1
g = [[]for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
seen = [-1 for i in range(n)]
taka = []
aok = []
def dfs(s,lis):
    nec = g[s]
    if len(nec)==1:
        lis.append(s)
    for i in nec:
        if seen[i]!=-1:
            continue
        seen[i] = seen[s]+1
        dfs(i,lis)

seen[u]=0
dfs(u,taka)
takadist = [i for i in seen]
seen = [-1 for i in range(n)]
seen[v]=0
dfs(v,aok)
ans = 0
for i in aok:
    if takadist[i]<seen[i]:
        ans = max(ans,seen[i])
if g[u]==[v]:
    print(0)
else:
    print(ans-1)


Measured memory_bytes: 101840
#include <cstdio>

int main(){
    char n[4];
    scanf("%s", n);
    for(int i=0; i<3; i++){
        if(n[i]=='1') n[i] = '9';
        else n[i] = '1';
    }
    printf("%s\n", n);
    return 0;
}

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

int main () {
  int N, ans = 0;
  cin >> N;
  vector<int> X(N);
  for (int i = 0; i < N; i++) {
    cin >> X[i];
  }
  for(int i = 0; i < N; i++){
    if(X[i]%2 == 0 && X[i]%3 != 0 && X[i]%5 != 0) {
      ans = 1;
    }
  }
  
  if(ans == 0) cout << "APPROVED" << endl ;
  else cout << "DENIED" << endl ;
}

Measured memory_bytes: 256
n,l=map(int,input().split())

mngap=[1,abs(l+1-1)]
for i in range(2,n+1):
  if mngap[1]>abs(l+i-1):
    mngap=[i,abs(l+i-1)]

total=0
for i in range(1,n+1):
  total+=l+i-1
print(total-(l+mngap[0]-1))

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

int main(int argc, char const *argv[])
{
    int a,b;
    cin >> a;
    cin >> b;

    int sum=0;
    for(auto i=0;i<2;i++){
        if(a>b){
            sum+=a;
            a--;
        }
        else{
            sum+=b;
            b--;
        }
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
int INF = 1e9+7;
int mod = 100000;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
signed main() {
    int N;
    cin >> N;
    vector<int>A(N+1);
    for(int i = 0; i <= N; i++) {
        cin >> A[i];
    }
    vector<int>B(N);
    int ans = 0;
    for(int i = 0; i < N; i++) {
        cin >> B[i];
        if(A[i]) {
            if(A[i] < B[i]) {
                B[i]-=A[i];
                ans+=A[i];
            }
            else {
                ans+=B[i];
                B[i] = 0;
            }
        }
        if(B[i]) {
            if(A[i+1] < B[i]) {
                ans+=A[i+1];
                A[i+1] = 0;
            }
            else {
                ans+=B[i];
                A[i+1]-=B[i];
            }
        }
    }
    cout  << ans << endl;
}


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

using namespace std;

int v[256];

int main ()
{
   // freopen ("file.in", "r", stdin);

    int n;
    scanf ("%d", &n);
    n *= 2;

    for (int i = 1; i <= n; ++i)
        scanf ("%d", &v[i]);

    sort (v + 1, v + n + 1);

    int sum = 0;
    for (int i = 1; i <= n; i += 2)
        sum += v[i];

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

    return 0;
}


Measured memory_bytes: 128
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

#[allow(dead_code)]
fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

fn main() {
    //let n = read::<u32>();
    let v = read_vec::<u32>();
    let n = v[0];
    let x = v[1];

    let ls = read_vec::<u32>();

    let mut d = 0;
    for i in 0..n {
        d = d + ls[i as usize];
        if d > x {
            println!("{}", i + 1);
            break;
        }
    }
    if d <= x {
        println!("{}", n + 1);
    }
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define rep(i , x , y) for(register int i = (x) , _## i = ((y) + 1) ; i < _## i ; i ++)
#define Rep(i , x , y) for(register int i = (x) , _## i = ((y) - 1) ; i > _## i ; i --)
using namespace std ;
#define int long long
using ll = long long ;
using pii = pair < int , int > ;
const static int _ = 1 << 20 ;
char fin[_] , * p1 = fin , * p2 = fin ;
inline char gc() { return (p1 == p2) && (p2 = (p1 = fin) + fread(fin , 1 , _ , stdin) , p1 == p2) ? EOF : * p1 ++ ; }
inline int read() {
	bool sign = 1 ; char c = 0 ; while(c < 48) ((c = gc()) == 45) && (sign = 0) ;
	int x = (c & 15) ; while((c = gc()) > 47) x = (x << 1) + (x << 3) + (c & 15) ;
	return sign ? x : -x ;
}
template < class T > void print(T x , char c = '\n') {
	(x == 0) && (putchar(48)) , (x < 0) && (putchar(45) , x = -x) ;
	static char _st[100] ; int _stp = 0 ;
	while(x) _st[++ _stp] = x % 10 ^ 48 , x /= 10 ;
	while(_stp) putchar(_st[_stp --]) ; putchar(c) ;
}
template < class T > void cmax(T & x , T y) { (x < y) && (x = y) ; }
template < class T > void cmin(T & x , T y) { (x > y) && (x = y) ; }
signed main() {
#ifdef _WIN64
	freopen("testdata.in" , "r" , stdin) ;
#endif
	int n ;
	cin >> n ;
	string s , t ;
	cin >>s >> t ;
	string ans ;
	for(int i = 0 ; i < n ; i ++) {
		ans += s[i] ;
		ans += t[i] ;
	} 
	cout << ans << '\n' ;
	return 0 ;
}


Measured memory_bytes: 256
program prob4
    implicit none
    integer::n, i, j, p, ans
    integer, allocatable::a(:)
    read(*,*) n
    allocate(a(n))
    read(*,*) a
    call hsort(n,1,1,a)
    p = gcd(a(2),a(1))
    do i = 3, n
        if(mod(a(i),p) > 0) p = gcd(p,mod(a(i),p))
    end do
    write(*,*) p
    deallocate(a)
    stop
contains
    ! n行m列の配列をp列目でsort
    ! 1次元配列ならm=p=1
    subroutine hsort(n,m,p,array)
        implicit none
        integer,intent(in)::n, m, p
        integer,intent(inout)::array(n,m)

        integer ::i,k,j,l
        integer::t(m)

        if(n.le.0)then
        write(6,*)"Error, at heapsort"; stop
        end if
        if(n.eq.1)return

        l=n/2+1
        k=n
        do while(k.ne.1)
        if(l.gt.1)then
            l=l-1
            t=array(L,:)
        else
            t=array(k,:)
            array(k,:)=array(1,:)
            k=k-1
            if(k.eq.1) then
                array(1,:)=t
                exit
            end if
        end if
        i=l
        j=l+l
        do while(j.le.k)
            if(j.lt.k)then
                if(array(j,p).lt.array(j+1,p))j=j+1
            end if
            if (t(p).lt.array(j,p))then
                array(i,:)=array(j,:)
                i=j
                j=j+j
            else
                j=k+1
            end if
        end do
        array(i,:)=t
        end do

        return
    end subroutine hsort
    function gcd(x,y) result(z)
        implicit none
        integer::x, y, z, i, a, b, c
        a = y
        b = x
        do while(mod(a,b) > 0)
            c = mod(a,b)
            a = b
            b = c
        end do
        z = b
    end function
end program

Measured memory_bytes: 3404
#include<iostream>
#include<cstdlib>
#include<string>
#include<map>
#include<algorithm>
#include<vector>
#include<cmath>
#include<iomanip>
using namespace std;
#define rep(i,n) for(int i(0);i<n;i++)
typedef long long ll;

int main(){
	long N(0), K(0);
    cin >> N >> K ;
    vector<long> H;
    rep(i,N){
        long h;
        cin >> h;
        H.push_back(h);
    }

    sort(H.begin(),H.end());

    long ans(0);
    if(K>=H.size()) ans = 0;
    else{
        rep(i,H.size()-K) ans += H[i];
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 2420
#include <bits/stdc++.h>
using namespace std;
long long n, a[200000], b[200000], c[200000], dp[200000][3]; 
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i ++)
		cin >> a[i] >> b[i] >> c[i];
		
	dp[1][1] = a[1]; 
	dp[1][2] = b[1];
	dp[1][3] = c[1];
	
	for (int i = 2; i <= n; i ++)
	{
		dp[i][1] = max(dp[i-1][2], dp[i-1][3]) + a[i];
		dp[i][2] = max(dp[i-1][1], dp[i-1][3]) + b[i];
		dp[i][3] = max(dp[i-1][1], dp[i-1][2]) + c[i]; 
	}	
	cout << max (dp[n][1], max (dp[n][2], dp[n][3]));
}

Measured memory_bytes: 8832
import java.util.Map.Entry;
import java.util.*;
import java.math.*;
import org.w3c.dom.css.Counter;
  
public class Main{
    public static void main(final String[] args){
 
        final Scanner sc = new Scanner(System.in);
        long A =sc.nextInt();
        long V =sc.nextInt();
        long B =sc.nextInt();
        long W =sc.nextInt();
        long T =sc.nextInt();
        long div = Math.abs(A-B);
        long run = V-W;
        long ans =div -(run*T);
        if(ans>0){
            System.out.println("NO");
        }else{
            System.out.println("YES");
        }
    }
} 

Measured memory_bytes: 35776
n, k = map(int, input().split())
A = list(map(int, input().split()))

ans = 10 ** 11
for b in range(1 << n):
    if bin(b).count("1") != k:
        continue

    max_ai = 0
    cost = 0
    for i in range(n):
        if (b & 1 << i):
            if A[i] > max_ai:
                max_ai = A[i]
            else:
                cost += (max_ai + 1) - A[i]
                max_ai += 1
        else:
            max_ai = max(max_ai, A[i])

    ans = min(ans, cost)

print(ans)




Measured memory_bytes: 3064
#include<algorithm>
#include <iostream>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<string>
using namespace std;
int main(){
   
    int x,a,b;
    cin>>x>>a>>b;
    
    if(abs(x-a)>abs(x-b)){
        cout<<"B"<<endl;
    }else{
        cout<<"A"<<endl;
    }
    
    return 0;
}






Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
mod2 = mod4 = 0
for i in a:
    if i%4==0:
        mod4 += 1
    elif i%2==0:
        mod2 += 1
n -= max(0, mod2-1)
if n<=mod4*2+1:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 15020
#include <bits/stdc++.h>
using namespace std;
template<typename T, typename U> T &ctmax(T &x, const U &y){ return x = max<T>(x, y); }
template<typename T, typename U> T &ctmin(T &x, const U &y){ return x = min<T>(x, y); }



int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(ios::badbit | ios::failbit);
	int n;
	cin >> n;
	const int inf = numeric_limits<int>::max();
	vector<int> a(n), b(n);
	vector<int> al(n + 1, -1), ar(n + 1, -1), bl(n + 1, -1), br(n + 1, -1);
	for(auto i = 0; i < n; ++ i){
		cin >> a[i];
	}
	for(auto i = 0; i < n; ++ i){
		cin >> b[i];
	}
	int tot = 0;
	vector<int> cnt(n + 1);
	for(auto x = 1, ai = 0, bi = 0; x <= n; ++ x){
		while(ai < n && a[ai] < x){
			++ ai;
		}
		if(ai < n && a[ai] == x){
			int aj = ai;
			while(aj < n && a[aj] == x){
				++ aj;
			}
			tie(al[x], ar[x]) = pair{ai, aj};
			ai = aj;
		}
		while(bi < n && b[bi] < x){
			++ bi;
		}
		if(bi < n && b[bi] == x){
			int bj = bi;
			while(bj < n && b[bj] == x){
				++ bj;
			}
			tie(bl[x], br[x]) = pair{bi, bj};
			bi = bj;
		}
		if(~al[x] && ~bl[x]){
			++ tot;
			if(ar[x] - al[x] + br[x] - bl[x] > n){
				cout << "No\n";
				return 0;
			}
			if(bl[x] <= al[x]){
				if(br[x] <= al[x]){
					++ cnt[0];
					-- cnt[al[x] - br[x] + 1];
					++ cnt[ar[x] - bl[x]];
					-- cnt[n];
				}
				else{
					++ cnt[ar[x] - bl[x]];
					-- cnt[al[x] + n - br[x] + 1];
				}
			}
			else{
				++ cnt[max(0, ar[x] - bl[x])];
				-- cnt[al[x] + n - br[x] + 1];
			}
		}
	}
	for(auto t = 0; t < n; ++ t){
		if(cnt[t] == tot){
			cout << "Yes\n";
			rotate(b.begin(), b.begin() + n - t, b.end());
			for(auto x: b){
				cout << x << " ";
			}
			cout << "\n";
			return 0;
		}
		cnt[t + 1] += cnt[t];
	}
	cout << "No\n";
	return 0;
}

/*

*/

////////////////////////////////////////////////////////////////////////////////////////
//                                                                                    //
//                                   Coded by Aeren                                   //
//                                                                                    //
////////////////////////////////////////////////////////////////////////////////////////

Measured memory_bytes: 8688
#include<bits/stdc++.h>
using namespace std ;
int32_t main()
{
     int a,b,c ;
     cin>>a>>b>>c ;
     int k;
     cin>>k;
        int steps=0;
     while(b<=a)
     {
         b=b*2;
         ++steps;
     }
     
     while(c<=b)
     {
         c=c*2;
         ++steps;
     }
     if(steps<=k)
     cout<<"Yes\n";
     else
     cout<<"No\n";

    return 0;
}


Measured memory_bytes: 3612
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC125A
{
    class Program
    {
        static void Main(string[] args)
        {
            int a, b, c;
            string[] ss = Console.ReadLine().Split(' ');
            a = int.Parse(ss[0]);
            b = int.Parse(ss[1]);
            c = int.Parse(ss[2]);
            Console.WriteLine((c / a) * b);
            Console.ReadKey();

        }
    }
}


Measured memory_bytes: 11092
// F.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <unordered_set>

using namespace std;

typedef pair<int, int> II;

class BIT {
	std::vector<int> bit;
	int size;
public:
	BIT() { }
	BIT(int sz) { init(sz); }
	void init(int sz) {
		bit = std::vector<int>((size = sz) + 1);
	}
	int sum(int i) {
		int s = 0;
		while (i > 0) {
			s += bit[i];
			i -= i & -i;
		}
		return s;
	}
	void add(int i, int x) {
		while (i <= size) {
			bit[i] += x;
			i += i & -i;
		}
	}
};

int main(int argc, char* argv[]) {
	cout.precision(20);
#ifdef _MSC_VER
	while (true)
#endif
	{
		int n = -1, q, l, r;
		cin >> n >> q;
		if (n <= 0) return 0;
		vector<int> col(n), last(n), ans(q);
		for (int i = 0; i < n; ++i) {
			cin >> col[i];
			--col[i];
		}
		vector<pair<II, int>> query(q);
		for (int t = 0; t < q; ++t) {
			query[t].second = t;
			cin >> query[t].first.second >> query[t].first.first;
		}
		sort(query.begin(), query.end());
		int qi = 0;
		BIT bit(n);
		for (int i = 0; i < n; ++i) {
			if (last[col[i]]) {
				bit.add(last[col[i]], -1);
			}
			last[col[i]] = i + 1;
			bit.add(last[col[i]], 1);
			while (qi < q && query[qi].first.first == i + 1) {
				ans[query[qi].second] = bit.sum(i + 1) - bit.sum(query[qi].first.second - 1);
				++qi;
			}
		}
		for (int t = 0; t < q; ++t) {
			cout << ans[t] << endl;
		}
	}
	return 0;
}


Measured memory_bytes: 17364
#include <bits/stdc++.h>
using namespace std;
int main() {
    int A,B,C,D; cin>>A>>B>>C>>D;
    int left=A+B;
    int right=C+D;
    if(left>right){
        cout<<"Left";
    }
    else if(left<right){
        cout<<"Right";
    }
    else{
        cout<<"Balanced";
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <queue>

using namespace std;

int main()
{
    int n, m;
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > ab;
    priority_queue<int> max_b;

    cin >> n >> m;

    for(int i = 0; i < n; ++i)
    {
        int a, b;
        cin >> a >> b;
        ab.push(make_pair(a, b));
    }


    int ans = 0;
    for(int i = 1; i <= m; ++i)
    {
        while(!ab.empty() && ab.top().first <= i)
        {
            auto p = ab.top();
            ab.pop();

            max_b.push(p.second);
        }

        if(!max_b.empty())
        {
            ans += max_b.top();
            max_b.pop();
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1908
// tested by Hightail - https://github.com/dj3500/hightail
import std.stdio, std.string, std.conv, std.algorithm;
import std.range, std.array, std.math, std.typecons, std.container, core.bitop;

int h, w;

void main() {
    scan(h, w);

    foreach (i ; 0 .. h) {
        auto j = readln.split.countUntil("snuke");

        if (j > -1) {
            writefln("%c%d", ('A' + j).to!char, i + 1);
            return;
        }
    }
}


void scan(T...)(ref T args) {
    string[] line = readln.split;
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}


void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){

    char str[10];
    scanf("%s", str);

    int cnt = 0;
    int max = 0;

    for (int i = 0; i < 10; i++){
        
        if(str[i] == 65||str[i] == 67||str[i] == 71||str[i] == 84){
            cnt += 1;
        }else{
            cnt = 0;
        }

        if(cnt > max){
            max = cnt;
        }
    }

    printf("%d", max);

    return 0;
}

Measured memory_bytes: 128