akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;


int r, c, k, ri, ci, vi, v[3005][3005];
typedef long long ll;
ll ans, memo[3005][3005][4];
#define INF 1023456789123456789

ll dp(int i, int j, int can_take){
    //printf("%d %d %d\n", i, j, can_take);
    if (i <= 0 || j <= 0 || i > r || j > c) return -INF;
    if (i == r && j == c){
        if (can_take != 0) return v[i][j];
        else return 0;
    }
    if (memo[i][j][can_take] != -1) return memo[i][j][can_take];
    if (v[i][j] == 0 || can_take == 0){
        memo[i][j][can_take] = max(dp(i, j + 1, can_take), dp(i + 1, j, 3));
    }
    else{
        memo[i][j][can_take] = max(max(dp(i + 1, j, 3), dp(i + 1, j, 3) + v[i][j]),
                                   max(dp(i, j + 1, can_take), dp(i, j + 1, can_take - 1) + v[i][j]));
    }
    //printf("%d %d %d %d %lld\n", i, j, can_take, v[i][j], memo[i][j][can_take]);
    return memo[i][j][can_take];
}

int main(){
    scanf("%d%d%d", &r, &c, &k);
    for (int i = 0; i < k; ++i){
        scanf("%d%d%d", &ri, &ci, &vi);
        v[ri][ci] = vi;
    }
    memset(memo, -1, sizeof memo);
    printf("%lld", dp(1, 1, 3));
}


Measured memory_bytes: 321916
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e5 + 5;

int n, m;
int A[N];
pair<int, int> BC[N];

int main()
{
  cin >> n >> m;
  for(int i = 0 ; i < n ; i++){
    cin >> A[i];
  }
  sort(A, A + n);
  for(int i = 0 ; i < m ; i++)
    cin >> BC[i].second >> BC[i].first;
  sort(BC, BC + m);
  int idx = 0;
  long long ans = 0;
  for(int i = m - 1 ; i >= 0 ; i--){
    int cur = BC[i].first;
    int cnt = BC[i].second;
    while(idx < n && A[idx] < cur && cnt > 0){
      A[idx++] = cur;
      cnt--;
    }
  }
  for(int i = 0 ; i < n ; i++)
    ans += A[i];
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1408
from collections import deque
n, m = map(int, input().split())
ab = []
for i in range(m):
    a, b = map(int, input().split())
    a-=1; b-=1
    ab.append((a, b))

ans = 0
for i in range(m):
    # グラフ作成
    g = [[] for i in range(n)]
    for j in range(m):
        if i == j: continue
        a, b = ab[j]
        g[a].append(b)
        g[b].append(a)
    # 距離計算
    dist = [-1] * n
    dq = deque([0])
    dist[0] = 0
    while dq:
        now = dq.popleft()
        for to in g[now]:
            if dist[to]>=0: continue
            dist[to] = dist[now] + 1
            dq.append(to)
    if dist.count(-1) > 0:
        ans+=1
print(ans)
    

    

Measured memory_bytes: 9440
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <string>
#include <sstream>
#include <stack>
#include <iomanip>
#include <numeric>
#include <queue>
#include <climits>
#include <set>
#include <complex>
#include <cmath>
#include <map>
using namespace std;
using ll = long long;
#define MOD 1000000007
#define INF 1LL << 59

vector<string> R;
int dxy[5] = {-1, 0, 1, 0, -1};

void dfs(int y, int x)
{
    R[y][x] = '0';

    for (int i = 0; i < 4; ++i)
    {
        int ny = y + dxy[i], nx = x + dxy[i + 1];
        if (nx >= 0 && nx < 12 && ny >= 0 && ny < 12 && R[ny][nx] == '1')
        {
            dfs(ny, nx);
        }
    }
}
int solve()
{
    int ans = 0;
    for (int i = 0; i < 12; ++i)
    {
        for (int j = 0; j < 12; ++j)
        {
            if (R[i][j] == '1')
            {
                dfs(i, j);
                ans++;
            }
        }
    }
    return ans;
}
int main()
{
    //std::ios::sync_with_stdio(false);
    //std::cin.tie(0);
    //cout << fixed << setprecision(7);

    while (true)
    {
        R = vector<string>(12);

        for (int i = 0; i < 12; i++)
        {
            if (!(cin >> R[i]))
            {
                return 0;
            }
        }

        cout << solve() << endl;
    }
    return 0;
}


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

signed main() {
    int N, x;
    cin >> N >> x;

    vector<int> a(N);
    for (int& x : a) cin >> x;

    vector<vector<int>> mem(N, vector<int> (N, 1LL<<62));
    for (int i = 0; i < N; i++) {
        for (int k = 0; k < N; k++) {
            int t = a[(i + N - k) % N];
            mem[i][k] = min(mem[i][k - !!k], t);
        }
    }

    int ans = 1LL<<62;
    for (int k = 0; k < N; k++) {
        int t = 0;
        for (int i = 0; i < N; i++) {
            t += mem[i][k];
        }
        ans = min(ans, t + k * x);
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 31616
#include <stdio.h>
#include <stdlib.h>

int main(){
	int j;
	int n;
	int *A = NULL;
	int flag;
	int temp;
	int count = 0;

	scanf("%d",&n);
	A = (int *)malloc(4*n);
	for(j=0;j<n;j++){
		scanf("%d",&A[j]);
	}

	flag = 1;
	while(flag){
		flag = 0;
		for(j=n-1;j>0;j--){
			if(A[j]<A[j-1]){
				temp = A[j];
				A[j] = A[j-1];
				A[j-1] = temp;
				flag = 1;
				count++;
			}
		}
	}
	for(j=0;j<n-1;j++){
		printf("%d ", A[j]);
	}
	printf("%d\n",A[n-1]);
	printf("%d\n",count);
	free(A);
}

Measured memory_bytes: 600
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define mod 1000000007ll
#define mod1 998244353ll
#define endl '\n'
#define inf ((ll)1e18+1)
#include<chrono>
using namespace chrono;
mt19937_64 rng(high_resolution_clock::now().time_since_epoch().count());
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define debr(x,y) {cout<<"-->  "<<#x<<" to "<<#y<<" :  "; auto itr=x; while(itr!=y) cout<<(*itr++)<<' '; cout<<endl; }
#define deba(x) {cout<<"-->  "<<#x<<" :  "; for(auto ele:(x)) cout<<ele<<"  "; cout<<endl; }
#define deb(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s);istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {cout<<endl;}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << " = " << a <<"  ,  ";
    err(++it, args...);
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll n;
    cin>>n;
    map<string,ll> mp;
    for(ll x=0;x<n;x++){
        string s;
        cin>>s;
        mp[s]++;
    }
    cout<<"AC x "<<mp["AC"]<<endl;
    cout<<"WA x "<<mp["WA"]<<endl;
    cout<<"TLE x "<<mp["TLE"]<<endl;
    cout<<"RE x "<<mp["RE"]<<endl;
    return 0;

}

Measured memory_bytes: 3648
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

i64 x;

int main()
{
	i64 n;
	scanf("%lld", &x);
	n=(x-1)/11;
	n=n*2+1;
	if(x%11>6 || x%11==0){
		n+=1;
	}

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

	return 0;
}


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

using namespace std;

long long int table[100];

long long int func(int n) {
        if (table[n] == 0) {
                return (table[n] = func(n - 1) + func(n - 2));
        } else {
                return table[n];
        }
}

int main() {
        table[0] = 2;
        table[1] = 1;

        int x;
        cin >> x;
        cout << func(x) << endl;

        return 0;
}

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

int main() {
  int N, K, x ,Y;
  cin >> N >> K;
  for(int i = 0; i < N; i++) {
    cin >> x;
    if(K / 2 >= x) {
      Y += x * 2;
    }
    else if(K / 2 < x && x <= K) {
      Y += (K - x) * 2;
    }
    else {
      Y += (x - K) * 2;
    }
  }
  cout << Y << endl;
}


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

using namespace std;

#define inf 1<<30
#define pqueue priority_queue
#define mp make_pair
#define pb push_back
#define fn fill_n
typedef long long llong;
typedef unsigned long long ullong;
typedef pair<int, int> P;


int main(){
	string s;
	cin >> s;
	for(int i = 1; i <= 7; i++){
		string f = s.substr(0, i);
		string b = s.substr((int)s.size()-(7-i), 7-i);
		string check = f+b;
		if(check == "keyence"){
			cout << "YES" << endl;
			return 0;
		}
	}

	cout << "NO" << endl;
	return 0;
}

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

using namespace std;

#define sz(x) ((int) ((x).size()))
typedef long long ll;
typedef long double ld;

const int mod = 1e9 + 7;
int n, l[2], p[5100], dp[3][5100][5100], ps[5100];

int add(int a, int b) {
  a += b;
  if (a >= mod)
    a -= mod;
  return a;
}

int sub(int a, int b) {
  a -= b;
  if (a < 0)
    a += mod;
  return a;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(10);
  cin >> n >> l[0] >> l[1];
  p[0] = 1;
  for (int i = 0; i < n; i++)
    p[i + 1] = add(p[i], p[i]);
  if (l[0] < l[1])
    swap(l[0], l[1]);
  int res = 0;
  dp[0][0][0] = 1;
  for (int i = 0; i <= n; i++) {
    ps[i + 1] = add(ps[i + 1], ps[i]);
    dp[1][i][0] = add(dp[1][i][0], ps[i]);
    for (int j = 0; j <= i && j < l[0]; j++) {
      dp[0][i + 1][j + 1] = add(dp[0][i + 1][j + 1], dp[0][i][j]);
      dp[0][i + 1][j + 1] = add(dp[0][i + 1][j + 1], dp[1][i][j]);
      dp[0][i + 1][j + 1] = add(dp[0][i + 1][j + 1], dp[2][i][j]);
      dp[2][i + 1][j + 1] = add(dp[2][i + 1][j + 1], dp[2][i][j]);
      if (i + l[1] <= n)
        dp[2][i + l[1]][j + l[1]] = add(dp[2][i + l[1]][j + l[1]], dp[0][i][j]);
      ps[i + 1] = add(ps[i + 1], dp[0][i][j]);
      if (i + l[1] <= n)
        ps[i + l[1]] = sub(ps[i + l[1]], dp[0][i][j]);
    }
  }
  for (int k = 0; k < 3; k++)
    for (int i = 0; i <= n; i++)
      for (int j = l[0]; j <= n; j++)
        res = add(res, ((ll) dp[k][i][j] * p[n - i]) % mod);
  cout << res << "\n";
}


Measured memory_bytes: 157992
import java.util.*;

public class Main {
    public static void main(String[] args){
    
    Scanner sc = new Scanner(System.in);
	String S = sc.next();
 	String T = sc.next();  
	int A = sc.nextInt();
	int B = sc.nextInt();
 	String U = sc.next();  
      if(U. equals (S)){
		System.out.println(A-1 +" "+ B);
    }else{
		System.out.println(A + " "+ (B-1));
    }
}
}

Measured memory_bytes: 22356
n=int(input())
s=input()
left=0
left_cnt=0
for i in s:
    if i=="(":
        left+=1
    else:
        if left>=1:
            left-=1
        else:
            left_cnt+=1
right=0
right_cnt=0
for i in s[::-1]:
    if i==")":
        right+=1
    else:
        if right>=1:
            right-=1
        else:
            right_cnt+=1
print("("*left_cnt+s+")"*right_cnt)

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

int main()
{
    string S;
    cin >> S;
    int n = S.size(), cnt = 0;
    for(int i = 0;i < n / 2;i++) if(S[i] != S[n - 1 - i]) {
        ++cnt;
    }
    cout << cnt << endl;
    return 0;
}


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

int main(){
    int N,M,X;
    cin>>N>>M>>X;
    int A[M]={},B[N+1]={};
    for(int i=0;i<M;i++){
        cin>>A[i];
        B[A[i]]=1;
    }
    int count=0;
    for(int i=0;i<X;i++){
        count+=B[i];
    }
    if(count<M/2){
        cout<<count<<endl;
    }else{
        cout<<M-count<<endl;
    }


    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <math.h>

using namespace std;

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

    long long ans = N - 1;
    for (int i = 2; i <= sqrt(N); i++)
        if (N % i == 0)
        {
            ans = i + N / i - 2;
        }

    cout << ans << endl;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
typedef long long int ll;
#define rep(i,n) for (int i = 0; i< (n); i++)
#define Rep(i,n,m) for (int i = (n); i< (m); i++)
#define Sort(a) sort(a.begin(), a.end())
#define Reverse(a) reverse(a.begin(), a.end())
using namespace std;


int main() {
    ll n, count=0, max = 0;
    cin>>n;
    
    vector<ll> h(n);
    
    rep(i,n) cin>>h[i];
    
    
    Rep(i,0, n-1){
        if(h[i]>=h[i+1]) count++;
        
        else{
            if(max<count) max = count;
            count = 0;
        }
    }
    
    if(max<count) max = count;
    
    cout<<max<<endl;
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define pll pair<ll,ll>
#define pii pair<int,int>
#define rep(i,n) for(int i=0;i<n;i++)
#define For(i,a,b) for(int i=a;i<b;i++)
#define sz(x) ((ll)(x).size())
#define pb push_back
#define mp make_pair
#define bit(n) (1LL<<(n))
#define F first
#define S second
#define debug(x) cerr << x << endl
#define Complex complex<double>
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const ll INF = 1LL<<60;
const ll mod = (int)1e9 + 7;

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

int main() {
    string s;
    cin >> s;
    rep(i,3){
        if(s[i]=='7'){
            cout << "Yes";
            return 0;
        }
    }
    cout << "No";

    
}

/*
*/



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

int main(void) {
  string S;
  long long K;
  cin >> S >> K;
  int cnt = 0;
  char nc;
  for(int i = 0; i < S.size(); i++) {
    if(0 < S[i] - '1') {
      nc = S[i];
      break;
    }
    cnt++;
  }
  if(K <= cnt) {
    cout << '1' << endl;
    return 0;
  }
  cout << nc << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

long long a[100010][3];

long long dp[100010][3];

int main()
{
  int n; cin >> n;
  for (int i = 0; i < n; i++) for (int j = 0; j < 3; ++j) cin >> a[i][j];
  
  // ループ
  for (int i = 0; i < n; ++i)
  {
    for (int j = 0; j < 3; ++j)
    {
      for (int k = 0; k < 3; ++k)
      {
        if( j==k ) continue;
        chmax(dp[i+1][k], dp[i][j] + a[i][k]);
      }
    }
  }
  
  long long res = 0;
  for (int j = 0; j < 3; ++j) chmax(res,dp[n][j]);
  cout << res << endl;
}
  

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

cnt=0
for i in A:
    if i < 0:
        cnt += 1

X=[]
for i in A:
    X.append(abs(i))

if cnt % 2 == 0:
    print(sum(X))
else:
    print(sum(X) - (min(X)*2))

Measured memory_bytes: 14412
#include<stdio.h>
#define ll long long
ll abbs(ll a){if(a>0) return a; return -a;}
int main(){
    ll n, k;
    scanf("%lld%lld",&n,&k);
    if(k >= (2 * n)) printf("%lld\n",n);
    else{
        ll q = n % k;
        ll r = abbs(q - k);
        if(r > q) printf("%lld\n",q);
        else printf("%lld\n",r);
    }
    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    string s[3]= {"Sunny","Cloudy","Rainy"};
    string s1; cin >> s1;
    if(s1=="Sunny"){
        cout << "Cloudy" << endl;
    }
    if(s1=="Cloudy"){
        cout << "Rainy" << endl;
    }
    if(s1=="Rainy"){
        cout << "Sunny" << endl;
    }
}


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

using namespace std;
int main()
{
  long long n;
  cin>>n;
  long long h[n+1],dp[n+1];
  for(long long i=1;i<=n;i++)
    cin>>h[i];
  dp[0]=0;
  h[0]=0;
  dp[1]=0;
  dp[2]=abs(h[2]-h[1]);
  for(long long i=3;i<=n;i++)
  {
    dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]));
  }
  cout<<dp[n];
  return 0;
}

Measured memory_bytes: 5100
# -*- coding: utf-8 -*-
"""
B - Chocolate
https://beta.atcoder.jp/contests/abc092/tasks/abc092_b

"""
import sys
from sys import stdin
input = stdin.readline


def solve(N, D, X, A):
    ans = X
    for a in A:
        for i in range(1, D+1, a):
            ans += 1
    return ans


def main(args):
    N = int(input())
    D, X = map(int, input().split())
    A = []
    for _ in range(N):
        A.append(int(input()))
    ans = solve(N, D, X, A)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])
    


Measured memory_bytes: 3064
S = input()
y,m,d = S.split('/')
if int(y) < 2019:
  print('Heisei')
else:
  if int(y) <= 2019:
    if int(m) < 5:
      print('Heisei')
    else:
      print("TBD")
  else:
    print("TBD")

Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define int long long
#define f first
#define s second
using namespace std;
const int mod=2019;
int pw(int a,int t){
    int x=1;
    while(t){
        if(t&1)x=x*a%mod;
        a=a*a%mod,t>>=1;
    }
    return x;
}
int32_t main(){
    ios::sync_with_stdio(0),cin.tie(0);
    string st;
    cin >> st;
    reverse(st.begin(),st.end());
    st='0'+st;
    int n=st.size();
    int a[n],ans=0,s=0;
    for(int i=0;i<n;i++){
        // cout << st[i]-'0';
        s=((s+pw(10,i)*(st[i]-'0'))%mod)%mod;
        a[i]=s;
    }
    map <int,int> m;
    for(int i=0;i<n;i++){
        ans+=m[a[i]];
        m[a[i]]++;
    }
    cout << ans;
}

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

using namespace std;

int main(){



    int a,b,c;
    int i;
    cin >> a >> b >> c;
    int ans;
    ans = c-(a-b);
    if (ans < 0){
        ans = 0;
    }

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

Measured memory_bytes: 256
N, M = map(int, input().split())
A = [0] * M
B = [0] * M

for i in range(M):
    A[i], B[i] = map(int, input().split())

class UF:
    def __init__(self, N):
        self.par = [-1] * N

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

    def size(self, v):
        return -1 * self.par[self.find(v)]
    
    def union(self, v1, v2):
        v1 = self.find(v1)
        v2 = self.find(v2)
        if v1 == v2: return False

        if self.size(v1) < self.size(v2):
            v1, v2 = v2, v1
        self.par[v1] += self.par[v2]
        self.par[v2] = v1
        return True

uf = UF(N)
ans = [0] * (M)
ans[M-1] = N*(N-1)//2

for i in reversed(range(1, M)):
    if uf.find(A[i]-1) == uf.find(B[i]-1):
        ans[i-1] = ans[i]
    else:
        ans[i-1] = ans[i] - uf.size(A[i]-1) * uf.size(B[i]-1)
        uf.union(A[i]-1, B[i]-1)

for a in ans:print(a)

Measured memory_bytes: 18172
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000007
ll ara[200005];
main()
{
    ll n,i,ans=0;
    cin>>n;
    for(i=1;i<=n;i++)cin>>ara[i];
    for(i=2;i<=n;i++)
    {
        if(ara[i]<ara[i-1])
        {
            ans+=(ara[i-1]-ara[i]);
            ara[i]=ara[i-1];
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 5164
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <cmath>
using namespace std;
#define MOD 1000000007
#define INF 1<<30
#define LINF (ll)1<<62
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> P;
typedef vector<pair<ll, ll>> vpl;
 
vvl G(200005);
vl sum(200005,0);
bool visit[200005];
vl v(200005,0);

void bfs(ll s, ll n){
    queue<ll> q;
    q.push(s);
    sum[s] += v[s];
    while(!q.empty()){
        ll t = q.front(); q.pop();
        visit[t] = true;
        for(auto i : G[t]){
            if(visit[i]) continue;
            sum[i] = sum[t] + v[i];
            q.push(i);
        }
    }
}
 
int main(){
    ll n,q; cin >> n >> q;
    rep(i,n-1){
        ll a,b; cin >> a >> b; a--; b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    ll p,x;
    rep(i,q){
        cin >> p >> x;
        p--;
        v[p] += x;
    }
    bfs(0,n);
    rep(i,n) cout << sum[i] << " ";
    //rep(i,q) cout << v[i] << endl;
}


Measured memory_bytes: 19696
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <map>
#include <numeric>
using namespace std;

int main()
{
  int n;
  cin>>n;
  int up=n/100,down=n-n/100*100;
  if(1<=up&&up<=12 && 1<=down&&down<=12){
    cout<<"AMBIGUOUS"<<endl;
  }else if(1<=up&&up<=12){
    cout<<"MMYY"<<endl;
  }else if(1<=down&&down<=12){
    cout<<"YYMM"<<endl;
  }else{
    cout<<"NA"<<endl;
  }
}


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

using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> a(n);
	for(int i = 0; i < n; ++i){ cin >> a[i]; }
	sort(a.begin(), a.end());
	int c = 0;
	for(int i = 1; i < n; ++i){
		if(a[i - 1] == a[i]){ ++c; }
	}
	const int answer = n - ((c + 1) & ~1);
	cout << answer << endl;
	return 0;
}



Measured memory_bytes: 640
n,d = map(int,input().split())

dat = []

for i in range(n):
    dat.append(list(map(int,input().split())))

def isSquare(x):
    for i in range(x+1):
        if i**2 == x:
            return True
    return False
cnt = 0
for i in range(n):
    for j in range(i+1,n):
        s = 0
        for k in range(d):
            s+= (dat[i][k]-dat[j][k])**2
        if isSquare(s):
            cnt+=1
print(cnt)


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


def solve(N: int, K: int, X: int, Y: int):
    res = 0
    if N > K:
        res = K * X + (N - K) * Y
    else:
        res = N * X
    print(int(res))
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    solve(N, K, X, Y)


if __name__ == "__main__":
    main()


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

class Rolling_Hash{
private:
  ll n;
  static constexpr ll base1=1007,base2=2009;
  static constexpr ll mod1=(1e9+7),mod2=(1e9+9);
  vector<ll> hash1,hash2,mpow1,mpow2;
public:
  Rolling_Hash(const string& s){
    n=s.size();
    hash1.assign(n+1,0);
    hash2.assign(n+1,0);
    mpow1.assign(n+1,1);
    mpow2.assign(n+1,1);
    for(ll i=0;i<n;++i){
      hash1[i+1] = (hash1[i]*base1+s[i])%mod1;
      hash2[i+1] = (hash2[i]*base2+s[i])%mod2;
      mpow1[i+1] = (mpow1[i]*base1)%mod1;
      mpow2[i+1] = (mpow2[i]*base2)%mod2;
    }
  }
  auto get(ll l,ll r){
    ll lefval = hash1[r]-hash1[l]*mpow1[r-l]%mod1;
    ll rigval = hash2[r]-hash2[l]*mpow2[r-l]%mod2;
    if(lefval<0)lefval+=mod1;
    if(rigval<0)rigval+=mod2;
    return make_pair(lefval,rigval);
  }
  auto get_LCP(ll a,ll b){
    ll len = min( n-a+1,n-b+1 );
    ll low=0,high=len;
    while( high-low>1 ){
      ll mid=(high+low)>>1;
      if(get(a,a+mid)!=get(b,b+mid))high=mid;
      else low=mid;
    }
    return low;
  }
};

main(){

  ll n;
  string s;
  cin>>n>>s;

  Rolling_Hash rh(s);
  ll ans=0;
  rep(i,n){
    for(ll j=i+1;j<n;++j){
      ll lcp=rh.get_LCP(i,j);
      ans=max(ans,min(lcp,j-i));
    }
  }
  cout<<(ans)<<endl;

}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
//#include <string>
#include <algorithm>
//#include <math.h>
//#include <queue>
//#include <stack>
//#include <iomanip>

// sometimes used
//#include <set>
//#include <map>
//#include <numeric>
//#include <list>
//#include <deque>
//#include <unordered_map>

typedef long long LL;
//typedef long double LD;
using namespace std;
 
//#define MOD 1000000007
//#define MAX 100100
//#define NIL -1
//#define INFTY 1000000000000000000

int main(){
    LL n;
    LL x;
    LL y;
    cin >> n;

    vector<LL> z(n);
    vector<LL> w(n);
    for(LL i=0; i<n; i++){
        cin >> x >> y;
        z[i]=x+y;
        w[i]=x-y;
    }

    sort(z.begin(), z.end());
    sort(w.begin(), w.end());
    LL ans=max(z[n-1]-z[0], w[n-1]-w[0]);

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 6316
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

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

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL


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

    int N, M;
    cin >> N >> M;

    cout << (M >= N ? "Yes\n" : "No\n");

    return 0;
}



Measured memory_bytes: 256
const memo = {}

const main = stdin => {
  const input = stdin.trim().split('\n')
  const [A, B, C] = input[0].split(' ').map(x => parseInt(x))
  const K = parseInt(input[1])

  const max = Math.max(A, B, C)
  console.log(max * Math.pow(2, K) + A + B + C - max)
}


// 標準入力
main(require("fs").readFileSync("/dev/stdin", "utf8"))


Measured memory_bytes: 29560
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    n = int(input())
    A = readInts()
    res = 0
    # 同じおなじやつは同じ奴でずっと続く
    i = 0
    while i < n:
        # 同じもの
        while i+1 < n:
            if A[i] == A[i+1]:
                i += 1
            else:
                break
        # 無くなったら、
        # もし先に上のものを見つけたら、ずっと上を探索する
        if i+1 < n:
            if A[i] < A[i+1]:
                while i+1 < n:
                    if A[i] <= A[i+1]:
                        i+=1
                    else:
                        break
        # どちらかなので、elifで。
            elif i + 1 < n:
                if A[i] > A[i+1]:
                    while i + 1 < n:
                        if A[i] >= A[i+1]:
                            i += 1
                        else:
                            break
        # ここで1ループは終わりなので、カウントに+1する
        #print(i)
        res += 1
        i += 1
    print(res)
if __name__ == '__main__':
  main()


Measured memory_bytes: 16340
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];
    if(n % 2 == 0){
        for(int i = n; i > 0; i-=2) cout << a[i] << " ";
        for(int i = 1; i < n; i+=2) cout << a[i] << " ";
    } else {
        for(int i = n; i > 0; i -= 2) cout << a[i] << " ";
        for(int i = 2; i < n; i+=2) cout << a[i] << " ";
    }
    cout << endl;
    return 0;
}


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

#define F first
#define S second
#define PB push_back
#define MP make_pair
#define REP(i,a,b) for (int i = a; i <= b; i++)
#define debug(i) cout << i << endl;
#define debugarr(a) for(auto i : a) cout << i << " ";

#define lli long long
#define vi vector<int>
#define vli vector<li>
#define vlli vector<lli>
#define pi pair<int,int>
#define pli pair<li, li>
#define vpi vector<pi>
#define gcd __gcd

using namespace std;

int main() {

    ios_base::sync_with_stdio(false);


    lli a, b, c, d;

    cin >> a >> b >> c >> d;

    lli divsC = b/c - (a-1)/c;
    lli divsD = b/d - (a-1)/d;

    lli ans = (b-a+1) - divsC - divsD;
    lli mmc = (c * d) / gcd(c, d);

    lli k = a + a % mmc;
    if(k <= b) {
        ans += b/mmc - (a-1)/mmc;
    }
    cout << ans << endl;

}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(void) {

	char S[6];

	scanf("%s",S);


	if(S[2]==S[3] && S[4]==S[5]){
		puts("Yes");
	}

	else{
		puts("No");
	}

	return 0;
}



Measured memory_bytes: 128
import java.util.*;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    String s = sc.next();
    String k = s.substring(0,n/2);
    String l = s.substring(n/2,n);


    if (k.equals(l)) {
      System.out.println("Yes");
    } else {
      System.out.println("No");
    }

  }

}


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

int main(){
    string S;
    cin >> S;
    int price = 700;
   for (int i; i < 3; i++){
        if (S[i] == 'o'){
            price = price + 100;
        }
    }
    cout << price << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int C[101],a,b,i;
int main()
{
	for(;~scanf("%d%d",&a,&b);)
	{
		if(a+b)
			C[a]++,C[b]++;
		else
		{
			for(i=3;i<=100;i++)
				if(C[i]%2)
					break;
			puts(i==101&&C[1]%2&&C[2]%2?"OK":"NG");
			memset(C,0,sizeof(C));
		}
	}
	return 0;
}

Measured memory_bytes: 584
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
template<class T> using vc = vector<T>;
template<class T> using vvc = vector<vector<T>>;

#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define repr(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repe(i, l, r) for (ll i = (l); i < (r); i++)
#define reper(i, l, r) for (ll i = (r)-1; i >= (l); i--)
#define repa(i,n) for (auto& i: n)

template<class T> inline bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
void init() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(15);}

#ifdef DEBUG
template <class T, class N> void verr(const T& a, const N& n) { rep(i, n) cerr << a[i] << " "; cerr << "\n" << flush; }
ll dbgt = 1; void err() { cerr << "passed " << dbgt++ << "\n" << flush; }
template<class H, class... T> void err(H&& h,T&&... t){ cerr<< h << (sizeof...(t)?" ":"\n") << flush; if(sizeof...(t)>0) err(forward<T>(t)...); }
#endif

const ll INF = 4e18;
const ld EPS = 1e-11;
const ld PI = acos(-1.0L);
// const ll MOD = 1e9 + 7;
const ll MOD = 998244353;
//--------------------------------------------------------------------------------//
ll A,B,C,D;
ll memo[3001][3001];

ll rec(ll a, ll b){
    if (memo[a][b]) return memo[a][b];
    ll ret = 0;

    if (a > A) ret += rec(a - 1, b) * (b) % MOD;
    if (b > B) ret += rec(a, b - 1) * (a) % MOD;
    if (a > A and b > B) ret -= rec(a - 1, b - 1) * (a - 1) * (b - 1) % MOD;
    ret = (MOD + ret) % MOD;
    memo[a][b] = ret;

    return ret;
}

int main() {
    init();
    cin >> A >> B >> C >> D;

    memo[A][B] = 1;
    cout << rec(C, D)%MOD << endl;

}

Measured memory_bytes: 74272
N, M = gets.split.map &:to_i
h = (N+M).times.map{[]}
$<.each_with_index{|s, i|
  _, *l = s.split.map &:to_i
  h[i] = l.map{|k|N+k-1}
  l.each{|k| h[N+k-1] << i }
}

visited = h.map{|k|
  k.empty? ? true : false
}

dfs = ->pos, lv = 0{
  visited[pos] = true
  h[pos].each{|to|
    next if visited[to]
    if lv > 100
      Fiber.new { dfs[to] }.resume
    else
      dfs[to, lv+1]
    end
  }
}
dfs[0]
puts visited.all? ? :YES : :NO


Measured memory_bytes: 88060
import sys


def input():
    return sys.stdin.readline().strip()


N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))

pos = A[1]
path = [1]
visited = {1}
cycle_start = -1
for _ in range(N):
    if pos in visited:
        cycle_start = pos
        break
    visited.add(pos)
    path.append(pos)
    pos = A[pos]

if cycle_start > 0:
    cycle_start_idx = path.index(cycle_start)
    acyclic_path = path[:cycle_start_idx]
    cyclic_path = path[cycle_start_idx:]
    if K < len(acyclic_path):
        print(acyclic_path[K])
    else:
        print(cyclic_path[(K - len(acyclic_path)) % len(cyclic_path)])
else:
    print(path[K])


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

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

    priority_queue<int> a;
    for(int i = 0; i < n; i++) {
        int tmp;
        cin >> tmp;
        a.push(tmp);
    }

    int aSum = 0, bSum = 0;
    for(int i = 0; !a.empty(); i++) {
        if(i % 2 == 0) {
            aSum += a.top();
        } else {
            bSum += a.top();
        }
        a.pop();
    }
    
    cout << aSum - bSum << endl;
    
    return 0;
}

Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
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;
}
typedef long long int ll;

#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define endl "\n"
const double EPS = 1e-7;
const int INF = 1 << 30;
const ll LLINF = 1LL << 60;
const double PI = acos(-1);
const int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

//-------------------------------------

struct UnionFind {
    vector<ll> par;

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

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

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

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

    ll size(ll x) { return -par[root(x)]; }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n, m;
    cin >> n >> m;
    vector<ll> a(m), b(m);
    for(int i = 0; i < m; i++) {
        cin >> a[i] >> b[i];
        a[i]--;
        b[i]--;
    }
    vector<ll> ans;
    UnionFind uf(n);
    ll res = n * (n - 1) / 2;
    for(ll i = m - 1; i >= 0; i--) {
        ans.emplace_back(res);
        if(uf.issame(a[i], b[i])) {
            continue;
        }
        res -= uf.size(a[i]) * uf.size(b[i]);
        uf.merge(a[i], b[i]);
    }
    reverse(ALL(ans));
    for(auto i : ans) {
        cout << i << endl;
    }
}

Measured memory_bytes: 4596
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 int K;
 string S,M;
 cin >> K >> S;
  if(S.size()<=K)
    cout << S << endl;
  if(S.size()>K){
    M=S.substr(0,K);
    cout << M+"..." << endl;
  }
}

Measured memory_bytes: 3628
//aising2019_b.cpp
//Sat Jan 12 20:59:55 2019

#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#define INTINF 2147483647
#define LLINF 9223372036854775807
using namespace std;
using ll=long long;
typedef pair<int,int> P;

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

	int p[n];
	int range[3];
	fill(range,range+3,0);
	for (int i=0;i<n;i++){
		cin >> p[i];
		if (p[i]<=a){
			range[0]++;
		}else if (p[i]<=b){
			range[1]++;
		}else{
			range[2]++;
		}
	}

	int ans = min(range[0],range[1]);
	ans = min(range[2],ans);

	cout << ans << endl;

}

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

int main() {
	string s;
	cin >> s;
	if (s[0] == s[1] || s[1] == s[2] || s[2] == s[3]) cout << "Bad" << endl;
	else cout << "Good" << endl;


}

Measured memory_bytes: 256
N, Q = map(int, input().split())
s = input()

X = []
for i in range(Q):
    t, d = input().split()
    if d == 'L':
        X.append([t, -1])
    else:
        X.append([t, 1])
        
def check(m):
    i = m
    for x in X:
        if x[0] == s[i]:
            i += x[1]
            if i < 0:
                return -1
            if i >= N:
                return 1
    return 0

L, R = -1, N
while R - L > 1:
    M = (L + R) // 2
    if check(M) < 0:
        L = M
    else:
        R = M  
A = L

L, R = -1, N
while R - L > 1:
    M = (L + R) // 2
    if check(M) > 0:
        R = M
    else:
        L = M
B = R

print(B - A - 1)

Measured memory_bytes: 25688
/* Author: Jason L.(int3xccATgmailDOTcom), Sat Jun  3 10:31:07 CST 2017 */
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pll = pair<ll, ll>; using dd = long double;
//=========================================================================
namespace {
static bool constexpr dbg =
#ifdef INT3XCC_DEBUG
        1;
#else
        0;
#endif
#define Dprintf(fmt, ...) do{if(dbg) printf(fmt, ##__VA_ARGS__);}while(0)
#define REP0(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define REP1(i, n) for (ll i = 1; i <= (ll)(n); ++i)
//=========================================================================
ll constexpr N = 3.1e5;
ll n, res, x[N], l[N], r[N];
//=========================================================================
void init() {
    cin>>n; REP1(i, 3*n) cin>>x[i];
    priority_queue<ll, vector<ll>, greater<ll>> pql;
    ll sum = 0;
    REP1(i, 3*n) {
        sum += x[i];
        pql.push(x[i]);
        if (pql.size() > n) {
            sum -= pql.top();
            pql.pop();
        }
        l[i] = sum;
    }
    priority_queue<ll> pqr;
    sum = 0;
    for (ll i = 3*n; i >= 1; --i) {
        sum += x[i];
        pqr.push(x[i]);
        if (pqr.size() > n) {
            sum -= pqr.top();
            pqr.pop();
        }
        r[i] = sum;
    }
    res = LONG_LONG_MIN;
    for (ll i = n; i <= 2*n; ++i) res = max(res, l[i]-r[i+1]);
    cout<<res;
}
void solve() {
}}
//=========================================================================
int main() {
    if (!dbg) { std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);}
    cout<<fixed<<setprecision(20); init(); solve(); return 0;
}


Measured memory_bytes: 9204
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n);i++)
#define sz(x) int(x.size())
typedef long long ll;
typedef pair<int,int> P;
constexpr int INF = 2e9;

int main(){ 
  int n;
  ll k;
  cin >> n >> k;
  vector<int> a(n);
  rep(i,n) cin >> a[i], a[i]--;
  int cnt = 0;
  vector<bool> vis(n, false);
  vector<int> b(n, 0);
  int i = 0;
  
  while (!vis[i]) {
    vis[i] = true;
    b[i] = cnt;
    if (cnt == k) {
      cout << i + 1 << endl;
      return 0;
    }
    i = a[i];
    cnt++;
  }
  
  int d = b[i];
  cnt = 1;
  int j = a[i];
  vector<int> c(n, -1);
  c[i] = 0;
  while (j != i) {
    c[j] = cnt;
    cnt++;
    j = a[j];
  }
  
  ll res = (k - d) % cnt;
  for (int i = 0; i < n; i++) {
    if (c[i] == res) {
      cout << i + 1 << endl;
      return 0;
    }
  }
  return 0;
} 

Measured memory_bytes: 5636
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<string>
#define rep(i,N) for(int i=0;i<N;i++)

long long  INF=1000000000000000000;
long long mod=1000000007;
using namespace std;

int main(){
vector<int> a(3);
rep(i,3)cin>>a[i];

sort(a.begin(),a.end());
int ans=0;
rep(i,2){
    ans+=abs(a[i+1]-a[i]);
}
cout<<ans<<endl;
 return 0;
}
/*
1 6 3

5

11 5 5

6

100 100 100

0
*/


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

using namespace std;

#define MAX_N 10
#define INF 1e9
typedef pair<int,string> P;

int N,bit;
string s[MAX_N];
string dp[1<<MAX_N][MAX_N];
vector<P> G[MAX_N];

void init(){
  bit = 0;
  for(int i = 0 ; i < (1<<N) ; i++){
    for(int j = 0 ; j < N ; j++){
      dp[i][j] = "#";
    }
  }
}

string cat(const string &a,const string &b){
  int l1 = a.size(),l2 = b.size();
  for(int i = min(l1,l2) ; i >= 0 ; i--){
    string suba = a.substr(l1-i,i);
    string subb = b.substr(0,i);
    if(suba == subb){
      return a + b.substr(i);
    }
  }
}

void overlap(int a,int b){
  string s1 = s[a], s2 = s[b];
  if(s2.find(s1) != string::npos &&
     s1.find(s2) == string::npos){
    bit |= (1<<a);
  }
  if(s1.find(s2) != string::npos &&
     s2.find(s1) == string::npos){
    bit |= (1<<b);
  }
}

string solve(int S,int v){
  if(S == (1<<N)-1){
    return s[v];
  }
  if(dp[S][v] != "#"){
    return dp[S][v];
  }
  string res = "#";
  for(int i = 0 ; i < N ; i++){
    if((S >> i) & 1) continue;
    string next = cat(s[v],solve(S|(1<<i),i));
    if(res == "#"){
      res = next;
    }else{
      if(next.size() < res.size()){
        res = next;
      }else if(next.size() == res.size() && next < res){
        res = next;
      }
    }
  }
  return dp[S][v] = res;
}

int main(){
  while(cin >> N, N > 0){
    init();
    for(int i = 0 ; i < N ; i++){
      cin >> s[i];
    }
    if(N == 1){
      cout << s[0] << endl;
      continue;
    }
    for(int i = 0 ; i < N ; i++){
      for(int j = 0 ; j < N ; j++){
        if(i == j) continue;
        overlap(i,j);
      }
    }
    string res = "#";
    for(int i = 0 ; i < N ; i++){
      if((bit >> i) & 1) continue;
      string r = solve(bit|(1<<i),i);
      if(res == "#"){
        res = r;
      }else{
        if(r.size() < res.size()){
          res = r;
        }else if(r.size() == res.size() && r < res){
          res = r;
        }
      }
    }
    cout << res << endl;
  }
  return 0;
}

Measured memory_bytes: 2060
import sys
from collections import deque
K = int(sys.stdin.readline().rstrip())
A = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
d = [-1, 0, 1]

for i in range(K):
    N = str(A.popleft())
    for i in d:
        if 0 <= int(N[-1]) + i <= 9:
            new = N + str(int(N[-1]) + i)
            A.append(int(new))
print(N)

Measured memory_bytes: 10884
#include<iostream>

using namespace std;

int main(void)
{
	int n,k;
	cin >> n >> k;
	long long x[n],y[n];
	for(int i=1;i<=n;i++)
		cin >> x[i-1] >> y[i-1];
	
	long long ans = 9000000000000000000;

	for(int i=1;i<=n;i++)
	{
	for(int i2=1;i2<=n;i2++)
	{
		for(int j=1;j<=n;j++)
		{
		for(int j2=1;j2<=n;j2++)
		{
			if(i==j)break;
			int count=0;
			for(int l=1;l<=n;l++)
			{
				if(((x[i-1]<=x[l-1] && x[l-1]<=x[j-1]) || (x[j-1]<=x[l-1] && x[l-1]<=x[i-1])) && ((y[i2-1]<=y[l-1] && y[l-1]<=y[j2-1]) || (y[j2-1]<=y[l-1] && y[l-1]<=y[i2-1])))count++;
			}
			if(count>=k)
				ans=min(ans,abs(x[i-1]-x[j-1])*abs(y[i2-1]-y[j2-1]));
		}
		}
	}
	}

	cout << ans << endl;
}

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

using namespace std;

int main() {
    int A, B;

    cin >> A >> B;

    if (A % 3 == 0) {
        cout << "Possible" << endl;
        return 0;
    } else if (B % 3 == 0) {
        cout << "Possible" << endl;
        return 0;
    } else if ((A + B) % 3 == 0) {
        cout << "Possible" << endl;
        return 0;
    }

    cout << "Impossible" << endl;
    return 0;
}

Measured memory_bytes: 256
N=int(input())
L=[int(i) for i in input().split()]
ans=0
for i in range(N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            x=L[i]+L[j]-L[k]
            y=L[j]+L[k]-L[i]
            z=L[k]+L[i]-L[j]
            if min(x,y,z)>0 and len({L[i],L[j],L[k]})==3:
                ans+=1
print(ans)


Measured memory_bytes: 68940
from sys import stdin

n,m = [int(x) for x in stdin.readline().rstrip().split()]
a = list(map(int,stdin.readline().rstrip().split()))
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(m)]
a.sort()
li.sort(key=lambda x:(x[1]*(-1),x[0]*(-1)))
lin = []
frag = 0
while frag == 0:
    point = 0
    for i in li:
        lin += [i[1]]*i[0]
        point += i[0]
        if point > n:
            frag = 1
            break
    frag = 1
if len(lin) <= n:
    lin += [0]*(n-len(lin))
else:
    lin = lin[:n]
count = 0
for i in range(n):
    if lin[i] > a[i]:
        count += lin[i]
    else:
        count += a[i]
print(count)

Measured memory_bytes: 46784
#include<iostream>
#include<cstdio>


using namespace std;

string bit[12] = {
  "0111111", /*0*/
  "0000110", /*1*/
  "1011011", /*2*/
  "1001111", /*3*/
  "1100110", /*4*/
  "1101101", /*5*/
  "1111101", /*6*/
  "0100111", /*7*/ 
  "1111111", /*8*/
  "1101111", /*9*/
  "0000000"  /*pre*/
};





int main(){
  int n,in;
  while(true){
    cin >> n;
    if(n == -1)break;
    int pre = 10;
    for(int i=0;i<n;i++){   
      cin >> in;
      for(int i=0;i<7;i++){
	if(bit[pre][i] != bit[in][i]){
	  cout << '1';
	}
	else cout << '0';
      }
      cout << endl;
      pre = in;
    }
  }
  return 0;
}

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

int main() {
    int a,b,c,ans=0;
    cin>>a>>b>>c;
    for(int i=1;c>0;i++){
        if(i%7==0)
            c-=b;
        c-=a;
        ans=i;
    }
    cout<<ans<<endl;
    return 0;
}




Measured memory_bytes: 3108
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i) 
#define PI acos(-1)

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

using card = pair<char, int>;

int partition(vector<card>& as, int p, int r, bool& flag) {
    card x = as[r];
    vector<card> right;
    int i = p - 1;
    for (int j = p; j < r; ++j) {
        if (as[j].second <= x.second) {
            i++;
            swap(as[i], as[j]);
        }
        else right.push_back(as[j]);
    }
    swap(as[i + 1], as[r]);
    rep(j, r - i - 1) flag &= (as[i + 2 + j] == right[j]);
    return i + 1;
}

bool quickSort(vector<card>& A, int p, int r) {
    bool flag = true;
    if (p < r) {
        int q = partition(A, p, r, flag);
        flag &= quickSort(A, p, q - 1);
        flag &= quickSort(A, q + 1, r);
    }
    return flag;
}

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

    int n;
    cin>>n;
    vector<card> deck(n);
    rep(i, n) cin>>deck[i].first>>deck[i].second;
    
    bool ans = true;
    ans = quickSort(deck, 0, n - 1);
    if (ans) cout<<"Stable"<<endl;
    else cout<<"Not stable"<<endl;
    rep(i, n) cout<<deck[i].first<<" "<<deck[i].second<<endl;
}


Measured memory_bytes: 4700
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <string>
#include <cmath>
#include <complex>
#include <numeric>
#include <cassert>

#include <vector>
#include <array>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <utility>

#define int64 long long
#define uint64 unsigned long long
#define PI 3.1415926535897932384626433832795
using namespace std;

int main()
{
	int64 nn, kk, fuko = 0;
	cin >> nn >> kk;
	string ss;
	cin >> ss;
	if(ss[0] == 'L')
	{
		fuko++;
	}
	for(int64 ii = 1;ii < nn;ii++)
	{
		if(ss[ii - 1] == 'R' && ss[ii] == 'L')
		{
			fuko += 2;
		}
	}
	if(ss[nn - 1] == 'R')
	{
		fuko++;
	}
	for(int64 ii = 0;ii < kk;ii++)
	{
		fuko -= 2;
		if(fuko <= 1)
		{
			cout << (nn - 1) << endl;
			return 0;
		}
	}
	cout << (nn - fuko) << endl;
	return 0;
}


Measured memory_bytes: 3724