akhauriyash/Code-Regression huggingface dataset:
# https://atcoder.jp/contests/abc102/tasks/arc100_a
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

def main():
    N = int(input())
    ab = [tuple(map(int, input().split())) for _ in range(N-1)]

    graph = [set() for _ in range(N+1)]
    for a, b in ab:
        graph[a].add(b)
        graph[b].add(a)

    d = deque()
    d.append(1)

    ans = [-1] * (N+1)

    parent = [-1] * (N+1)
    parent[1] = 1

    while d:
        p = d.popleft()
        c = 0
        for g in graph[p]:
            if parent[g] > 0 or g == parent[g]:
                continue
            c += 1
            if c == ans[p]:
                c += 1
            ans[g] = c

            parent[g] = p
            d.append(g)

    print(max(ans))
    print('\n'.join([str(ans[b]) for _, b in ab]))

if __name__ == '__main__':
    main()


Measured memory_bytes: 49616
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define pii pair<int,int>
#define pll pair<long long, long long>
#define rep(i,l,r) for(int i = l;i<r;i++)

#define SSTR( x ) static_cast< std::ostringstream & >( \
        ( std::ostringstream() << std::dec << x ) ).str()

#define fastout  ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
using namespace __gnu_pbds;

typedef tree<pll,null_type,less<pll>,rb_tree_tag,tree_order_statistics_node_update> order_set;

const int INF = (int)1e9 + 7;
const long long LLINF = (long long)1e18 + 7;

int main() {
    int n;
    cin >> n;
    for (int c = 0; c < 100; c++) {
        int tp = n - c * 4;
        if (tp >= 0) {
            if (tp % 7 == 0) {
                cout << "Yes";
                return 0;
            }
        }
    }
    cout << "No";
}


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

using namespace std;

int main(){
	string a;
	cin >> a;
	int b = 700;
	for (int i = 0; i < a.size(); i++) {
	
		if (a[i] == 'o') {
			b+= 100;
		}
	}
	cout << b << endl;
}

Measured memory_bytes: 3132
#include<bits/stdc++.h>
#define ll long long int
#define M 1000000007
using namespace std;
ll n,t;

int main(){
      ios_base::sync_with_stdio(false); cin.tie(NULL);
      cin>>n;
      ll a[n],ans=1e10;
      for(int i=0;i<n;i++)
      {
        cin>>a[i];
      }
      for(int x=0;x<=100;x++)
      {
        ll sum=0;
        for(int i=0;i<n;i++)
        {
          sum+=(a[i]-x)*(a[i]-x);
        }
        ans=min(ans,sum);
      }
      cout<<ans;
}

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

int main() {
    ll L[87];
    L[0] = 2, L[1] = 1;
    for (int i = 2; i <= 86; i++) {
        L[i] = L[i-1] + L[i-2];
    }
    int n;
    cin >> n;
    cout << L[n] << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <functional>
#include <cassert>
#include <utility>
#include <stack>
#include <queue>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,n1,n2) for(int i=n1;i<n2;i++)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef pair<int,int> Pi;
typedef long long int ll;
const int INF=(ll)(1<<30)-1;
const ll INFl=(ll)9223372036854775807;
const int MAX=10000;
const ll MOD=(ll)1e9+7;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a, b)*b;}


int main(){
	int a,b,t;
	cin>>a>>b>>t;
	int ans=t/a;
	ans=ans*b;
	cout<<ans<<endl;
	return 0;
}
	

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define a11111111 using namespace std;
#define a11111112 int n,m,s,a[1000][1000],used[1000][1001],p[1000];
#define a11111113 int main(){
#define a11111114 cin>>n>>m>>s;
#define a11111115 map<int,int> mp;
#define a11111116 int sm=0;
#define a11111117 for(int k=1;k<=n;k++)
#define a11111118 for(int i=1;i<=m;i++){
#define a11111119 a[k][i]=0;
#define a11111120 char ch;
#define a11111121 cin>>ch;
#define a11111122 if(ch=='#'){
#define a11111123 p[k]++;
#define a11111124 sm++;
#define a11111125 a[k][i]=1;
#define a11111126 }
#define a11111128 int u=1;
#define a11111129 for(int k=1;k<=n;k++){
#define a11111130 int t=0;
#define a11111132 if(a[k][i]==1){
#define a11111133 t++;
#define a11111134 if(mp[u]==1){
#define a11111135 u++;
#define a11111136 mp[u]++;
#define a11111138 else{
#define a11111142 used[k][i]=u;
#define a11111144 if(t!=0)
#define a11111148 int j=k;
#define a11111149 while(j<n){
#define a11111150 if(p[j]!=0)
#define a11111151 break;
#define a11111152 else j++;
#define a11111154 if(p[j]==0){
#define a11111155 while(j>0){
#define a11111158 else j--;
#define a11111161 for(int i=1;i<=m;i++)
#define a11111162 cout<<used[j][i]<<' ';
#define a11111163 cout<<endl;
#define a11111165 return 0;
a11111111
a11111112
a11111113
a11111114
a11111115
a11111116
a11111117
a11111118
a11111119
a11111120
a11111121
a11111122
a11111123
a11111124
a11111125
a11111126
a11111126
a11111128
a11111129
a11111130
a11111118
a11111132
a11111133
a11111134
a11111135
a11111136
a11111126
a11111138
a11111136
a11111126
a11111126
a11111142
a11111126
a11111144
a11111135
a11111126
a11111129
a11111148
a11111149
a11111150
a11111151
a11111152
a11111126
a11111154
a11111155
a11111150
a11111151
a11111158
a11111126
a11111126
a11111161
a11111162
a11111163
a11111126
a11111165
a11111126


Measured memory_bytes: 10240
a = []
while True:
    try:
        n = input()
        n1 = n.lower()
        v = list(n1)
        a += v
    except:
        break
b = len(a)
d = []
for i in range(b):
        c = ord(a[i])
        d.append(c)
for k in range(97,123):
    e = d.count(k)
    if e == 0:
        print(f'{chr(k)} : 0')
    else:
        print(f'{chr(k)} : {e}')


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

int main() {
  int N;
  cin >> N;
  for (auto i=0; i<N; i++) {
    int t[3];
    cin >> t[0] >> t[1] >> t[2];
    sort(t, t+3);
    cout << ( (t[0]*t[0] + t[1]*t[1] == t[2]*t[2]) ? "YES" : "NO" ) << endl;
  }
}

Measured memory_bytes: 1164
using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using System.Text;

class Program
{
    static void Main(string[] args)
    {
        // 入力
        var n = long.Parse(Console.ReadLine());
        long[] a = Console.ReadLine().Split().Select(long.Parse).ToArray();

        long[] sum = new long[n];
        sum[0] = a[0];
        for (long i = 1; i < n; i++)
        {
            sum[i] += a[i] + sum[i-1];
        }

        long ans = long.MaxValue;
        long s = 0;
        long t = 0;
        for (long i = 0; i < n-1; i++)
        {
            s = sum[i];
            t = sum[n-1]-sum[i];
            ans = Math.Min(ans,Math.Abs(s-t));
        }


        Console.WriteLine(ans);
    }
}


Measured memory_bytes: 37624
S=input()
n=len(S)
if n==2:
  if S=='hi':
    print('Yes')
  else:
    print('No')
elif n==4:
  if S=='hihi':
    print('Yes')
  else:
    print('No')
elif n==6:
  if S=='hihihi':
    print('Yes')
  else:
    print('No')
elif n==8:
  if S=='hihihihi':
    print('Yes')
  else:
    print('No')
elif n==10:
  if S=='hihihihihi':
    print('Yes')
  else:
    print('No')
else:
  print('No')

Measured memory_bytes: 3064
# coding:utf-8
import math
array = map(float,raw_input().split())
x1 = array[0]
y1 = array[1]
x2 = array[2]
y2 = array[3]
answer = math.sqrt(math.pow(x2 - x1,2) + math.pow(y2 - y1,2))
print answer



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

using ll = long long;
using pii = pair<int, int>;
template <class T>
using V = vector<T>;
template <class T>
using VV = V<V<T>>;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i, n) rep2(i, 0, n)
#define rep2(i, m, n) for (int i = m; i < (n); i++)
#define per(i, b) per2(i, 0, b)
#define per2(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define ALL(c) (c).begin(), (c).end()

constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }

template <class T, class U>
void chmin(T& t, const U& u) {
    if (t > u) t = u;
}
template <class T, class U>
void chmax(T& t, const U& u) {
    if (t < u) t = u;
}

template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os << "(" << p.first << "," << p.second << ")";
    return os;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "{";
    rep(i, v.size()) {
        if (i) os << ",";
        os << v[i];
    }
    os << "}";
    return os;
}

#ifdef LOCAL
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << H;
    debug_out(T...);
}
#define debug(...) \
    cerr << __LINE__ << " [" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl
#else
#define debug(...) (void(0))
#define dump(x) (void(0))
#endif

int main() {
    int N;
    cin >> N;
    ll ans = 0;
    rep(i, N) { ans += ll(i + 1) * (N - i); }

    rep(i, N - 1) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        if (a > b) swap(a, b);
        ans -= ll(a + 1) * (N - b);
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3616
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		new Main().solveA();
		//		new Main().solveB();
		//		new Main().solveC();
		//		new Main().solveD();
	}

	private void solveA() {
		Scanner scanner = null;
		int a = 0;
		int b = 0;

		try {
			scanner = new Scanner(System.in);
			a = scanner.nextInt();
			b = scanner.nextInt();
			if (a > 8 || b > 8) {
				System.out.println(":(");
			} else {
				System.out.println("Yay!");
			}
		} finally {
			if (scanner != null) {
				scanner.close();
			}
		}
	}

	private void solveB() {
		Scanner scanner = null;
		int lineAB = 0;
		int lineBC = 0;
		int lineCA = 0;

		try {
			scanner = new Scanner(System.in);
			lineAB = scanner.nextInt();
			lineBC = scanner.nextInt();
			lineCA = scanner.nextInt();

		} finally {
			if (scanner != null) {
				scanner.close();
			}
		}
	}

	private void solveC() {
		Scanner scanner = null;
		int lineAB = 0;
		int lineBC = 0;
		int lineCA = 0;

		try {
			scanner = new Scanner(System.in);
			lineAB = scanner.nextInt();
			lineBC = scanner.nextInt();
			lineCA = scanner.nextInt();

		} finally {
			if (scanner != null) {
				scanner.close();
			}
		}
	}

	private void solveD() {
		Scanner scanner = null;
		int lineAB = 0;
		int lineBC = 0;
		int lineCA = 0;

		try {
			scanner = new Scanner(System.in);
			lineAB = scanner.nextInt();
			lineBC = scanner.nextInt();
			lineCA = scanner.nextInt();

		} finally {
			if (scanner != null) {
				scanner.close();
			}
		}
	}
}

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

#define For(i, j, k) for (int i = j; i <= k; ++ i)
#define Forr(i, j, k) for (int i = j; i >= k; -- i)

using namespace std;

inline void File() {
	freopen("D.in", "r", stdin);
	freopen("D.out", "w", stdout);
}

int L, cnt, h, t;
struct edge { int u, v, w; } E[100];

inline void add(int x, int y, int z) {
	E[++ cnt].u = x, E[cnt].v = y, E[cnt].w = z;
}

int main() {

	cin >> L;
	for (int tt = L; tt; ++ h, tt >>= 1);

	For(i, 1, h - 1) {
		add(i, i + 1, 1 << h - i - 1);
		add(i, i + 1, 0);
	}

	t = 1 << h - 1;
	Forr(i, h - 1, 1) if (L >> (i - 1) & 1) add(1, h - i + 1, t), t += 1 << i - 1;

	cout << h << ' ' << cnt << endl;
	For(i, 1, cnt) printf("%d %d %d\n", E[i].u, E[i].v, E[i].w);

	return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <string.h>
#include <vector>
using namespace std;

#define ll long long
#define INF (1 << 30)
#define INFLL (1LL << 60)

#define FOR(i,a,b) for(ll i = (a);i<(b);i++)
#define REP(i,a) FOR(i,0,(a))
#define MP make_pair

int n, m, ans;
pair<int, int> edge[40];

bool vec_find(vector<int> vec, int n) {
    vector<int>::iterator cIter = find(vec.begin(), vec.end(), n);

    return cIter != vec.end();
}

void check(int num, vector<int> vec) {
    if (num == n - 1) {
        ans++;
        return;
    }

    REP(i, m) {
        if (edge[i].first == vec[num] && !vec_find(vec, edge[i].second)) {
            vector<int> vec1 = vec;
            vec1.push_back(edge[i].second);
            check(num + 1, vec1);
        }
        if (edge[i].second == vec[num] && !vec_find(vec, edge[i].first)) {
            vector<int> vec2 = vec;
            vec2.push_back(edge[i].first);
            check(num + 1, vec2);
        }
    }

}

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

    REP(i, m) {
        int a, b;
        cin >> a >> b;
        edge[i].first = a;
        edge[i].second = b;
    }

    ans = 0;
    vector<int> vec;
    vec.push_back(1);
    check(0, vec);

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
n = int(input())
a = [int(input()) for i in range(n)]

if a[0]!=0:
    print(-1)
    exit()

ans = a[-1]
x = a[-1]
for i in range(n-1):
    if a[-i-2] > x-1:
        ans += a[-i-2]
        x = a[-i-2]
    elif a[-i-2]==x-1:
        x -=1
    else:
        print(-1)
        exit()

print(ans)

Measured memory_bytes: 57772
#include <bits/stdc++.h>
#define rep(i,x,n) for(int i=x; i<(int)(n); i++)
#define rep_eq(i,x,n) for(int i=x; i<=(int)(n); i++)
using namespace std;

typedef long long ll;

int main() {
  string S; cin >>S;
  char temp=S[0];
  int Ans=0;
  rep(i,1,S.size()) {
    if (temp!=S[i]) {
      Ans++;
      temp=S[i];
    }
  }
  cout <<Ans <<endl;
  return 0;
}


Measured memory_bytes: 512
n,m=map(int,input().split())
l=[]
for _ in range(n):l.append(0)
wa=0
for i in range(m):
    p,s=map(str,input().split())
    if l[int(p)-1]==-1:continue
    elif s=="AC":
        wa+=l[int(p)-1]
        l[int(p)-1]=-1
    else: l[int(p)-1]+=1
print(l.count(-1),wa)



Measured memory_bytes: 52640
import java.util.*;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int l;
		for(l=1; l<N; l++){
			N -= l;
		}
		if(N != l){
			System.out.println("No");
			System.out.flush();
			return;
		}
		System.out.println("Yes");
		System.out.println(l+1);
		int[][] answer = new int[l+1][l];
		int Index = 1;
		for(int i=0; i<=l; i++){
		StringBuilder string = new StringBuilder();
			string.append(l);
			int j=0;
			for(; j<i; j++){
				string.append(" ");
				string.append(answer[j][i-1]);
			}
			for(; j<l; j++){
				string.append(" ");
				string.append(answer[i][j]=Index++);
			}
			System.out.println(string.toString());
		}
		System.out.flush();
		return;
	}
}


Measured memory_bytes: 36108
#include <bits/stdc++.h>
 
using namespace std;
 
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define Eunique(v) v.erase(unique(all(v)),v.end())
#define pvec(v) rep(i,v.size()){cout << v[i] << " ";};cout<<endl;
#define pb push_back
#define pf push_front
#define mod 1e9+7
 
typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;

const double pi = acos(-1.0);
 
ll gcd(ll x, ll y) { return (y == 0) ? x : gcd(y, x % y); }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }

int main()
{
	ll n,h,w,a,b,ans=0;
	cin >> n >> h >> w;
	rep(i,n){
		cin >> a >> b;
		if(h<=a && w<=b) ans++;
	}
	cout << ans << endl;
	return 0;
}

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

int main() {
  int N, A[100] = {0};
  
  // input
  cin >> N;
  for(int n=0; n<N; n++)
  {
    cin >> A[n];
  }
  
  // カードを並び替え
  // 逆順にすること
  sort(A, A+N, greater<>());
  
  // Alice の回答 = 偶数の和  
  // Bob の回答 = 奇数の和
  int SumA = 0;
  int SumB = 0;
  for(int n=0; n<N; n+=2)
  {	SumA += A[n];
   	SumB += A[n+1];    
  }

  // 回答
  cout << (SumA - SumB) << endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>

#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define all(c) begin(c),end(c)

template<typename T1, typename T2>
inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }

template<typename T1, typename T2>
inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }

//改造
typedef long long int ll;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 1000000007


//ここから編集する
class Solve {
public:
    int N;
    int K;
    vector<ll> a;
    vector<ll> b;

    void input() {
        cin >> N >> K;
        a.resize(N);
        rep(i, 0, N) {
            cin >> a[i];
        }

        for (int i = 0; i < N; ++i) {
            ll tmp = 0;
            for (int j = i; j < N; ++j) {
                tmp += a[j];
                b.push_back(tmp);
            }
        }

        sort(all(b));
    }

    void solve() {
        input();

        vector<ll> survive;
        for (auto e : b) {
            survive.push_back(e);
        }
        //数字の下からpビット目
        ll ans = 0ll;
        for (int p = 40; p >= 0; --p) {
            vector<ll> next; //次の世代の生き残り
            ll tmp = ans;
            tmp |= (1ll << p);
            for (auto e : survive) {
                if ((e & tmp) == tmp) {
                    next.push_back(e);
                }
                if (next.size() >= K) {
                    ans |= 1ll << p;
                }
            }
        }

        cout << ans << endl;

    }
};


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

    Solve().solve();


    return 0;
}


Measured memory_bytes: 12396
#!/usr/bin/env python
# coding: utf-8

def ri():
    return int(input())

def rl():
    return list(input().split())

def rli():
    return list(map(int, input().split()))

def main():
    n, m = rli()
    switch = []
    for i in range(m):
        tmp = rli()
        k = tmp[0]
        ls = tmp[1:]
        switch.append(ls)
    lp = rli()
    ans = 0
    def check(mask):
        on_off = []
        for i in range(0, n):
            on_off.append(mask & (1 << i))
        for i in range(m):
            cnt = sum(1 for s in switch[i] if on_off[s-1])
            if cnt % 2 != lp[i]:
                return 0
        return 1
    ans = 0
    for i in range(1 << n):
        ans += check(i)
    print(ans)





if __name__ == '__main__':
    main()


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

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

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

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

bool is_prime(int x) {
  if (x <= 1) {
    return false;
  }
  for (int i=2; i*i < x; i++) {
    if (x%i == 0) {
      return false;
    }
  }
  return true;
}

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

  ll x;
  cin >> x;
  vector<ll> prime;
  for(ll i = 2; i <= 100003; ++i) {
    if (is_prime(i)) prime.push_back(i);
  }
  ll index = lower_bound(prime.begin(), prime.end(), x) - prime.begin();
  cout << prime[index] << endl;
  return 0;
}


Measured memory_bytes: 512
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
int n;
ll a[200020];
void solve(int l, int r, vector<ll> v[2][2]){
	if(l>r){
		for(int i=0; i<2; i++) for(int j=0; j<2; j++) v[i][j].push_back(0);
		return;
	}else if(l==r){
		for(int i=0; i<2; i++) for(int j=0; j<2; j++) v[i][j].push_back(0);
		v[1][1].push_back(a[l]);
		return;
	}else if(l+1==r){
		for(int i=0; i<2; i++) for(int j=0; j<2; j++) v[i][j].push_back(0);
		v[1][1].push_back(max(a[l], a[r]));
		v[1][0].push_back(a[l]);
		v[0][1].push_back(a[r]);
		return;
	}
	vector<ll> v1[2][2], v2[2][2];
	int m=(l+r)/2;
	solve(l, m, v1);
	solve(m+1, r, v2);
	v[0][0].resize(1+(r-l)/2);
	v[0][1].resize(1+(r-l+1)/2);
	v[1][0].resize(1+(r-l+1)/2);
	v[1][1].resize(1+(r-l+2)/2);
	for(int i=0; i<2; i++){
		for(int j=0; j<2; j++){
			for(int k=0; k<2; k++){
				int p=v1[i][k].size()-1, q=v2[k^1][j].size()-1;
				while(p>=0 && q>=0){
					v[i][j][p+q]=max(v[i][j][p+q], v1[i][k][p]+v2[k^1][j][q]);
					if(p==0 && q==0) break;
					else if(p==0) q--;
					else if(q==0) p--;
					else{
						if(v1[i][k][p-1]+v2[k^1][j][q]>v1[i][k][p]+v2[k^1][j][q-1]) p--;
						else q--;
					}
				}
			}
		}
	}
	return;
}
int main()
{
	scanf("%d", &n);
    const ll geta=1e9+7;
	for(int i=0; i<n; i++){
		scanf("%lld", &a[i]);
        a[i]+=geta;
	}
	vector<ll> ans[2][2];
	solve(0, n-1, ans);
	cout<<ans[1][1][n/2]-geta*(n/2)<<endl;
	return 0;
}


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

int main()
{
    char c[100001]={0};
    cin >> c;
    for(int i=1;i<100001;i=i+2) {
        if(c[i-1]!=0) cout << c[i-1];
    }
    cout << "\n";
    return 0;
}


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

// typedef
// -----------------------------------------------------------------------------
typedef long long ll;
typedef long double ld;

// container util
// -----------------------------------------------------------------------------
#define ALL(c)  (c).begin(),(c).end()
#define SZ(c) ((ll)(c).size())
#define MAX(c) *max_element(ALL(c))
#define MIN(c) *min_element(ALL(c))
#define SORT(c) sort((c).begin(),(c).end())

// repetition
// -----------------------------------------------------------------------------
#define FOR(i, a, b) for(ll i= (a); i < (ll)(b); ++i)
#define REP(i, n) FOR(i, 0, n)

// constant
// -----------------------------------------------------------------------------
const ll INF = 1e9;
const ll MOD = 1e9 + 7;
const double EPS = 1e-9;
const double PI = acos(-1.0);

// debug
// -----------------------------------------------------------------------------
#define DUMP(x)  cerr << #x << " = " << (x) << endl


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
    string S; cin >> S;
    if(count(S.begin(), S.end(), 'A') && count(S.begin(), S.end(), 'B')) {
        cout << "Yes" << "\n";
    } else {
        cout << "No" << "\n";
    }
}

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

#define endl ('\n')
#define all(x) (x).begin(),(x).end()

template<typename Type>
Type gcd(const Type a,const Type b){return(b==0)?a:gcd(b,a%b);}
template<typename Type>
Type lcm(const Type a,const Type b){return(a/gcd(a,b))*b;}

template<typename Type>
void sort(vector<Type>& v){
	sort(all(v));
}
template<typename Type>
void sortInv(vector<Type>& v){
	sort(all(v), greater<Type>());
}

int main(){
	int X,Y,A,B,C;
	cin >> X >> Y >> A >> B >> C;
	vector<int> p(A),q(B),r(C);
	for(int i=0;i<A;i++) cin >> p[i];
	for(int i=0;i<B;i++) cin >> q[i];
	for(int i=0;i<C;i++) cin >> r[i];
	sortInv(p);
	sortInv(q);

	vector<int> x(X+Y+C);
	for(int i=0;i<X;i++) x[i] = p[i];
	for(int i=0;i<Y;i++) x[X+i] = q[i];
	for(int i=0;i<C;i++) x[X+Y+i] = r[i];
	sortInv(x);
	ll ans=0;
	for(int i=0;i<X+Y;i++) ans+=x[i];
	cout << ans;
}

Measured memory_bytes: 2560
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#include <functional>
#include <stack>
#include <cassert>
#include <cctype>
#include <cstdlib>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define rep1(i,n) for(int i=1;i<=(n);++i)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define fs first
#define sc second
#define show(x) //cout << #x << " = " << x << endl;
typedef long long ll;
typedef pair<ll,ll> P;
ll mod=1e9+7;
#define showpair(p) //cout<<#p<<"  "<<p.fs<<" "<<p.sc<<endl
string s;
stack<P> st;
P lp_=P(-1,0),rp_=P(-2,0),and_=P(-3,0),or_=P(-4,0),not_=P(-5,0),e=P(1,1);
P calcnot(P p){
	bool rev=false;
	while(!st.empty()&&st.top()==not_) st.pop(),rev=!rev;
	if(!rev) return p;
	return P(p.sc,p.fs);
}
P calcand(P a,P b){
	P p=P(a.fs*b.fs%mod,(a.fs*b.sc+a.sc*b.fs+a.sc*b.sc)%mod);
	//cout<<"and";
	showpair(p);
	return p;
}
P calcor(P a,P b){
	P p=P((a.fs*b.fs+a.fs*b.sc+a.sc*b.fs)%mod,(a.sc*b.sc)%mod);
	//cout<<"or";
	showpair(p);
	return p;
}
int main(){
	cin>>s;
	s="("+s+")";
	int it=0;
	while(it<s.size()){
//		show(it);
//		show(s[it]);
		if(s[it]!='x'){
			if(s[it]=='(') st.push(lp_);
			if(s[it]==')'){
				P a=st.top();st.pop();
				P b=st.top();st.pop();
//				//cout<<a.fs<<" "<<a.sc<<endl;
//				//cout<<b.fs<<" "<<b.sc<<endl;
				if(b==lp_){
					st.push(calcnot(a));
//					//cout<<"ok";
				}else{
//					show(it);
					P c=st.top();st.pop();
					P d=st.top();st.pop();
//					showpair(c);
//					showpair(d);
					if(d==lp_){
//						//cout<<"here";
						if(b==and_){
							st.push(calcnot(calcand(c,a)));
						}else if(b==or_){
	//						//cout<<"ok";
							st.push(calcnot(calcor(c,a)));
						}else{
							assert(false);
						}
					}else{
						P f=st.top();st.pop();
						P g=st.top();st.pop();
						//cout<<"her";
						if(g!=lp_){
							P h=st.top();st.pop();
							show(it);
							showpair(h);
							showpair(g);
							showpair(f);
							showpair(d);
							showpair(c);
							showpair(b);
							showpair(a);
							exit(0);
						}
						st.push(calcnot(  calcor(f,calcand(c,a))  ));
					}
				}
			}
			if(s[it]=='&'){
				//cout<<"inand";
				show(it);
				P a=st.top();st.pop();
				P b=st.top();st.pop();
				if(b==lp_||b==or_){
					st.push(b);
					st.push(a);
					st.push(and_);
					//cout<<"here\n";
				}else{
					P c=st.top();st.pop();
					assert(b==and_);
					st.push(calcand(c,a));
					st.push(and_);
				}
			}
			if(s[it]=='|'){
				//cout<<"inor\n";
				show(it);
				P a=st.top();st.pop();
				P b=st.top();st.pop();
				if(b==lp_){
					show(it);
					st.push(b);
					st.push(a);
					st.push(or_);
					it++;
					continue;
				}else if(b==and_){
					P c=st.top();st.pop();
					st.push(calcand(c,a));
				}else if(b==or_){
					P c=st.top();st.pop();
					st.push(calcor(c,a));
				}else{
					assert(false);
				}
				continue;
			}
			if(s[it]=='~') st.push(not_);
			it++;
			continue;
		}
		it++;
		while(isdigit(s[it])) it++;
		bool rev=false;
		st.push(calcnot(e));
	}
	P p=st.top();
	show(st.size());
	cout<<p.fs<<endl;
}

Measured memory_bytes: 10176
#include <iostream>
#include <set>
#include <string>
#include <cstring>
using namespace std;

int t[26][26];

//ノードidからいくつのノードに移動可能か
//すでに探索済みのノードは通らない
int reachableNode(int id,bool *used){
  int res = 1;

  used[id] = true;
  for(int i=0;i<26;i++){
    if(t[id][i] > 0 && !used[i]){
      res += reachableNode(i,used);
    }
  }

  return res;
}

int main(void){
  int n;

  while(cin>>n && n){
    string s;
    int from,to;
    set<int> ap;

    memset(t,0,sizeof(t));

    for(int i=0;i<n;i++){
      cin>>s;
      from = s[0] - 'a';
      to = s[s.size()-1] - 'a';

      //自己ループ以外の辺はカウント
      if(from != to){
        t[from][to]++;
      }
      ap.insert(from);
      ap.insert(to);
    }

    //森が一つだけであるかの確認
    bool used[26];
    memset(used,0,sizeof(used));
    int count = reachableNode(from,used);
    if(count != ap.size()){
      cout<<"NG\n";
      continue;
    }

    //入次数と出次数が同じかどうかの確認
    set<int>::iterator i = ap.begin();
    for(;i!=ap.end();i++){
      int in=0,out=0;
      for(int j=0;j<26;j++){
        in += t[j][*i];
        out += t[*i][j];
      }
      if(in != out) break;
    }

    if(i == ap.end())cout<<"OK\n";
    else cout<<"NG\n";
  }

  return 0;
}

Measured memory_bytes: 920
alpha="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
count=[0 for i in range(26)]
test=""
while True:
    try:
        string=input()
        test+=string
    except:
        break

for i in range(len(test)):
    for j in range(26):
        if test[i]==alpha[j] or test[i]==alpha[j+26]:
            count[j]+=1
            break

for i in range(26):
    print("{} : {}".format(alpha[i],count[i]))


Measured memory_bytes: 5568
#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 <cctype> // isupper, islower, isdigit, toupper, tolower
#include <cmath>
#include <limits>
#include <list>
#define ALL(x) (x).begin(),(x).end()
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define int_INF 2147483647
#define pint_INF 2000000000
#define ll_INF 	9223372036854775807
#define MOD 1000000007
#define vi vector<int>
#define vvi vector<vector<int>>
#define vvll vector<vector<long long>>
#define vvc vector<vector<char>>
#define vll vector<long long>
#define pii pair<int,int>
#define vpii vector<pair<int,int>>
#define sysp system("PAUSE")
#define pno cout << "no" << endl
#define pyes cout << "yes" << endl
#define pYes cout << "Yes" << endl
#define pNo cout << "No" << endl
#define pNO cout << "NO" << endl
#define pYES cout << "YES" << endl
#define endl "\n"
#define pi 3.14159265358979
using namespace std;
using ll = long long;
class LargeNumber {
public:
	bool is_prime[1000000 + 13];// Up to 1e6 + 13
	vector<int> Prime_table;
public:
	vector<int> Eratosthenes(const int N = 277776) { // return primes up to N
		for (int i = 0; i <= N; i++)
		{
			is_prime[i] = true;
		}
		for (int i = 2; i <= N; i++)
		{
			if (is_prime[i])
			{
				for (int j = 2 * i; j <= N; j += i)
				{
					is_prime[j] = false;
				}
				if (i % 5 == 1) {
					Prime_table.emplace_back(i);
				}
			}
		}
		return Prime_table;
	}

	template<typename T>
	map<T, T> Factorization(T N) const {
		map<T, T> mp;
		if (N == 1) {
			return mp;
		}

		for (int i = 0; i < Prime_table.size(); i++) {
			while (N % Prime_table[i] == 0) {
				mp[Prime_table[i]]++;
				N /= Prime_table[i];
			}
		}

		if (N > 1) mp[N]++;

		return mp;
	}


	bool isPrime(long long x) {
		if (x == 0 || x == 1) {
			return false;
		}
		return is_prime[x];
	}
};

signed main() {
	int N; cin >> N;
	LargeNumber lg;
	vi prime_table = lg.Eratosthenes();
	for (int i = 0; i < N; i++) {
		cout << prime_table[i] << " ";
	}
	cout << endl;
}

Measured memory_bytes: 3856
#include<bits/stdc++.h>
using namespace std;
#define N 1111116

int n,t,a[N];

int read(){
	int x=0,f=1;char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-')  f=-f;
	for (;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
	return x*f;
}

bool check(int k){
	for (int i=1;i<=n-1;i++){
		if ((a[n-i]>=k)==(a[n-i+1]>=k))
		return a[n-i]>=k;
		if ((a[n+i]>=k)==(a[n+i-1]>=k))
		return a[n+i]>=k;
	}
	return (a[n]>=k)^(n%2==0);
}

int main(){
	n=read();
	for (int i=1;i<=2*n-1;i++) a[i]=read();
	for (int k=1<<17;k;k/=2)
		if (check(t+k)) t+=k;
	printf("%d\n",t);
	return 0;
}

Measured memory_bytes: 1152
#include<bits/stdc++.h>
using namespace std;
 
#define int long long 
#define ll long long 
#define pb push_back
#define mp make_pair
#define pii pair<ll,ll>
#define ff first
#define ss second
#define vi vector<ll>
#define mod 1000000007
#define MOD 1000000007
#define full(a) a.begin(),a.end()
#define inf INT_MAX
#define minf INT_MIN
#define dd double
#define fori(x,n) for(ll i=x;i<n;i++)
#define modd 998244353
#define umap unordered_map<ll,ll>
#define mmap map<ll,ll>

int32_t main() 
{ 
  
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif

    
 
       ll n;
       cin>>n;
       ll sum=0;
       ll cnt[100005]={0};
       fori(0,n){
        ll x;
        cin>>x;
        cnt[x]++;
        sum+=x;
       }
       ll q;
       cin>>q;
       while(q--){
        ll x,y;
        cin>>x>>y;
        sum =sum - cnt[x]*(x-y);
        cout<<sum<<"\n";
        cnt[y]+=cnt[x];
        cnt[x]=0;
       }
      
 

     
 
return 0;
}     

Measured memory_bytes: 4436
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<map>
#include<numeric>
#include<set>
#include<string>
#include<utility>
#include<vector>

#define rep(i, a, n)  for(int i=a; i<n; i++)
#define per(i, a, n)  for(int i=n-1; i>=a; i--)
#define all(x)  (x).begin(), (x).end()
#define MAX 1000000007
using namespace std;
typedef long long ll;

int main(){
  int n;  cin >> n;
  vector<int> vec(n);
  rep(i, 0, n)  cin >> vec[i];
  sort(all(vec));
  int sum = 0;
  rep(i, 0, n-1) sum+=vec[i];
  if(sum>vec.back())  cout << "Yes" << endl;
  else  cout << "No" << endl;
}

Measured memory_bytes: 256
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn solve(n: i32, y: i32) -> (i32, i32, i32) {
    for i in 0..n + 1 {
        for j in 0..n - i + 1 {
            if i * 10000 + j * 5000 + (n - i - j) * 1000 == y {
                return (i, j, n - i - j);
            }
        }
    }
    (-1, -1, -1)
}

fn main() {
    input!{
        n: i32,
        y: i32
    }
    let (a, b, c) = solve(n, y);
    println!("{} {} {}", a, b, c)
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using pi = pair<int, int>;

int main(){
	int n, l; 
	scanf("%d %d",&n,&l);
	vector<pair<int, vector<int>>> stk;
	lint dap = 0;
	for(int i=0; i<n; i++){
		int x; scanf("%d",&x);
		while(sz(stk) && stk.back().first < x){
			auto lev = stk.back().first;
			auto vec = stk.back().second;
			vector<int> nvec;
			stk.pop_back();
			if(sz(vec) < l){
				stk.clear();
				break;
			}
			for(int i=sz(vec)-l; i>=0; i-=l) nvec.push_back(vec[i]);
			reverse(all(nvec));
			if(sz(stk) && stk.back().first == lev + 1){
				int foo = stk.back().second.back();
				for(auto &j : nvec) stk.back().second.push_back(foo + j);
			}
			else{
				stk.emplace_back(lev + 1, nvec);
			}
		}
		dap += 1;
		if(sz(stk) && stk.back().first == x){
			int foo = stk.back().second.back();
			stk.back().second.push_back(foo + 1);
		}
		else{
			stk.emplace_back(x, vector<int>{1});
		}
		if(sz(stk.back().second) >= l) dap += stk.back().second[sz(stk.back().second) - l];
		int sum = sz(stk.back().second);
		int clvl = x;
		for(int j=sz(stk)-2; j>=0; j--){
			while(sum && clvl < stk[j].first){
				sum /= l;
				clvl++;
			}
			if(sum == 0) break;
			sum += sz(stk[j].second);
			if(sum >= l) dap += stk[j].second[min(sz(stk[j].second) - 1, sum - l)];
		}
	}
	printf("%lld\n", dap);
}


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

int main(){
  string s;
  cin >> s;
  if(s[0] != 'A'){
    cout << "WA";
    return 0;
  }
  int cntC = 0,n = s.length();
  for(int i = 2; i < n -1; i++){
    if(s[i] == 'C')cntC++;
  }
  if(cntC > 1 || cntC == 0){
    cout << "WA";
    return 0;
  }
  for(int i = 0; i < n; i++){
    if(s[i] == 'A' || s[i] == 'C') continue;
    if(s[i] - 65 + 1 >= 1 && s[i] - 65 + 1 <= 26){
      cout << "WA";
      return 0;
    }
  }
  cout << "AC";
  return 0;
}
  


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

using namespace std;

int main(void)
{
	int n, k;
	cin >> n >> k;
	int max = (n - 1) * (n - 2) / 2;
	if (k > max)
	{
		cout << -1 << endl;
	}
	else
	{
		cout << (n - 1) + (max - k) << endl;
		for (int i = 0; i < n - 1; ++i)
		{
			cout << 1 << " " << i + 2 << endl;
		}
		int it = max - k;
		int begin = 2, end = begin + 1;
		while (it > 0)
		{
			cout << begin << " " << end << endl;
			end++;
			if (end > n)
			{
				begin++;
				end = begin + 1;
			}
			it--;
		}
	}
	return 0;
}


Measured memory_bytes: 256
from collections import Counter


n = int(input())
v = list(map(int, input().split()))
a = Counter(v[::2]).most_common()
b = Counter(v[1::2]).most_common()

ans = 0

if a[0][1] > b[0][1]:
    ans += (n//2) - a[0][1]
    if a[0][0] == b[0][0]:
        if len(b) > 1:
            ans += (n//2) - b[1][1]
        else:
            ans += (n//2)
    else:
        ans += (n // 2) - b[0][1]
elif a[0][1] < b[0][1]:
    ans += (n // 2) - b[0][1]
    if a[0][0] == b[0][0]:
        if len(a) > 1:
            ans += (n // 2) - a[1][1]
        else:
            ans += (n // 2)
    else:
        ans += (n // 2) - a[0][1]
else:
    ans += (n // 2) - b[0][1]
    if a[0][0] == b[0][0]:
        if len(a) > 1:
            ans += (n // 2) - max(a[1][1], b[1][1])
        else:
            ans += (n // 2)
    else:
        ans += (n // 2) - a[0][1]

print(ans)


Measured memory_bytes: 95804
# frozen_string_literal: true

S_A, S_B, S_C = Array.new(3) { gets.chomp.chars }
turn = pred = 'a'

loop do
  unless turn
    puts pred.upcase
    exit
  end

  turn = case turn
         when 'a' then S_A.shift
         when 'b' then S_B.shift
         when 'c' then S_C.shift
         end
  pred = turn if turn
end

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

int main(){
	int N;
	cin >> N;
	int T[N+1];
	int tt = 0;
	rep(i,N) {
		cin >> T[i+1];
		tt += T[i+1];
	}
	int M;
	cin >> M;
	rep(i,M) {
		int p, x;
		cin >> p >> x;
		cout << tt+x-T[p] << endl;
	}

	return 0;
}


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

int main() {
  
  int n;
  string s;
  cin >> n >> s;
  
  bool ans = true;
  if(n % 2 == 1) ans = false;
  
  REP(i,n/2) {
    if (s[i] != s[n/2+i]) ans = false;                  
  }
  
  cout << (ans ? "Yes" : "No") << endl;
    
}

Measured memory_bytes: 256
from heapq import *
n,m = map(int,input().split())
a = list(map(int,input().split()))
bc = [list(map(int,input().split()))for _ in range(m)]

heapify(a)
bc = sorted(bc,key=lambda x:x[1],reverse=True)

for b,c in bc:
    for i in range(b):
        tmp = heappop(a)
        if tmp >= c:
            heappush(a,tmp)
            break
        else:
            heappush(a,c)

print(sum(a))

Measured memory_bytes: 33724
#include<cstdio>
#include<algorithm>
using namespace std;

int main(){
  int n,k,s[100];
  scanf("%d %d",&n,&k);
  fill(s,s+n,0);
  for(int i=0;i<k;i++){
    int a,b;
    scanf("%d %d",&a,&b);
    s[a-1] = b;
  }
  int dp[n][27];
  fill(dp[0],dp[0]+27*n,0);
  for(int i=0;i<3;i++){
    for(int j=0;j<3;j++){
      for(int k=0;k<3;k++){
        if((i!=j||j!=k)&&(s[0]==0||(i-s[0])%3==0)&&(s[1]==0||(j-s[1])%3==0)&&(s[2]==0||(k-s[2])%3==0)){
          dp[2][9*i+3*j+k] = 1;
        }
      }
    }
  }

  for(int i=3;i<n;i++){
    for(int j=0;j<27;j++){
      if(j%13==0||(s[i]>0&&(j-s[i])%3!=0)) dp[i][j] = 0;
      else{
        int x = j%3;
        int y = j/3;
        for(int k=0;k<3;k++) dp[i][j]+=dp[i-1][9*k+y];
        dp[i][j]%=10000;
      }
    }
  }
  int ans = 0;
  for(int i=0;i<27;i++) ans+=dp[n-1][i];
  printf("%d\n",ans%10000);
  return 0;
}

Measured memory_bytes: 2716
N = int(input())
S = str(input())

lis = list()
for i in range(len(S)):
    if (ord(S[i]) + N) > 90:
        lis.append(chr(ord(S[i]) +N - 26))
    else:
        lis.append(chr(ord(S[i]) + N))

ans =""

for x in lis:
    ans += x

print(ans)

Measured memory_bytes: 3064
#include <stdio.h>

struct DICE {
	int num[7];
};

void throwdice(char ch, struct DICE *dice)
{
	int temp;
	switch (ch) {
	case 'N':
		temp = dice->num[6] ;
		dice->num[6] = dice->num[5] ;
		dice->num[5] = dice->num[1] ;
		dice->num[1] = dice->num[2] ;
		dice->num[2] = temp;
		break;
	case 'S':
		temp = dice->num[6] ;
		dice->num[6] = dice->num[2] ;
		dice->num[2] = dice->num[1] ;
		dice->num[1] = dice->num[5] ;
		dice->num[5] = temp;
		break;
	case 'E':
		temp = dice->num[6] ;
		dice->num[6] = dice->num[3] ;
		dice->num[3] = dice->num[1] ;
		dice->num[1] = dice->num[4] ;
		dice->num[4] = temp;
		break;
	case 'W':
		temp = dice->num[6] ;
		dice->num[6] = dice->num[4] ;
		dice->num[4] = dice->num[1] ;
		dice->num[1] = dice->num[3] ;
		dice->num[3] = temp;
		break;
	}
}

int rot(int top, int front, struct DICE *dice)
{
	int cnt;
	cnt = 0;
	while (dice->num[2] != front) {
		if (dice->num[3] == front || dice->num[4] == front) {
			throwdice('E', dice);
		}
		throwdice('N', dice);
		cnt++;
		if(cnt == 4) {
			return -1;
		}
	}
	cnt = 0;
	while (dice->num[1] != top) {
		throwdice('E', dice);
		cnt++;
		if(cnt == 4) {
			return -1;
		}
	}
	return 0;
}

int main(void)
{
	struct DICE dice;
	int i, q, top, front, right, f;
	
	for(i=1; i<=6; i++) {
		scanf("%d",&dice.num[i]);
	}
	scanf("%d",&q);
	for (i=0; i<q; i++) {
		scanf("%d %d",&top,&front);
		f = rot(top, front, &dice);
		printf("%d\n", dice.num[3]);
	}
	return 0;
}

Measured memory_bytes: 596
import java.util.*;
import java.lang.*;
import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException{
        FastReader in = new FastReader();
        FastWriter out = new FastWriter();
        int n = in.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++){
            nums[i] = in.nextInt();
        }
        int ans = 0;
        for (int i = 0; i < n; i++){
            for (int j = i+1; j < n; j++){
                ans+= nums[i]*nums[j];
            }
        }
        out.pl(ans);
        out.close();
    }
}
class FastReader{ 
    BufferedReader br; 
    StringTokenizer st; 
    public FastReader() { 
        br = new BufferedReader(new InputStreamReader(System.in)); 
    } 
    String next(){ 
        while (st == null || !st.hasMoreElements()) { 
            try{ 
                st = new StringTokenizer(br.readLine()); 
            }catch (IOException  e){ 
                e.printStackTrace(); 
            } 
        } 
        return st.nextToken(); 
    } 
    int nextInt(){ 
        return Integer.parseInt(next()); 
    } 
    long nextLong(){ 
        return Long.parseLong(next()); 
    } 
    double nextDouble(){ 
      return Double.parseDouble(next()); 
    } 
    String nextLine(){ 
        String str = ""; 
        try{ 
            str = br.readLine(); 
        } 
        catch (IOException e){ 
            e.printStackTrace(); 
        } 
        return str; 
    } 
}
class FastWriter{
    PrintWriter out;
    FastWriter(){
        out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
	out.flush();
    }
    void pl(Object o){
        out.write(o.toString());
	    out.write("\n");
        out.flush();
    }
    void pl(){
        out.write("\n");
    }
    void p(Object o){
        out.write(o.toString());
    }
    void close(){
        out.flush();
        out.close();
    }  
}


Measured memory_bytes: 32916
#include<iostream>
using namespace std;
typedef long long ll;
const ll Mod = 1e9 + 7;
const int N = 200005;
ll Inv[2*N], Fac[2*N];
ll C(ll n, ll m) {
    if(!m || (n == m)) return 1;
    return Fac[n]*Inv[n-m]%Mod*Inv[m]%Mod;
}
ll Cal(ll x, ll y) {
    return C(x+y-2,y-1);
}
ll ex_gcd(ll a, ll b, ll &x, ll &y) {
    ll r, x1, y1;
    if(!b) {
        x = 1, y = 0; return a;
    }
    r = ex_gcd(b,a%b,x1,y1);
    x = y1,  y = x1-a/b*y1;
    return r;
}
ll inv(ll a, ll n) {
    ll x, y;
    if(ex_gcd(a,n,x,y) == 1) return (x+n)%n;
    else return -1;
}
int main() {
    ll H, W, A, B, ans = 0, n = N+N/2;
    cin >> H >> W >> A >> B;
    Fac[1] = 1;
    for(int i = 2; i <= n; ++i) {
        Fac[i] = (Fac[i-1]*i)%Mod;
    }
    for(int i = 1; i <= n; ++i) Inv[i] = inv(Fac[i],Mod);
    
    for(ll i = B+1; i <= W; ++i) {
        ans = (ans + Cal(H-A,i)*Cal(A,W-i+1)) % Mod;
    }
    cout << ans << '\n';
return 0;
}

Measured memory_bytes: 8264
#include <bits/stdc++.h>
using namespace std;
 
int main () {
  string s; 
  cin >> s;
  int r = 0;
  for(int i= 0;i<s.size();i++){
    if(s[i] == '1'){
      r++;
    }
  }
      cout << r << endl;
    
  
}

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


int my_gets(char *buf,int nBuf,FILE *fp){
    int ch;

    while(--nBuf >0){
        ch=getc(fp);
        if(ch==EOF || ch=='\n')
            break;
        *(buf++)=(char)ch;
    }
    *(buf)='\0';

    return nBuf;
}

int GetOddSum(char *buf){
    int ret=0;

    for(int i=0; i<7; i++)
        ret += buf[2*i+1] - '0';
    return ret;
}

int GetEvenSum(char *buf){
    int ret=0;

    for(int i=0; i<8; i++){
        int tmp =2*(buf[2*i] - '0');

        ret += (tmp>=10)?(tmp%10 +1):(tmp);
    }
    return ret;
}


int main(){
    int n;
    char buf[20];

    scanf("%d%*c",&n);
    printf("%d\n",3*n*n);
    
    return 0;
}

Measured memory_bytes: 128
#include <stdlib.h>
#include <iostream>  
#include <string.h>
#include <algorithm>
#include <stdio.h>
#include <sstream>
using namespace std;
#include <math.h> 
#include <cmath>
string  ch = "";
string  chr = "";
string table[1000000];
string mat[100][100];
 long long int t[1000000];
 long long int t2[1000000];

 long long int n, m, k, s, p, x,y,z;

int main()
{
	x=0;
	y=0;
	z=0;
	cin >> n>>m>>p>>k;
	 
		if (k%2!=0)
		{
			s=m-n;
		}else{
			s=n-m;
		}
		
	
		if (s<1e18)
		{
			cout<<s;
			return 0;
		}else{
			cout<<"Unfair";
						

			return 0;

		}
}
	


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

using namespace std;

int main(){
   int tmp;
   int k;
   int mmin = 1000;
   int mmax = -1;
   for(int i = 0; i < 5;i++){
      scanf("%d",&tmp);
      mmax = max(mmax, tmp);
      mmin = min(mmin,tmp);
   }
   scanf("%d",&k);
   if( mmax - mmin > k)printf(":(\n");
   else printf("Yay!");
   return 0;

}


Measured memory_bytes: 256