akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;i--)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
using namespace std;
int main() {
    int n;
    cin>>n;
    vector<string>s(n);
    rep(i,n)cin>>s.at(i);
    vector<int>vec(26,100);
    rep(i,n){
        vector<int>tmp(26);
        rep(j,s.at(i).size()) tmp.at(s.at(i).at(j)-'a')++;
        rep(i,26) vec.at(i)=min(vec.at(i),tmp.at(i));
    }
    
    string ans;
    rep(i,26){
        rep(j,vec.at(i)) ans+='a'+i;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
# ABC138E - Strings of Impurity
def main():
    S = input()
    T = input()
    if set(T) <= set(S):
        lim_s, lim_t = len(S) - 1, len(T)
        ans, cur, idx = 1, 0, -1
        while cur < lim_t:
            x = S[idx + 1 :].find(T[cur])
            if x == -1:
                ans += 1
                idx = -1
            else:
                idx += x + 1
                cur += 1
        ans = (ans - 1) * (lim_s + 1) + idx + 1
        print(ans)
    else:  # corner case
        print(-1)


if __name__ == "__main__":
    main()

Measured memory_bytes: 3316
n,q = map(int,input().split())
s = input()
u = [ list(map(int,input().split())) for _ in range(q)]

c = [0]
count = 0
for i in range(1,n):
  #print(s[i-1] + s[i])
  if s[i-1] + s[i] == 'AC':
    count += 1
  c.append(count)

for i,j in u:
  print( c[j-1] - c[i-1] )


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

using namespace std;

typedef long long ll;
const int maxn = 1e5+500;

int main()
{
	//string s;
	int a;
	cin>>a;
	string s;
	cin>>s;
	if(a>=3200){
		cout<<s;
	}else{
		cout<<"red";
	}
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;a++)
#define rl(a,b,c) for(int a=b;a>=c;a--)
#define niv vector<int>
#define LL long long
#define IT iterator
#define PB(a) push_back(a)
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
typedef pair<mp,mp> superpair;
int a[100001];
bool cmp(int A,int B){
	return A>B;
}
vector<mp> opera;
int main(){
	ios::sync_with_stdio(false);
	int n,sum=0;
	cin>>n;
	rb(i,1,n) cin>>a[i],sum+=a[i];
	sort(a+1,a+1+n,cmp);
	int OK=0;
	rb(i,1,n) if(a[i]<0) OK=1;
	if(a[1]<0){
		int res=a[1];
		rb(i,2,n) res-=a[i];
		cout<<res<<endl;
		int SAVE=a[1];
		rb(i,2,n){
			cout<<SAVE<<" "<<a[i]<<endl;
			SAVE-=a[i];
		}
		return 0;
	}
	if(OK){
		int res=0;
		rb(i,1,n) res+=abs(a[i]);
		cout<<res<<endl;
		int FROM;
		rb(i,1,n){
			if(a[i]<0){
				FROM=i;
				break;
			}
		}
		rb(i,FROM,n-1){
			cout<<a[1]<<" "<<a[i]<<endl;
			a[1]-=a[i];
		}
		rb(i,2,FROM-1){
			cout<<a[n]<<" "<<a[i]<<endl;
			a[n]-=a[i];
		}
		cout<<a[1]<<" "<<a[n];
	}
	else{
		int res=0;
		rb(i,1,n-1) res+=a[i];
		res-=a[n];		
		cout<<res<<endl;
		rb(i,2,n-1){
			cout<<a[n]<<" "<<a[i]<<endl;
			a[n]-=a[i];
		}
		cout<<a[1]<<" "<<a[n]<<endl;
	}
	return 0;
}

Measured memory_bytes: 2304
#include<iostream>
#include<stdio.h>
//#include <bits/stdc++.h>
#include<vector>
#include<float.h>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
#include<math.h>
#include<cmath>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include <cassert>
#include <cmath>
#include<cstdint>

#define INF 1e9
#define rep(i,n)for(int i=0;(i)<(int)(n);i++)
#define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define vec(type,n) vector<type>(n)
#define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))
#define ALL(a)  (a).begin(),(a).end()

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

vector<int>bitSearch(int bit,int n){
    vector<int>S;
    rep(i,n)if(bit&(1<<i))S.push_back(i);
    return S;
}



int main(){
   int n;cin>>n;
   int res = 0;
   for(int i=1;i*i<=n;i++){
       res = max(res,i*i);
   }
   cout<<res;
}



Measured memory_bytes: 256
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric, std.container;

void main()
{
    auto nw = readln.split.to!(int[]);
    auto N = nw[0];
    long W = nw[1];
    int[] vs;
    long[] ws;
    foreach (_; 0..N) {
        auto vw = readln.split.to!(int[]);
        vs ~= vw[0];
        ws ~= vw[1];
    }

    auto DP = new long[][](N+1, 100*N+1);
    foreach (ref dp; DP) dp[] = long.max/3;
    DP[0][0] = 0;
    foreach (i; 0..N) {
        foreach (v; 0..100*N+1) {
            DP[i+1][v] = min(DP[i+1][v], DP[i][v]);
            if (v >= vs[i]) DP[i+1][v] = min(DP[i+1][v], DP[i][v-vs[i]] + ws[i]);
        }
    }
    foreach_reverse (v; 0..100*N+1) if (DP[N][v] <= W) {
        writeln(v);
        return;
    }
}


Measured memory_bytes: 10324
check :: String -> Bool
check x = '7' `elem` x && '5' `elem` x && '3' `elem` x

solve :: Int -> String -> Int
solve n s
  | s /= "" && read s > n = 0
  | otherwise = solve n (s ++ "7")
              + solve n (s ++ "5")
              + solve n (s ++ "3")
              + if check s then 1 else 0

main :: IO ()
main = do
  n <- readLn
  print $ solve n ""

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

int main(){
    int n;
    cin >> n;
    int a[n];
    for(int i=0; i<n; i++)cin>>a[i];

    int count=0;
    for(int i=1; i<n; i++){
        if(a[i-1]==a[i]){
            count++;
            a[i]++;
            if(a[i]==10000)a[i]=1;
            if(a[i]==a[i+1])a[i]++;
        }
    }
    cout << count << endl;
    return 0;
}


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

#define rate 380000.0
int main(void){
    int N;
    double sum=0;
    char ans[3]={'B','T','C'};
    cin>>N;

    for(int i=0;i<N;i++){
        double x;
        string u;
        int cnt=0;
        cin>>x>>u;
        double yen;

        for(int j=0;j<3;j++){
            if(u[j]==ans[j])
                cnt++;
        }
        if(cnt==3){
             yen=x*rate;
        }else
            yen=x;
        sum+=yen;
    }
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(x) begin(x),end(x)

using namespace std;
using ll = int64_t;

int main() {
  int n;
  cin>>n;
  if ((n%2) == 0) {
    cout << (n-2)*n/2 << endl;
    REP(i,n) {
      int j = i+1;
      int op = n+1 - j;
      REP(k,i) {
        int l = k+1;
        if (l == op) continue;
        cout << j << ' ' << l << endl;
      }
    }
  } else {
    int cnt = 0;
    stringstream ss;
    int m = n+1;
    REP(i,m) {
      int op = n - i;
      FOR(k,1,i) {
        if (k == op) continue;
        ss << i << ' ' << k << endl;
        ++cnt;
      }
    }
    cout << cnt << endl;
    cout << ss.str();
  }
  return 0;
}


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

#include <iostream>
using namespace std;
int main() {
  int64_t n, m, x;
  cin >> n >> m >> x;
  vector<int64_t> C(n);
  vector<vector<int64_t>> A(n, vector<int64_t>(m));
  vector<int64_t> sum_j(m, 0);
  for (int64_t i = 0; i < n; ++i) {
    cin >> C[i];
    for (int64_t j = 0; j < m; ++j) {
      cin >> A[i][j];
      sum_j[j] += A[i][j];
    }
  }

  bool achieve = true;
  for (auto elem_sum_j : sum_j) {
    if (elem_sum_j < x) {
      achieve = false;
      break;
    }
  }

  if (achieve) {
    int64_t min_total = accumulate(C.begin(), C.end(), 0);
    int64_t step = pow(2, n);
    for (int64_t i = 0; i < step; ++i) {
      int64_t total = 0;
      int64_t temp_i = i;
      vector<int64_t> sum_j2(m, 0);
      for (int64_t j = n - 1; j >= 0; --j) {
        int64_t temp = pow(2, j);
        if (temp_i >= temp) {
          for (int64_t k = 0; k < m; ++k) {
            sum_j2[k] += A[j][k];
          }
          total += C[j];
          temp_i -= temp;
        }
      }
      bool achieve = true;
      for (auto elem_sum_j : sum_j2) {
        if (elem_sum_j < x) {
          achieve = false;
          break;
        }
      }
      if (achieve && total < min_total) {
        min_total = total;
      }
    }
    cout << min_total << endl;
  } else {
    cout << -1 << endl;
  }

  return 0;
}


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

using namespace std;
#define inf 1000000000
#define unvisited -1
#define visited 1
#define eps 1e-9
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define uint64 unsigned long long
#define FastSlowInput ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;

int main(){
	string s;
	cin>>s;
	int cnt[256];
	memset(cnt, 0, sizeof cnt);
	for(int i=0;i<s.length();i++){
		cnt[s[i]]++;
	}
	int counter = 0;
	for(int i='A';i<='Z';i++){
		if(cnt[i] == 2) {
			counter++;
		}else if(cnt[i] == 0) {

		}else{
			printf("No\n");
			return 0;
		}
	}

	if(counter == 2){
		printf("Yes\n");
	}

	return 0;
};

Measured memory_bytes: 764
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<numeric>
#include<vector>
#include<cstring>
#define foreach(t,p) for(t::iterator it=p.begin();it!=p.end();p++)
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
#define MAX_W 50

bool island[MAX_W+3][MAX_W+3];

int solve(int x,int y)
{
	if(!island[x][y]) {return 0;}

	island[x][y]= false;
	solve(x-1,y-1);
	solve(x-1,y);
	solve(x-1,y+1);
	solve(x,y-1);
	solve(x,y+1);
	solve(x+1,y+1);
	solve(x+1,y);
	solve(x+1,y-1);
//	cout << x << " " << y << endl;
	return 1;
}


int main()
{
	int w,h;
	while(cin >> w >> h &&w && h)
	{
		REP(i,MAX_W+2)REP(j,MAX_W+2) island[i][j]=false;
		REP(i,h)REP(j,w){cin >> island[i+1][j+1];}
		int kosu = 0;
		REP(i,h)REP(j,w){kosu += solve(i+1,j+1);}
		cout << kosu << endl;
		
	}
	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <string.h>
#include <cstdio>
#include <tuple>
#include <numeric>
using namespace std; using ll = long long; using ld = long double;  using pll = pair<ll, ll>;
using vl = vector<ll>; using vll = vector<vl>; using vpll = vector<pll>;
using vs = vector<string>; using tll = tuple<ll, ll, ll>; using vtll = vector<tll>;
const ld PI = 3.1415926535897932;
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define co(i) cout << i << endl;
#define co2(i,j) cout << i << " " << j << endl;
#define co3(i) cout << i << " ";
#define po(i) cout << i.first << " " << i.second << endl;
void in() {}
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail>
void debug_out(Head h, Tail... t) {
	cerr << " " << h;
	if (sizeof...(t) > 0) cerr << " :";
	debug_out(t...);
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> vec) {
	for (size_t i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
	return os;
}
ll ctoi(char c) {
	switch (c) {
	case '0': return 0; case '1': return 1; case '2': return 2;
	case '3': return 3; case '4': return 4; case '5': return 5;
	case '6': return 6; case '7': return 7; case '8': return 8;
	case '9': return 9;  default: return 0;
	}
}
bool pairCompare(const pll firstElof, pll secondElof)
{
	return firstElof.first > secondElof.first;
}
//**Snippetリスト**//
//rep, vin, all, iteLoop, bitSearch, bitList, nod//
//gcdlcm, isPrime, eratos, primeFactorize, Npow, combination, divisor, modinv, doubling, digitDP//
//dfs, bfs, dijkstra, WarshallFloyd, BellmanFord, UnionFind, Kruskal, RMQ, LCA//
ll i, j, k, l; ll N, M, K, H, W, L, X, Y, Z, R, Q;
ll MOD = 1000000007, INF = 1LL << 60, ans = 0, z = 0, o = 1;
vll flag, D; vpll path;
//***********//
int main() { 
	cin >> N;
	if (N == 3) {
		cout << 2 << " " << 5 << " " << 63;
		exit(0);
	}
	else if(N%2==1){
		vl A = { 6,2,10,3,9,4,8,12 };
		ll B = 0; ll now = 0;
		while (N > 0) {
			co3(A[now]+B);
			now++;
			if (now == A.size()) {
				B += 12; now = 0;
			}
			N--;
		}
	}
	else {
		vl A = { 2,10,3,9,4,8,6,12 };
		ll B = 0; ll now = 0;
		while (N > 0) {
			co3(A[now] + B);
			now++;
			if (now == A.size()) {
				B += 12; now = 0;
			}
			N--;
		}
	}
}

Measured memory_bytes: 3636
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
import heapq
INF = float("inf")
MOD = 10**9 + 7
sys.setrecursionlimit(10**7)
# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W
def mi(): return map(int, input().split())
def ii(): return int(input())
###template###

N = ii()
As = list(mi())
ave = round(sum(As) / N)

ans = 0
for a in As:
  ans += (ave - a) ** 2

print(ans)


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

int main(void){
    int i, n, a[100];
    cin >> n;
    for (i=0;i<n;i++) cin >> a[i];
    for (i=n-1; i>=0; i--){
        if(i<n-1) cout << " ";
        cout << a[i];
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		String l = sc.nextLine();
		Integer N = Integer.valueOf(l);
		l = sc.nextLine();
		String[] arr = l.split(" ");
		
		StringBuilder sb = new StringBuilder();
		int[] boss = new int[arr.length + 1];
		int[] result = new int[N+1];
		
		int count = 1;
		for(String s : arr) {
			result[Integer.valueOf(s)]++;
			
		}
		for (int i = 1; i < result.length; i++) {
			sb.append(result[i]+"\n");
		}
		sc.close();
		System.out.println(sb.toString());
	}
}

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

#define SIZE 5

using namespace std;

int main() {
	int list[5];
	for (int i = 0; i < SIZE; i++) {
		cin >> list[i];
	}

	sort(list, list+SIZE);

	for (int i = 0; i < SIZE - 1; i++) {
		cout << list[SIZE - i - 1] << " ";
	}
	cout << list[0] << endl;

	return 0;
}

Measured memory_bytes: 3084
#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 <memory>        // unique_ptr, shared_ptr, weak_ptr

using namespace std;

int main() {
    int a, b;
    char op;
    while (true) {
        cin >> a >> op >> b;
        if (op == '?') break;
        else if (op == '+') cout << a + b << endl;
        else if (op == '-') cout << a - b << endl;
        else if (op == '*') cout << a * b << endl;
        else if (op == '/') cout << a / b << endl;
    }
    return 0;		 
}


Measured memory_bytes: 3084
#include<stdio.h>
#define MAX 100005
#define NIL -1
struct Node_struct{int p, l, r;}; /*p: 親(parent), l: 一番左の子(left child), r:右の兄弟(right sibling)*/
typedef struct Node_struct Node;
Node T[MAX];
int D[MAX];

void print(int u){
  int i, c;
  printf("node %d: parent = %d, depth = %d, ", u, T[u].p, D[u]);

  if(T[u].p == NIL/*ここを埋める (fill this blank)*/) printf("root, ");
  else if(T[u].l == NIL/*ここを埋める(fill this blank)*/) printf("leaf, ");
  else printf("internal node, ");
  
  printf("[");
  for (i=0, c = T[u].l; c != NIL; i++, c = T[c].r){
    if(i) printf(", ");
    printf("%d", c);
  }
  printf("]\n");
  
}

void calcDepth(int u, int p){
  D[u] = p;
  if(T[u].r !=NIL/*ここを埋める(fill this blank)*/) calcDepth(T[u].r, p/*ここを埋める(fill this blank)*/);
  if(T[u].l !=NIL/*ここを埋める(fill this blank)*/) calcDepth(T[u].l, p+1/*ここを埋める(fill this blank)*/);
}

int main(){
  int i, j, k;
  int n;
  int id, sib, child;
  int root = NIL;
  scanf("%d", &n);
  for(i=0; i<n; i++) T[i].p = T[i].l = T[i].r = NIL;
  
  for(i=0; i<n; i++){
    scanf("%d %d", &id, &k);
    for(j = 0, sib = NIL; j<k; j++){ //子を入力する (input children)
      scanf("%d", &child);
      T[child].p = id;
      if(j == 0) T[id].l = child; //idの一番左の子 (the most left child of id)
      else T[sib].r = child; //左の兄弟に繋げる (connect to left sibling)
      sib = child;//次の子供の左の兄弟 (the left sibling of the next child)
    }
  }

  //根を求める (find the root)
  for(i=0; i<n; i++){
    if(T[i].p == -1) root = i;
  }
  
  //それぞれのノードの深さを求める (find depth of each node)
  calcDepth(root, 0);

  //出力 (output)
  for(i=0; i<n; i++) print(i);
  
  return 0;
}



Measured memory_bytes: 7296
#include <bits/stdc++.h>
using namespace std;
#define M 1000000007
long long int power(int a,int b)
{
    if(b==0)
        return 1;
    long long int k=power(a,b/2);
    if(b%2==0)
        return ((k%M)*(k%M))%M;
    else
        return ((k%M)*(k%M)*(a%M))%M;
}
long long int fact(long long int n)
{
    if(n==1 || n==0)
        return 1;
    else
        return ((n%M)*(fact(n-1)%M))%M;

}
int div(int n)
{  int c=0;
    for(int i=1;i<=sqrt(n);i++)
    {
        if(n%i==0)
        {
          if(n/i==i)
            c++;
          else
            c+=2;
        }

    }

    
    return  c;
}
int func(int n)
{
    return (n*(n+1))/2;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
     #ifndef ONLINE_JUDGE
 
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
   #endif
   
    int n,m,k;
    cin>>n>>m>>k;
    int s=0,s1=0;
    while(m--)
    {
          int h;
          cin>>h;
          if(h>k)
            s1++;
        else if(h<k)
            s++;

    }
    cout<<min(s,s1);



 return 0;
}








Measured memory_bytes: 3676
#include<stdio.h>
int main(){
  int n,i;
  scanf("%d",&n);
  int a[n+1][2];
  for(i=1;i<=n;i++){
    scanf("%d",&a[i][0]);
    a[i][1]=0;
  }
  i=1;
  int count=0;
  while(i!=2 && a[i][1]==0){
    a[i][1]++;
    i=a[i][0];
    count++;
  }
  if(i==2)
    printf("%d\n",count);
  else
    puts("-1");
  return 0;
}

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

int main() {
  string s;
  cin >> s;

  string t="";
  int s_size = s.size();
  for (int i=0; i<s_size; ) {
    if (i+5 <= s_size && s.substr(i, 5) == "dream") {
      t += "dream";
      i += 5;
    } else if (i+5 <= s_size && s.substr(i, 5) == "erase") {
      t += "erase";
      i += 5;
    } else if (i+2 <= s_size && s.substr(i-5, 5) == "dream" && s.substr(i, 2) == "er") {
      t += "er";
      i += 2;
    } else if (i+1 <= s_size && s.substr(i-5, 5) == "erase" && s[i] == 'r') {
      t += "r";
      i += 1;
    } else {
      break;
    }
  }

  if (s == t) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }

  return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <map>
#include <cstring>
#include <algorithm>

using namespace std;

typedef pair<int, int> pii;
typedef map<int, int> mii;

const int Z = 998244353;

void upd(int bit[], int n, int x) {
    for (; x <= n; x += x & -x) {
        bit[x]++;
    }
}

int qry(int bit[], int x) {
    int r = 0;
    for (; x; x -= x & -x) {
        r += bit[x];
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);

    int n;
    cin >> n;
    pii xy[n];
    for (int i = 0; i < n; i++) {
        cin >> xy[i].first >> xy[i].second;
    }
    sort(xy, xy+n);

    int a[n];
    for (int i = 0; i < n; i++) {
        a[i] = xy[i].second;
    }

    mii xx;
    for (int i = 0; i < n; i++) {
        xx[a[i]] = 0;
    }

    int q = 0;
    for (auto p : xx) {
        xx[p.first] = ++q;
    }

    for (int i = 0; i < n; i++) {
        a[i] = xx[a[i]];
    }

    int l[n], r[n], u[n], d[n], lu[n], ru[n], ld[n], rd[n];

    int bit[n+1];
    memset(bit, 0, sizeof(bit));
    for (int i = 0; i < n; i++) {
        ld[i] = qry(bit, a[i]);
        lu[i] = i - ld[i];
        upd(bit, n, a[i]);
    }

    memset(bit, 0, sizeof(bit));
    for (int i = n - 1; i >= 0; i--) {
        rd[i] = qry(bit, a[i]);
        ru[i] = n - 1 - i - rd[i];
        upd(bit, n, a[i]);
    }

    int p2[n+1];
    for (int i = 0; i <= n; i++) {
        p2[i] = i == 0 ? 1 : p2[i-1] * 2 % Z;
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        l[i] = i;
        r[i] = n - 1 - i;
        u[i] = lu[i] + ru[i];
        d[i] = ld[i] + rd[i];

        ans = (0ll + ans + p2[n] - 1 + Z * 4ll
              - p2[l[i]] - p2[r[i]] - p2[u[i]] - p2[d[i]]
              + p2[lu[i]] + p2[ld[i]] + p2[ru[i]] + p2[rd[i]]) % Z;
    }

    cout << ans << endl;

    return 0;
}


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

using namespace std;


//repetition
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define euc_dis(x, y) sqrt(x*x + y*y)

#define pb push_back
#define INF 999999999
#define MOD 1000000007
#define sp ' '


//typedef
typedef long long ll;
typedef pair<int, int> pint;
typedef pair<long, long> pll;
typedef map<int, int> mint;
typedef set<int> sint;
typedef vector<int> vint;
typedef vector<char> vchr;
typedef vector<long long> vll;
typedef vector<string> vstr;


ll mod(ll a, ll b){return (a%b+b)%b;}
ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
void Yes(){cout << "Yes" << endl;}
void No(){cout << "No" << endl;}
void Judge(bool b){b?Yes():No();}
void YES(){cout << "YES" << endl;}
void NO(){cout << "NO" << endl;}
void JUDGE(bool b){b?YES():NO();}
ll powMod(ll a, ll b, ll c){ll ans=1; rep(i, b){ans=ans*a%c;} return ans;}
double distance(ll x1, ll y1, ll x2, ll y2){return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));}

template<typename T>
void ppp(T n){cout << n << endl;}
template<typename T>
void dpp(T n){cerr << n << endl;}
template<typename T>
void vpp(T a){rep(i,a.size()){cout << a[i] << endl;}}
template<typename T>
void vdp(T a){rep(i,a.size()){cerr << a[i];}cerr << endl;}

const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const int ddx[8] = {1,0,-1,0,1,-1,-1,1};
const int ddy[8] = {0,1,0,-1,1,1,-1,-1};




using edge = struct {int to;ll cost;};

vector<edge> tree[100001];
ll d[100001];

void dfs(int v, int parent, ll dist){

    d[v] = dist;
    for(auto &e : tree[v]){
        if(e.to == parent) continue;
        dfs(e.to, v, dist + e.cost);
    }
}

int main(){

    cin.tie(0);
    ios::sync_with_stdio(false);


    int n;
    cin >> n;

    rep(i, n-1){
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        tree[a].push_back({b,c});
        tree[b].push_back({a,c});
    }

    int q, k;
    cin >> q >> k;
    --k;

    dfs(k, -1, 0);
    rep(i, q){
        int x, y;
        cin >> x >> y;
        x--; y--;
        cout << d[x] + d[y] << endl;
    }


    return 0;
}


Measured memory_bytes: 14336
#include<iostream>
#include<cmath>
using namespace std;
const int mod=1e9+7;
int main()
{
    long long int n,w=0,j,s,m=1,pr;
    cin>>n;
    long long int a[1000];
    long long int c[1000];
    if(n==1) cout<<"1"<<endl;
    if(n==2) cout<<"2"<<endl;
    if(n>2){
    for(int i=2;i<=n;i++)
    {
        pr=1;
        for(j=2;j<=sqrt(i);j++)
        {
            if((i%j)==0) {pr=0;break;}
        }
        if(pr==1||i==2) {a[w]=i;w++;}
    }
     for(int i=0;i<w;i++)
     {
         s=0;
         for(int k=a[i];;)
         {
             s=s+n/k;
             k*=a[i];
             if(k>n) break;
         }
         c[i]=s;
     }
     for(int i=0;i<w;i++)
     {
         m=(m*(c[i]+1))%mod;
     }
     cout<<m<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int[] ans = new int[3];
        for (int i = 0; i < 3; i++) {
            ans[i] = sc.nextInt();
        }
        Arrays.sort(ans);

        System.out.println(Integer.parseInt(String.valueOf(ans[2]).concat(String.valueOf(ans[1]))) + ans[0]);
    }
}

Measured memory_bytes: 22996
import numpy as np
n, m = map(int, input().split())
A = np.array([input() for i in range(n)])
B = [input() for i in range(m)]

flag = "No"
diff = n - m + 1
for i in range(diff):
  for j in range(diff):
    T = []
    for k in range(m):
      T.append(A[i+k][j:j+m])
    if T == B:
      flag = "Yes"
      break

print(flag)


Measured memory_bytes: 12496
def isPrime(n):
    i = 2
    while i * i <= n:
        if n % i == 0:
            break
        i += 1
    else:
        return True
    return False


if __name__ == '__main__':
    n = int(input())
    cnt = 0
    for _ in range(n):
        if isPrime(int(input())):
            cnt += 1
    print(cnt)


Measured memory_bytes: 5612
N = input()
s = raw_input()

for ans in ["SS", "SW", "WS", "WW"]:
  for i in range(2, N):
    if   ans[-2:]=="SS" and s[i-1]=="o": ans += "S"
    elif ans[-2:]=="SS" and s[i-1]=="x": ans += "W"
    elif ans[-2:]=="SW" and s[i-1]=="o": ans += "W"
    elif ans[-2:]=="SW" and s[i-1]=="x": ans += "S"
    elif ans[-2:]=="WS" and s[i-1]=="o": ans += "W"
    elif ans[-2:]=="WS" and s[i-1]=="x": ans += "S"
    elif ans[-2:]=="WW" and s[i-1]=="o": ans += "S"
    elif ans[-2:]=="WW" and s[i-1]=="x": ans += "W"
  if ((ans[0]=="S" and s[0]=="o" and ans[-1]==ans[1] or
       ans[0]=="S" and s[0]=="x" and ans[-1]!=ans[1] or
       ans[0]=="W" and s[0]=="o" and ans[-1]!=ans[1] or
       ans[0]=="W" and s[0]=="x" and ans[-1]==ans[1]) and
      (ans[-1]=="S" and s[-1]=="o" and ans[-2]==ans[0] or
       ans[-1]=="S" and s[-1]=="x" and ans[-2]!=ans[0] or
       ans[-1]=="W" and s[-1]=="o" and ans[-2]!=ans[0] or
       ans[-1]=="W" and s[-1]=="x" and ans[-2]==ans[0])):
    print ans
    exit(0)
print -1


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

#define rep(i, n) for(int i=0; i < n; i++)
#define REP(i, n, m) for(int i=n; i < m; i++)
#define reps(i, n) for(int i=1; i <= n; i++)
#define ALL(v) v.begin(), v.end()
#define rALL(v) v.rbegin(), v.rend()
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)

using namespace std;
using ll=long long;

ll mod=1;

const ll INF = 1LL << 60;

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

// a^n mod を計算 再帰
ll modpow(ll a,ll n,ll &mod){
  if(!n) return 1;
  ll x = modpow(a,n/2,mod)%mod;
  x *=x;
  if(n%2==1)x*=a;
  return x%mod;
}



int main(){
  string s;cin>>s;
  int n=s.size();
  int k;cin>>k;
  set<string> t;
  rep(i,n)reps(j,5){
    if(i+j<n+1)t.insert(s.substr(i,j));
  }
  auto itr=t.begin();
  advance(itr,k-1);
  cout<<*itr;
}


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

int main() {
	string a, b, c;
	cin >> a >> b >> c;
	int a_lst = a.size();
	int b_lst = b.size();
	
	if (b[0] == a[a_lst-1] && b[b_lst-1] == c[0])cout << "YES";
	else cout << "NO";
}

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

using namespace std;

int main() {
  string w;
  array<int, 26> a{0};

  cin >> w;
  for (auto i = w.begin(); i != w.end(); i++) {
    a[(int)(*i-'a')]++;
  }

  for (auto i = a.begin(); i != a.end(); i++) *i = *i % 2;

  //cout << accumulate(a.begin(), a.end(), 0) << endl;
  if (accumulate(a.begin(), a.end(), 0)) cout << "No" << endl;
  else cout << "Yes" << endl;

  return 0;
}


Measured memory_bytes: 256
n, m = map(int, input().split())
h = list(map(int, input().split()))
a = [0]*m
b = [0]*m
route = [[] for i in range(n)]
ans = 0

for i in range(m):
    a[i], b[i] = map(int, input().split())
    a[i] -= 1
    b[i] -= 1
    route[a[i]].append(b[i])
    route[b[i]].append(a[i])

for i in range(n):
    flag = True
    for idx in route[i]:
        if h[i] <= h[idx]:
            flag = False
    if flag:
        ans += 1

print(ans)

Measured memory_bytes: 31088
while True:
  try:
    s, t = raw_input(), raw_input()
    if len(s) < len(t): s, t = t, s
    MAXL = sum(min(s.count(i), t.count(i)) for i in set(list(s)) & set(list(t)))
    ans = 0
    for sp in range(len(t)):
      if len(t) - sp <= ans:
        break
      for l in range(ans+1, min(MAXL+1, len(t)-sp+1)):
        if t[sp:sp+l] in s:
          ans = l
        else:
          break
    print ans
  except:
    break

Measured memory_bytes: 4488
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MOD=1e9+7;
const long double Pi=acos(-1);
using  P=pair<ll,ll>;
int main(){
  ll N,ans=1;
  cin>>N;
  string str;
  cin>>str;
  for(ll i=1;i<N;i++){
    if(str.at(i)==str.at(i-1)){}
    else{ans++;}
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 512
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
#include<set>
#include<unordered_map>
#include<string.h>
#define int long long
#define mod 100000007
using namespace std;

int memo[2001][2001];
int saiki(int a, int b) {
	if (memo[a][b] != -1)return memo[a][b];
	int c = 0;
	if (a == 0 || b == 0)c = 1;
	else {
		c += saiki(a - 1, b);
		c += saiki(a, b - 1);
	}
	return memo[a][b] = c%mod;
}
signed main() {
	memset(memo, -1, sizeof(memo));
	int a, b, c, d, e, f;
	cin >> a >> b >> c >> d >> e >> f;
	int g = abs(e - c), h = abs(f - d);
	int i = a - max(e,c) + min(e,c), j = b - max(f,d) + min(f,d);
	int k = min(g, i), l = min(h, j);
	if (c == e) {
		if (h == j)puts("2");
		else puts("1");
		return 0;
	}
	if (d == f) {
		if (g == i)puts("2");
		else puts("1");
		return 0;
	}
	int ans = saiki(k, l);
	if (g == i) {
		if (h == j) {
			ans *= 4;
		}
		else {
			ans *= 2;
		}
	}
	else {
		if (h == j) {
			ans *= 2;
		}
	}
	cout << ans%mod << endl;
}

Measured memory_bytes: 34404
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int inf = 0x3f3f3f3f;
#define Rep(i,a,b) for(register int i=(a);i<=int(b);++i)
#define Dep(i,a,b) for(register int i=(a);i>=int(b);--i)
#define rep(i,a,b) for(register int i=(a);i<int(b);++i)
#define mem(x,v) memset(x,v,sizeof(x))
#define fi first
#define se second
#define lowbit(x) ((x)&-(x))
#define debug(x) cout << #x " = " << x << endl;
namespace IO{
	const int L = 1 << 15;
	char ibuf[L|1],*iS=ibuf,*iT=ibuf;
	char obuf[L|1],*oS=obuf,*oT=obuf+L;
	char c,st[66];int tp=0,f;
	inline char gc(){
		if(iS==iT) iT=(iS=ibuf)+fread(ibuf,sizeof(char),L,stdin);
		return (*iS++);
	}
	inline void flush() {
		fwrite(obuf,sizeof(char),oS-obuf,stdout);
		oS = obuf;
	}
	inline void pc(char c){*oS++=c;if(oS==oT) flush();}
	#define gc getchar
	#define pc putchar
	inline ll read(){
		ll x=0;f=1,c=gc();
		for(;!isdigit(c);c=gc())if(c=='-')f=-1;
		for(;isdigit(c);c=gc())x=(x<<1)+(x<<3)+(c&15);
		return x*f;
	}
	void write(ll x){
		if(!x) pc('0');if(x<0) pc('-'),x=-x;
		while(x) st[++tp]=x%10+'0',x/=10;
		while(tp) pc(st[tp--]);
	}
	void wri(ll x){write(x);pc(' ');}
	void writeln(ll x){write(x);pc('\n');}
	struct IOflusher{~IOflusher(){flush();}}_ioflusher_;
}
using IO::read;
using IO::writeln;
using IO::wri;
inline void gg(string s){cout << s << endl;exit(0);}
inline void gg(ll x){writeln(x);exit(0);}
const int maxn = 6000+233;
int dp[maxn+3][maxn*2+3],inv[maxn+3];
#define f(i,j) dp[i][j+maxn]
int n,mod;
inline int qpow(int a,int b){
	int ans = 1;
	for(;b;b>>=1,a=1ll*a*a%mod)
		if(b&1) ans=1ll*ans*a%mod;
	return ans;
}
int main(){
	n = read(),mod = read();
	f(0,0)=1;
	Rep(i,1,3*n) f(0,0)=1ll*f(0,0)*i%mod;
	inv[0] = inv[1] = 1;
	Rep(i,2,3*n) inv[i] = 1ll * (mod - mod / i) * inv[mod % i] %mod;
	Rep(i,1,3*n)
		Rep(j,-3*n,3*n){
			ll t = 0;
			if(i>=1) t+=f(i-1,j-1);//这个地方单独成一段 
			if(i>=2) t+=f(i-2,j+1);//这个地方加一个2的段 
			if(i>=3) t+=f(i-3,j);//这个地方加一个长度为3的段 
			f(i,j)=1ll*t%mod*inv[i]%mod;
		}
	int ans=0;
	Rep(j,0,3*n) ans=(ans+f(3*n,j))%mod;
	writeln(ans);
	return 0;
}

Measured memory_bytes: 295900
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll maxn=2e5+100;
string s,t;
int main(){
    ios::sync_with_stdio(0),cout.tie(0),cin.tie(0);
   // freopen("in.txt","r",stdin);
    cin>>s>>t;
    ll ans=0x3f3f3f3f;
    for(int i=0;i+t.size()-1<s.size();i++){
        ll temp=0;
        for(int j=0;j<t.size();j++){
            if(s[i+j]!=t[j])
                temp++;
        }
        ans=min(ans,temp);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3644
#include<stdio.h>
#define MAX 100001

int X,Y,Z;
int check(int ans)
{
    if ((unsigned long long)Y * ans + Z * (ans + 1) <= X)
        return 1;
    else
        return 0;
}

int upper_bound(int left, int right)
{
    if (right - left == 1)
        return left;
    int mid = left + (right - left) / 2;
    if (check(mid))
        return upper_bound(mid, right);
    else
        return upper_bound(left, mid);
}


int main()
{
    scanf("%d %d %d", &X, &Y, &Z);
    // [1 MAX)
    int ans = upper_bound(-1, MAX);
    if (ans <= 0)
        printf("0\n");
    else
        printf("%d\n", ans);
}


Measured memory_bytes: 1732
fun main(args: Array<String>){
    var s = readLine()!!
    val t = readLine()!!
    if(t.length > s.length){
        println("UNRESTORABLE")
        return
    }

    for(i in s.length - t.length downTo 0){
        var f = true
        var si = i
        for(j in 0 until t.length){
            f = f && (s[si] == '?' || s[si] == t[j])
            si++
        }
        if(f){
            s = s.replaceRange(i, i+t.length, t)
            s = s.replace('?', 'a')
            println(s)
            return
        }
    }
    println("UNRESTORABLE")
}

Measured memory_bytes: 33772
#include <bits/stdc++.h>
#define pii std::pair<int,int>
#define mp std::make_pair
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
int n,x[250005],y[250005],G[505][505],d[505][505];
int ans = 0;



void bfs(int x,int y){
	std::deque<pii>q;
	q.push_back(mp(x,y));
	while (!q.empty()) {
		pii u = q.front(); q.pop_front();
		for (int dr=0;dr<4;++dr) {
			int x1 = u.first + dx[dr];
			int y1 = u.second + dy[dr];
			if (x1 < 1 || x1 > n || y1 < 1 || y1 > n) continue;
			if (d[x1][y1] > d[u.first][u.second] + G[x1][y1]) {
				d[x1][y1] = d[u.first][u.second] + G[x1][y1];
				if (G[x1][y1]) q.push_back(mp(x1,y1));
				else q.push_front(mp(x1,y1));
			}
		}
	}
}

int main(){
	scanf("%d",&n);
	for (int i=1;i<=n*n;++i) {
		int p;
		scanf("%d",&p);
		x[i] = (p-1)/n + 1;
		y[i] = (p-1)%n + 1;
	}
	for (int i=1;i<=n;++i)
	for (int j=1;j<=n;++j) {
		d[i][j] = std::min( { i, j, n-i+1, n-j+1 } ) ;
		G[i][j] = 1;
	}
	for (int i=1; i <= n*n; i++) {
		d[x[i]][y[i]] --; G[x[i]][y[i]] = 0;
		ans += d[x[i]][y[i]];
		bfs(x[i],y[i]);
	}printf("%d",ans);
	return 0;
}



Measured memory_bytes: 8216
/*================================================================
rehtegot!
*   
*   File Name：e.cpp
*   Author：YaliKiWi
*   Date：2019年10月27日
*   Discribe：
*
================================================================*/


#include<bits/stdc++.h>
using namespace std;
#define fo(i,s,e) for(register int i=s,i%:%:_end=e;i<=i%:%:_end;i++)
#define max_(x,y) ((x)>(y)?(x):(y))
#define min_(x,y) ((x)<(y)?(x):(y))
#define dd double
#define ull unsigned long long
#define ll long long
#define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
#define maxn 200010
#define int __int128
#define inf 1e12
int x[maxn],y[maxn],n,k,zz;
inline bool cmp(int xx,int xy){
	return xx>xy;
}
inline int read(){
    char ch;
    int f=1,x=0;
    ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return f*x;
}
void pr(int x){
    if(x<0){putchar('-');pr(-x);}
    else{if(x/10)pr(x/10);putchar(x%10+'0');}
}
int ans=inf,tot;
inline bool chk(int w){
	int cnt=0;
	fo(i,1,n){
		int reg=w/y[i];
		if(reg>x[i])
			continue;
		else 
			cnt+=x[i]-reg;
		if(cnt>k)
			return 0;
	}
	return 1;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	n=read();
	k=read();
	fo(i,1,n)
		x[i]=read(),tot+=x[i];
	fo(i,1,n)
		y[i]=read();
	if(tot<=k){
		printf("0");
		return 0;
	}
	sort(x+1,x+n+1);
	sort(y+1,y+n+1,cmp);
	int l=1,r=inf;
	while(l<=r){
		int mid=(l+r)>>1;
		if(chk(mid)){
			ans=min_(ans,mid);
			r=mid-1;
		}
		else
			l=mid+1;
	}
	pr(ans);
	return 0;
}

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

int main(){

int N,D;
  cin >> N >> D;
  vector<vector<int>> X(N, vector<int>(D));
  for(int i=0;i<N;i++){
    for(int j=0;j<D;j++){
     cin >> X[i][j];
    }
  }
  int ans=0;
  for(int i=0;i<N;i++){
    for(int j=i+1;j<N;j++){
      int norm =0;
      for(int k=0;k<D;k++){
      int diff = abs(X[i][k]-X[j][k]);
        norm+=diff*diff;
      }
    
      bool flag=false;
      for(int k=0;k<=norm;k++){
        if(k*k==norm) flag=true;
      }
      if(flag) ans++;
      
      
    }  
  }
  cout << ans << endl;
}

Measured memory_bytes: 3656
using System;

namespace ABC094C
{
    class Program
    {
        static void Main(string[] args)
        {
            string s1 = Console.ReadLine();
            string s2 = Console.ReadLine();

            int N = int.Parse(s1);
            string[] ss = s2.Split(' ');

            int[] wrk = new int[N];
            int[] num = new int[N];

            int x = 0;
            for (int i = 0; i < N; i++)
            {
                x = int.Parse(ss[i]);
                wrk[i] = x;
                num[i] = x;
            }

            Array.Sort(num);
            Array.Reverse(num);

            int res = 0;
            for (int i = 0; i < N; i++)
            {
                int cp = N / 2 - 1;

                if (num[cp] <= wrk[i])
                {
                    res = num[cp + 1];
                }
                else
                {
                    res = num[cp];
                }

                Console.WriteLine(res);
            }

            Console.ReadLine();
        }
    }
}


Measured memory_bytes: 35932
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<tuple>
#include<map>
#include<queue>
#include<math.h>
#include<numeric>
#include<iomanip>
#define rep(i, n) rep2(i,0,n)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define PI acos(-1);
typedef long long ll;
using namespace std;
const int MOD=1000000007;
//scanf("%d", &a); '\n';


int main() {
	ll a, b, k;
	cin >> a >> b >> k;
	ll j = 0;
	if (a >= k) a -= k;
	else {
		k -= a;
		a = 0;
		
		if (b >= k) b -= k;
		else b = 0;
	}
	cout << a <<" "<< b;
	}

	

Measured memory_bytes: 256
N=int(input())
a=[0]*N
b=[0]*N
c=[0]*N
for i in range(N):
    a[i],b[i],c[i] = map(int,input().split())
a= [0]+a
b= [0]+b
c= [0]+c
    
dp=[[0]*(N+1) for _ in range(3)]
for i in range(1,N+1):
    dp[0][i] = max(dp[1][i-1],dp[2][i-1])+a[i]
    dp[1][i] = max(dp[0][i-1],dp[2][i-1])+b[i]
    dp[2][i] = max(dp[0][i-1],dp[1][i-1])+c[i]
maxi=0
for k in dp:
    maxi=max(maxi,k[-1])
print(maxi)

Measured memory_bytes: 26692
#define TEMPLATE_USED
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef vector<pl> vp;
const ll INF=1001001001;
const ll LINF=1001001001001001001;
const ll D4[]={0,1,0,-1,0};
const ll D8[]={0,1,1,0,-1,-1,1,-1,0};
#define _overload3(_1,_2,_3,name,...) name
#define _rep2(i,n) for(ll i=0;i<(n);++i)
#define _rep3(i,a,b) for(ll i=(ll)(a);i<(ll)(b);++i)
#define rep(...) _overload3(__VA_ARGS__,_rep3,_rep2)(__VA_ARGS__)
#define _repe2(i,n) for(ll i=0;i<=(ll)(n);++i)
#define _repe3(i,a,b) for(ll i=(ll)(a);i<=(ll)(b);++i)
#define repe(...) _overload3(__VA_ARGS__,_repe3,_repe2)(__VA_ARGS__)
#define _rrep2(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define _rrep3(i,a,b) for(ll i=(ll)(b)-1;i>=(ll)(a);i--)
#define rrep(...) _overload3(__VA_ARGS__,_rrep3,_rrep2)(__VA_ARGS__)
#define _rrepe2(i,n) for(ll i=(ll)(n);i>=0;i--)
#define _rrepe3(i,a,b) for(ll i=(ll)(b);i>=(ll)(a);i--)
#define rrepe(...) _overload3(__VA_ARGS__,_rrepe3,_rrepe2)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
template<class T>
bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>
bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}


void solve();

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

void solve(){
    char c;cin>>c;
    if(isupper(c))cout<<'A'<<endl;
    else cout<<'a'<<endl;
}


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

int main() {

int D;
cin >> D ;

int c[26+1]; //満足度の下がりやすさ
for(int i = 1; i < 26+1 ; i++){
  cin >> c[i];
}

int s[D+1][26+1]; //満足度の増加量(D日目,タイプ)
for(int i = 1; i < (D+1); i ++){
  for(int j = 1; j <26+1; j++){
    cin >> s[i][j];
  }
}

int S = 0; //満足度

int t[D+1]; //d日目に開催するコンテストのタイプ
for(int i = 1; i < (D+1); i++){
    cin >> t[i];
}

int last[26+1] = {};//最後にコンテストを開催した日

for(int d=1; d < (D+1); d++){
  S += s[d][t[d]];
  last[t[d]] = d;
  for(int i=1; i < 26+1; i++){
      S -= c[i] * (d - last[i]);
  }
}

int M;//変更数
cin >> M;
int day[M+1];//変更する日
int q[M+1];//変更後のタイプ

for(int i=1; i < M+1; i++){
  S=0;
  int last[26+1] = {};
  cin >> day[i] >> q[i];
  t[day[i]] = q[i];
  for(int d=1; d < (D+1); d++){
    S += s[d][t[d]];
    last[t[d]] = d;
    for(int j=1; j < 26+1; j++){
        S -= c[j] * (d - last[j]);
    }
  }
  cout << S <<endl;
}

return 0;
}

Measured memory_bytes: 4380
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
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; }
 
/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    ごちゃごちゃ場合分けを考える前に全探索は考えましたか？
*/
 
const ll mod = 1e9+7;

void chmod(ll &M){
    if(M >= mod) M %= mod;
    else if(M < 0){
        M += (abs(M)/mod + 1)*mod;
        M %= mod;
    }
}

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

    string s; cin >> s;
    int n = s.length();
    s = '0' + s;
    vector<vector<int>> dp(n+2, vector<int>(4, -1)); // dp[i][j] := i文字目までを考える、最後の分割を[i-j, i]とした場合の条件を満たす最大の分割数

    dp[1][0] = 1;
    dp[2][1] = 1;
    dp[3][2] = 1;
    dp[4][3] = 1;
    for(int i=2; i<=n; ++i){
        for(int j=0; j<4; ++j){
            if(i-j <= 0) continue;

            if(i-2*j-1>0  &&  s.substr(i-2*j-1, j+1) != s.substr(i-j, j+1)){
                for(int k=0; k<4; ++k) if(i-j-1-k>0) chmax(dp[i][j], dp[i-j-1][k]+1);
            }
            else{
                for(int k=0; k<4; ++k) if(i-j-1-k>0 && k!=j) chmax(dp[i][j], dp[i-j-1][k]+1);
            }
        }
    }

    int ans = 0;
    for(int j=0; j<4; ++j) chmax(ans, dp[n][j]);
    cout << ans << endl;

    // for(int i=1; i<=n; ++i){
    //     for(int j=0; j<4; ++j){
    //         cout << dp[i][j] << ' ';
    //     }
    //     cout << endl;
    // }

    
    return 0;
}



Measured memory_bytes: 11344
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAXN 15
char s[MAXN];
int main()
{
	scanf("%s",s+1);
	int len=strlen(s+1);
	if(s[1]!='A')
	{
		printf("WA\n");
		return 0;
	}
	bool f=0;
	for(int i=2;i<=len;i++)
	{
		if(!f&&i>=3&&i<=len-1&&s[i]=='C') {f=1;continue;}
		if(f&&i>=3&&i<=len-1&&s[i]=='C') 
		{
			printf("WA\n");
			return 0;
		}
		if(s[i]<'a'||s[i]>'z')
		{
			printf("WA\n");
			return 0;
		}
	}
	if(f==0){
			printf("WA\n");
			return 0;
		}
	printf("AC\n");
	return 0;
}

Measured memory_bytes: 128
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10000000)

N,K=map(int,input().split())

A=list(map(int,input().split()))
A.sort()

mod=10**9+7
cand=[0]

#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

def comb(n):
    if n==N-1:
        return 0
    
    if n<K-2:
        cand.append(0)
    elif n==K-2:
        cand.append(1)
    else:
        cand.append((cand[-1]*n)%mod*mod_inv((n-K+2),mod)%mod)
        
    comb(n+1)
    
    return 0

comb(0)

for i in range(N-1):
    cand[i+1]=cand[i]+cand[i+1]

up=sorted(A)
down=sorted(A,reverse=True)
down=list(map(lambda x:-x,down))

ans=0
for i in range(N):
    ans+=(up[i]+down[i])*cand[i]

print(int(ans%mod))

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

using namespace std;
typedef long long ll;
#define int ll

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; }

#define REP(i,n) for(int i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const double DINF = std::numeric_limits<double>::infinity();
const int MOD = 1000000007;
const int MAX_N = 100010;

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

    int A, B, N;
    cin >> A >> B >> N;

    int x = min(B - 1, N);
    int ans = A * x / B;
    printf("%lld\n", ans);

    return 0;
}


Measured memory_bytes: 3784
for$i(0..2499){
	push@_,map$i*12+$_,2,10,3,9,4,8,6,12
}
$N=<>;
$,=$";
if($N==3){
	print 2,5,63
}elsif($N%2){
	print@_[-1..$N-2]
}else{
	print@_[0..$N-1]
}


Measured memory_bytes: 2048
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm> // sort

#define REP(i, n) for (long long i = 0; i < (n); i++) 
typedef long long ll;
static const ll MOD = 1000000007;
static const ll INF = 1000000000000000000LL;
using namespace std;

//arc070_c
//i-1秒からi秒にかけて、i移動できるカンガルー
//0秒から1秒の間は1移動できる。1秒から2秒の間は2移動できる
//なにも考えずにすべて、足す
//ある数 s を足したときを出力する
//ちょうどXに止まらなくて良いか → sを足したときのあまりtは、s以下といえる
//s以下はすでに足してあるので、tを足さなかったことにすればよい
int main(){
  ll X,res;
  cin >> X;

  ll sum = 0;

  for(ll i = 1; i <= X; i++)
  {
    sum += i;
    if(sum >= X)
    {
      cout << i << endl;
      break;
    }
  }

  return 0;
}

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

int main() {
  int A,B,C,X,cnt=0;
  cin >> A >> B >> C >> X;
  for(int i=0; i<=A; i++) {
    for(int j=0; j<=B; j++) {
      for(int k=0; k<=C; k++) {
        if(500*i+100*j+50*k==X) {
          cnt++;
        }
      }
    }
  }
  cout << cnt << endl;
}


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

using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

pll A[55];
pll B[55];
ll C[55];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, M;
    cin >> N >> M;
    REP(i, N) {
        cin >> A[i].first >> A[i].second;
    }
    REP(i, M) {
        cin >> B[i].first >> B[i].second;
    }

    REP(i, N) {
        ll n = 0;
        REP(j, M) {
            ll d0 = abs(A[i].first - B[j].first) + abs(A[i].second - B[j].second);
            ll d1 = abs(A[i].first - B[n].first) + abs(A[i].second - B[n].second);
            if (d0 < d1)
                n = j;
        }
        C[i] = n + 1;
    }

    REP(i, N) {
        cout << C[i] << endl;
    }

    return 0;
}

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

#define PI 3.14159265359
#define rep(i,a,n) for(int i=a;i<(int)n;++i)
#define SZ(x) ((int)(x).size())	//size() unsigned -> int
#define descSort(a) sort(a.begin(),a.end(),std::greater<int>())
using namespace std;
typedef long long ll;
const ll INF = 1e9 + 7;

int main(void){
    ll n;
    cin>>n;
    vector<int> cnt(n+1,0);
    ll ans=0;
    for(ll i=1;i<=n;i++){
        for(int j=1;j*i<=n;j++){
            cnt[i*j]++;
        }
        ans+=i*cnt[i];
    }    
    cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 42336