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

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();

		int[] oddCnt = new int[100100];
		int[] evenCnt = new int[100100];

		Arrays.fill(oddCnt, 0);
		Arrays.fill(evenCnt, 0);

		for (int i = 0; i < N; i++) {
			int v = sc.nextInt();

			if (i % 2 == 0) evenCnt[v]++;
			else oddCnt[v]++;
		}

		int oddMax = 0, oddMaxId = 0, odd2ndMax = 0;
		int evenMax = 0, evenMaxId = 0, even2ndMax = 0;

		for (int i = 0; i < 100100; i++) {
			if (evenMax <= evenCnt[i]) {
				even2ndMax = evenMax;
				evenMax = evenCnt[i];
				evenMaxId = i;
			} else if (even2ndMax <= evenCnt[i]) {
				even2ndMax = evenCnt[i];
			}
			if (oddMax <= oddCnt[i]) {
				odd2ndMax = oddMax;
				oddMax = oddCnt[i];
				oddMaxId = i;
			} else if (odd2ndMax <= oddCnt[i]) {
				odd2ndMax = oddCnt[i];
			}
		}

		if (evenMaxId != oddMaxId) {
			System.out.println(N - evenMax - oddMax);
		} else if (even2ndMax > odd2ndMax) {
			System.out.println(N - even2ndMax - oddMax);
		} else {
			System.out.println(N - evenMax - odd2ndMax);
		}
	}
}


Measured memory_bytes: 52836
/*

*/
#include<iostream>
#include<iomanip>
#include<ios>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<algorithm>
#include<utility>
#include<math.h>
#include<cstdlib>
#define rep(i, n) for(int i=0;i<n;i++)
#define repb(i, a, b) for(int i=a;i<b;i++)
#define MAX_N 10000

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

const int INF = 1<<30;
const ll MOD = ll(1e9+7);

int main(){
  string s, t;cin>>s>>t;
  int ans=0;
  rep(i, (int)s.size()){
    ans += int(s[i]!=t[i]);
  }
  cout<<ans<<endl;
  // system("read -n 1 -s -p \"Press any key to continue...\"");
}


Measured memory_bytes: 3800
#include<iostream>
using namespace std;
int main(){
    int a,b,x;
    cin >> a >> b;
    x = a * b;
    if(x %2 == 1){
        cout << "Odd" << endl;
    }else
    {
        cout << "Even" << endl;
    }
    return 0;
    
}

Measured memory_bytes: 3136
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <unordered_set>
#include <cstring>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <bitset>
using namespace std;
typedef long long ll;
const int maxn = 55;

ll c[maxn][maxn];

int main() {
#ifdef suiyuan2009
  freopen("in.cpp","r",stdin);
#endif
  for(int i=0;i<maxn;i++)c[i][0]=c[i][i]=1;
  for(int i=1;i<maxn;i++)
  for(int j=1;j<i;j++)
  c[i][j]=c[i-1][j-1]+c[i-1][j];
  int n,p;
  cin>>n>>p;
  int odd=0;
  for(int i=0;i<n;i++){
    int x;
    cin>>x;
    if(x&1)odd++;
  }
  ll ret=1LL<<(n-odd);
  int start=p;
  ll tmp=0;
  for(int i=start;i<=odd;i+=2)tmp+=c[odd][i];
  cout<<ret*tmp<<endl;
  return 0;
}


Measured memory_bytes: 764
#include <bits/stdc++.h>
using namespace std;
string s;
long k;

int main(){
  cin >> s >> k;
  int one;
  for(one = 0; one < s.length(); one++){
	if(s[one] != '1'){
	  break;
    }
  }
  if(k <= one){
	printf("1\n");
  }else{
	printf("%c\n", s[one]);
  }
  return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MAX (ll)(4e3 + 4)
#define MOD (ll)(1e9 + 7)
#define INF (ll)(1e18 + 3)
#define PI (double)(3.14159265)

using namespace std;
using ll = long long;
using ld = long double;

int main () {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		if (i * (1.08) >= n && i * (1.08) < n + 1) {
			cout << i << "\n";
			return 0;
		}
	}
	cout << ":(\n";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<int(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define show(x) cout<< #x << " = " << x << endl
using namespace std;

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

int vx[]={0,0,-1,1};
int vy[]={1,-1,0,0};
int dx[]={1,0,-1,1,-1,1,0,-1};
int dy[]={1,1,1,0,0,-1,-1,-1};

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

const ll mod=1e9+7;
const int INF=INT_MAX/2;
const int N_MAX=100010;

int main(){
	int n,k;
	cin>>n>>k;
	vector<int> a(n);
	REP(i,n)cin>>a[i];
	int ans=1;
	if((n-k)%(k-1)==0)ans+=(n-k)/(k-1);
	else ans+=(n-k)/(k-1)+1;
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(void)
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, M, sum = 0;
  cin >> N >> M;
  vector<int> num (N);
  for (int i = 0; i < N; i++)
    cin >> num[i];
  sort(num.begin(), num.end());
  for (int i = 0; i < M; i++)
    sum += num[i];
  cout << sum << '\n';
  return 0;
}


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

int main() {
	int H,W;
	cin >> H >>W;
  for(int i=0;i<W+2;i++){
  cout <<"#";
  }
  cout << endl;
  
 for (int i =0; i<H ;i++){
  cout <<"#";
  string H;
   cin >> H;
   cout << H;
 
   cout <<"#"<<endl;
 }
  
   
   
   
   
   
    for(int i=0;i<W+2;i++){
  cout <<"#";
  }
  cout << endl;
}
 

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

int main() {
  int N;
  cin >> N;
  for (int i = 0; i < 100; i++) {    
    if ( N <= 1000 ) {
      break;
    }
      N -= 1000;
    }
  N = 1000 - N;
  cout << N << endl;
}


Measured memory_bytes: 3596
import java.util.*;
//import java.util.stream.Collectors;

public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		char c = sc.next().charAt(0);
		System.out.println(c == 'A' ? 'T' : (c == 'T' ? 'A' : (c == 'C' ? 'G' : 'C')));
	}
}


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

int main() {
  int n, m;
  cin >> n >> m;
  int total = n + m;
  int pairs = total * (total - 1) / 2;
  int odd = n * m;
  cout << pairs - odd << endl;
  return 0;
}

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

int main(void){
    int n; cin >> n;
    int Max, Min;
    for(int i = 0; i < n; i++){
        int a; cin >> a;
        if(i == 0){
            Max = Min = a;
        }else{
            Max = max(Max, a);
            Min = min(Min, a);
        }
    }

    cout << Max - Min << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

const int MAX = 200;
int in[MAX][3];
int point[MAX];
int N;

bool find(int t, int n){

  for(int i = 0; i < N; i++)
    if(i != n && in[n][t] == in[i][t]) return false;
  return true;
}

int main(){

  cin >> N;
  for(int i = 0; i < N; i++)
    for(int j = 0; j < 3; j++)
      cin >> in[i][j];

  for(int i = 0; i < 3; i++)
    for(int j = 0; j < N; j++)
      if(find(i,j)) point[j]+=in[j][i];

  for(int i = 0; i < N; i++) cout << point[i] << endl;

  return 0;
}

Measured memory_bytes: 1164
N = int(input())
A = list(map(int, input().split()))
A2 = []
Z = []
ans = 0
zerocnt = 0
for ai in A:
    if ai == 0:
        zerocnt += 1
    elif zerocnt >= 1:
        A2 += [0]
        Z += [zerocnt]
        ans += (zerocnt * (zerocnt+1)) // 2
        zerocnt = 0
    if ai != 0:
        A2 += [ai]
        Z += [1]
        ans += 1

if zerocnt >= 1:
    A2 += [0]
    Z += [zerocnt]
    ans += (zerocnt * (zerocnt+1)) // 2
    zerocnt = 0

for i, ai in enumerate(A2):
    aixor = ai
    sumA = ai
    for j in range(i+1, min(i+41, len(A2))):
        aj = A2[j]
        aixor = aixor ^ aj
        sumA += aj
        if aixor != sumA:
            break
        else:
            ans += (Z[i] * Z[j])
        
print(ans)

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

int main() {
  int r;
  cin >> r;
  cout << r * r << endl;
  return 0;
}

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

using ll = long long;
#define rep(i, j) for(int i=0; i < (int)(j); i++)
#define repeat(i, j, k) for(int i = (j); i < (int)(k); i++)
#define debug(x) cerr << #x << " : " << x << endl

template<class T> bool set_max(T &a, const T &b) { return a < b  ? a = b, true : false; }
// vector
template<class T> istream&
operator >> (istream &is , vector<T> &v) { for(T &a : v) is >> a; return is; }



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

    int N, K; cin >> N >> K;
    vector<int> A(N); cin >> A;
    
    vector<vector<int>> children(N);
    repeat(i, 1, N) children[A[i] - 1].push_back(i);
    
    int ans = A[0] != 1;
    A[0] = 1;

    function<int(int)> dfs = [&] (int now) {
        int max_depth = 0;
        for(int c : children[now]) {
            set_max(max_depth, dfs(c));
        }
        max_depth += 1;
        if(max_depth >= K and A[now] != 1) {
            ans ++;
            return 0;
        }
        return max_depth;
    };
    dfs(0);
    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 12416
@exp ||= []

def exp(n)
  return @exp[n] if @exp[n]

  @exp[n] = 1.upto(n).inject(0, &:+).to_f / n
end

n, k = gets.chomp.split(" ").map(&:to_i)
ps = gets.chomp.split(" ").map(&:to_i)

e = ps.map {|pi| exp(pi) }

q = Queue.new
max = 0

sum = 0
n.times {|i|
  sum -= q.pop if q.size == k

  v = e[i]
  sum += v
  q << v

  max = sum if max < sum
}

puts max


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

struct city {
    int id, year;
    city(int i, int y) : id(i), year(y) {}
    bool operator<(city const& that) const {
        return year < that.year;
    }
};

int main() {
    int n, m; cin >> n >> m;
    vector<vector<city>> cmp(n);
    for(int i = 0; i < m; ++i) {
        int p, y; cin >> p >> y;
        cmp[p - 1].emplace_back(i, y);
    }
    vector<string> ans(m);
    for(int pi = 0; pi < n; ++pi) {
        auto& cs = cmp[pi];
        sort(begin(cs), end(cs));
        for(int x = 1; x <= (int)cs.size(); ++x) {
            string s1 = to_string(pi + 1);
            string s2 = to_string(x);
            while(s1.size() < 6u) s1 = "0" + s1;
            while(s2.size() < 6u) s2 = "0" + s2;
            ans[cs[x - 1].id] = s1 + s2;
        }
    }

    for(auto& s : ans) {
        cout << s << endl;
    }
}


Measured memory_bytes: 12416
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector> 
#include <cstring>
#include <queue>
#include <ctime>

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1000000000;
const int maxN = 100010;
int a[maxN];
int main()
{
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	sort(a+1,a+1+n);
	reverse(a+1,a+1+n);
	int ans = 0;
	for(int i=1;i<=k;i++)
	{
		ans += a[i];
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n;
int mn, sum;
int main()
{
    mn = 23333;
    cin >> n;
    while (n --)
    {
        int a;
        cin >> a;
        sum += a;
        if (a % 10) mn = min(mn, a);
    }
    if (sum % 10 == 0) sum -= mn;
    if (mn == 23333) sum = 0;
    cout << sum;
}


Measured memory_bytes: 256
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
using ld = long double;
template<typename T> using V = vector<T>;
template<typename T> using VV = vector<vector<T>>;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,a,n) for(ll i=a;i<(ll)(n);++i)
#define repr(i,a,n) for(ll i=n-1;(ll)a<=i;--i)
#define ENDL '\n'
typedef pair<int,int> Pi;
typedef pair<ll,ll> PL;
constexpr ll mod = 1000000007;
constexpr ll INF = 1000000099;
constexpr ll LINF = (ll)(1e18 +99);
const vector<ll> dx={-1,1,0,0},dy={0,0,-1,1};
template<typename T,typename U> inline bool chmin(T& t, const U& u){if(t>u){t=u;return 1;}return 0;}
template<typename T,typename U> inline bool chmax(T& t, const U& u){if(t<u){t=u;return 1;}return 0;}
template<typename T> inline T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T,typename Y> inline T mpow(T a, Y n) {
  T res = 1;
  for(;n;n>>=1) {
    if (n & 1) res = res * a;
    a = a * a;
  }
  return res;
}

VV<int> e;
V<int> ans,st,ue;
V<bool> used;

void dfs1(int now,int pre){
  if(st[now]>ue[now]){
    cout<<"No"<<ENDL;
    exit(0);
  }

  for(auto&& nex:e[now]){
    if(pre==nex)continue;

    chmax(st[nex],st[now]-1);
    chmin(ue[nex],ue[now]+1);
    dfs1(nex,now);
    chmax(st[now],st[nex]-1);
    chmin(ue[now],ue[nex]+1);
    
  }
}


void dfs2(int now,int pre){
  if(st[now]>ue[now]){
    cout<<"No"<<ENDL;
    exit(0);
  }

  ans[now]=st[now];
  for(auto&& nex:e[now]){
    if(pre==nex)continue;
    if(st[nex]==ans[now]){
      cout<<"No"<<ENDL;
      exit(0);
    }

    chmax(st[nex],ans[now]-1);
    chmin(ue[nex],ans[now]+1);
    dfs2(nex,now);
  }
}

signed main(){
  cin.tie(0);ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(20);
  int n;cin>>n;
  e.assign(n,V<int>(0));
  ans.assign(n,INF),st.assign(n,-INF),ue.assign(n,INF);
  used.assign(n,false);

  rep(i,0,n-1){
    int a,b;cin>>a>>b;
    a--;b--;
    e[a].pb(b);
    e[b].pb(a);
  }

  int k;cin>>k;
  rep(i,0,k){
    int v,p;cin>>v>>p;
    v--;
    ans[v]=st[v]=ue[v]=p;
    used[v]=true;
  }

  dfs1(0,-1);
  dfs2(0,-1);

  cout<<"Yes"<<ENDL;
  rep(i,0,n){ 
    cout<<ans[i]<<ENDL;
  }

}
//! ( . _ . ) ! 
//CHECK overflow,vector_size,what to output?

Measured memory_bytes: 13824
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
char g[105][105];
int h,w;
int ans=0;
int dp[105][105];
int main(){
	scanf("%d%d",&h,&w);
	for(int i=1;i<=h;i++)
	for(int j=1;j<=w;j++)cin>>g[i][j];
	memset(dp,inf,sizeof(dp));
	if(g[1][1]=='#')dp[1][1]=1;
	else dp[1][1]=0;
	for(int i=1;i<=h;i++)
	for(int j=1;j<=w;j++){
		if(i>1){
			if(g[i][j]=='#'&&g[i-1][j]=='.')dp[i][j]=min(dp[i][j],dp[i-1][j]+1);
			else dp[i][j]=min(dp[i][j],dp[i-1][j]);
		}
		if(j>1){
			if(g[i][j]=='#'&&g[i][j-1]=='.')dp[i][j]=min(dp[i][j],dp[i][j-1]+1);
			else dp[i][j]=min(dp[i][j],dp[i][j-1]);
		}
	}
	printf("%d\n",dp[h][w]);
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;

struct Tree
{
	int parent;
	int left;
	int right;
};
Tree tree[100000];

void preorder(int n) {
	printf(" %d", n);
	if (tree[n].left != -1) preorder(tree[n].left);
	if (tree[n].right != -1) preorder(tree[n].right);
}

void inorder(int n) {
	if (tree[n].left != -1) inorder(tree[n].left);
	printf(" %d", n);
	if (tree[n].right != -1) inorder(tree[n].right);
}

void Postorder(int n) {
	if (tree[n].left != -1) Postorder(tree[n].left);
	if (tree[n].right != -1) Postorder(tree[n].right);
	printf(" %d", n);
}

int main(void) {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		tree[i].parent = -1;
		tree[i].left = -1;
		tree[i].right = -1;
	}
	for (int i = 0; i < n; i++) {
		int pa, left, right;
		cin >> pa >> left >> right;
		tree[pa].left = left;
		tree[pa].right = right;
	if (left == -1) { tree[right].parent = pa; }
		else if (right == -1) {
			tree[left].parent = pa;
		}
		else
		{
			tree[left].parent = pa;
			tree[right].parent = pa;
		}
	}
	int key = 0;
	for (int i = 0; i < n; i++) {
		if (tree[i].parent == -1) {
			key = i;
			break;
		}
	}
	cout << "Preorder" << endl;
	preorder(key);
	cout <<endl <<"Inorder" << endl;
	inorder(key);
	cout <<endl<< "Postorder" << endl;
	Postorder(key);
	cout<<endl;
}


Measured memory_bytes: 3200
#include <stdio.h>

int main(){
  int k,n;
  scanf("%d %d",&k,&n);
  int A[n+1],i,j,a;
  for(i=0;i<n;i++){
    scanf("%d",&j);
    A[i]=j;
  }
  A[n]=A[0]+k;
  a=0;
  for(i=0;i<n;i++){
    if(A[i+1]-A[i]>a){
      a=A[i+1]-A[i];
    }
  }
  i=k-a;
  printf("%d\n",i);
  return 0;
}

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

struct record {
  int t, n, s;
};

int main() {
  int N, M;
  while (cin >> N >> M and N) {
    int r;
    cin >> r;
    vector<int> ts(r), ns(r), ms(r), ss(r);
    for (int i = 0; i < r; i++) {
      cin >> ts[i] >> ns[i] >> ms[i] >> ss[i];
      ms[i]--, ns[i]--;
    }

    vector< vector<record> > students(M);
    for (int i = 0; i < r; i++) {
      record rd;
      rd.t = ts[i], rd.n = ns[i], rd.s = ss[i];
      students[ms[i]].push_back(rd);
    }

    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
      int ts, te, m;
      cin >> ts >> te >> m;
      m--;
      
      vector<int> times(1270);
      for (int i = 0; i < 1270; i++) {
        times[i] = 0;
      }
      vector<record> records = students[m];
      for (record rd : records) {
        if (rd.s == 1) {
          times[rd.t]++;
        } else if (rd.s == 0) {
          times[rd.t]--;
        }
      }

      for (int i = 1; i < 1270; i++) {
        times[i] += times[i-1];
      }

      int ans = 0;
      for (int i = ts; i < te; i++) {
        if (times[i] > 0) {
          ans++;
        }
      }

      cout << ans << endl;
    }
  }
}

Measured memory_bytes: 1476
#ABC091

n = int(input())
s = [input() for _ in range(n)]
m = int(input())
t = [input() for _ in range(m)]
l = []

for i in set(s):
    l.append([s.count(i)-t.count(i),i])
l = sorted(l,reverse=True)


print(max(l[0][0],0))

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

#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x)  cerr << #x << " = " << x << endl
using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ld PI = 3.14159265359;

const ll MOD = (ll) 998244353ll;
const ll MAXN = (ll) 5e4 + 10;
const ll INF = (ll) 1e17;
const ld EPS = (ld) 1e-8;

pll a[MAXN];

bool CMP(pll x, pll y){
	ll upx, upy;
	upx = x.F;
	upy = y.F;
	upx = min(upx, y.F - x.S);
	upy = min(upy, x.F - y.S);
	return upx > upy;
}

ll dp[2][MAXN];

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	
	ll n;
	cin >> n;
	for(int i = 0; i < n; i++) cin >> a[i].F >> a[i].S;
	sort(a, a + n, CMP);
	
	//for(int i = 0; i < n; i++) cerr << a[i].F << ' ' << a[i].S << '\n';
	
	for(int i = 0; i < 2;i++) fill(dp[i], dp[i] + n + 1, INF);
	
	dp[0][0] = 0;
	for(int i = 1; i <= n; i++){
		//fill(dp[i & 1], dp[i & 1] + n + 1, INF);
		dp[i & 1][0] = 0;
		for(int j = 1; j <= n; j++){
			dp[i & 1][j] = INF;
			dp[i & 1][j] = min(dp[i & 1][j], dp[i & 1 ^ 1][j]);
			if(a[i - 1].F >= dp[i & 1 ^ 1][j - 1]){
				dp[i & 1][j] = min(dp[i & 1][j], dp[i & 1 ^ 1][j - 1] + a[i - 1].S);
			}
		}
	}
	
	//debug(dp[0][3]);
	
	ll ans = 0;
	for(int i = 1; i <= n; i++){
		if(dp[n & 1][i] != INF) ans = max(ans, (ll) i);
	}
	
	cout << ans;
	
	return 0;
}


/*

                                 ____              ,----..               ,----..
   ,---,                       ,'  , `.           /   /   \             /   /   \
  '  .' \                   ,-+-,.' _ |          /   .     :           /   .     :
 /  ;    '.              ,-+-. ;   , ||         .   /   ;.  \         .   /   ;.  \
:  :       \            ,--.'|'   |  ;|        .   ;   /  ` ;        .   ;   /  ` ;
:  |   /\   \          |   |  ,', |  ':        ;   |  ; \ ; |        ;   |  ; \ ; |
|  :  ' ;.   :         |   | /  | |  ||        |   :  | ; | '        |   :  | ; | '
|  |  ;/  \   \        '   | :  | :  |,        .   |  ' ' ' :        .   |  ' ' ' :
'  :  | \  \ ,'        ;   . |  ; |--'         '   ;  \; /  |        '   ;  \; /  |
|  |  '  '--'          |   : |  | ,             \   \  ',  /          \   \  ',  /
|  :  :                |   : '  |/               ;   :    /            ;   :    /
|  | ,'                ;   | |`-'                 \   \ .'              \   \ .'
`--''                  |   ;/                      `---`                 `---`
                       '---'

*/


Measured memory_bytes: 384
#include <stdio.h>

int main(void) {

  int n;
  scanf("%d", &n);
  char s[7];
  int start = 0;
  int end = n-1;
  int q = (n-1)/2;
  int start_person;
  int end_person;
  int q_person;
  printf("0\n");
  fflush(stdout);
  scanf("%s", s);
  if (s[0] == 'V') {
    return 0;
  } else {
    if (s[0] == 'M') {
      start_person = 1;
    } else {
      start_person = 0;
    }
  }
  printf("%d\n", n-1);
  fflush(stdout);
  scanf("%s", s);
  if (s[0] == 'V') {
    return 0;
  } else {
    if (s[0] == 'M') {
      end_person = 1;
    } else {
      end_person = 0;
    }
  }
  while (1) {
    printf("%d\n", q);
    fflush(stdout);
    scanf("%s", s);
    if (s[0] == 'V') {
      return 0;
    } else {
      if (s[0] == 'M') {
        q_person = 1;
      } else {
        q_person = 0;
      }
    }
    if (((q-start)%2 == 1 && q_person == start_person) || ((q-start)%2 == 0 && q_person != start_person)) {
      end = q;
      end_person = q_person;
    } else {
      start = q;
      start_person = q_person;
    }
    q = (start+end)/2;
  }

  return 0;
}

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

using namespace std;

int a[200005], n, x;

main(){
    cin >> n;
    for (int i = 1; i < n; i++){
        cin >> x;
        a[x]++;
    }
    for (int i = 1; i <= n; i++)
        cout << a[i] << endl;
}

Measured memory_bytes: 4368
MOD = 1000000007

#互いに素な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 com(n, k):
    x = 1
    for i in range(k):
        x *= n - i
        x *= mod_inv(i+1,MOD)
        x %= MOD
    return x

n,a,b=map(int,input().split())

x = pow(2, n, MOD)
y = 1 + com(n, a) + com(n, b)
y %= MOD

print((x+MOD-y)%MOD)

Measured memory_bytes: 41964
#include<stdio.h>
#include<string>
#include<utility>
#include<iostream>
#include<queue>
#include<math.h>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<bitset>

using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0;i<(int)(n);i++)

int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    long long int v[55]={};
    long long int max=(-10000000*100);
    REP(i,n)scanf("%lld",&v[i]);
    for(int kkk=0;kkk<=k;kkk++){
        for(int nu=0;nu<=kkk/2;nu++){
            int act=kkk-nu*2;
            for(int i=act/2+(act%2!=0);i<=act;i++){
                int pull_num=i;
                int push_num=act-i;
                if(pull_num>n)continue;
                for(int j=0;j<=pull_num;j++){
                    int pl=j;
                    int pr=pull_num-j;
                    vector<long long int> pick;
                    for(int kk=0;kk<pl;kk++)pick.push_back(v[kk]);
                    for(int kk=n-1;kk>=n-pr;kk--)pick.push_back(v[kk]);
                    sort(pick.begin(),pick.end(),std::greater<long long int>());
                    /*
                    REP(i,pick.size()){
                        printf("%lld",pick[i]);
                    }
                    printf("\n");
                    */
                    REP(ii,push_num)pick.pop_back();
                    long long int sum=0;
                    REP(ii,pick.size())sum+=pick[ii];
                    //printf("%lld\n",sum);
                    if(max<sum)max=sum;
                }
            }
        }
    }
    printf("%lld\n",max);
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

main(){

int x,y,z,temp;

scanf("%d %d %d",&x,&y,&z);

if(x>y){
temp=x;
x=y;
y=temp;
}

if(y>z){
temp=y;
y=z;
z=temp;
}

if(x>y){
temp=x;
x=y;
y=temp;
}


printf("%d %d %d\n",x,y,z);

return 0;
}

Measured memory_bytes: 596
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
a=[0]*m
for i in range(n):
    for j in range(l[i][0]):
        a[l[i][j+1]-1]+=1
ans=0
for i in range(m):
    if a[i]==n:
        ans+=1
print(ans)

Measured memory_bytes: 9148
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"sort"
	"strconv"
)

type ab struct{ a, b int }
type abs []ab

func (a abs) Len() int           { return len(a) }
func (a abs) Less(i, j int) bool { return a[i].a < a[j].a }
func (a abs) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

func main() {
	N := nextInt()
	K := nextInt()
	var list []ab
	for i := 0; i < N; i++ {
		a := nextInt()
		b := nextInt()
		list = append(list, ab{a: a, b: b})
	}

	sort.Sort(abs(list))
	var total int
	for _, l := range list {
		total += l.b
		if total >= K {
			fmt.Println(l.a)
			return
		}
	}
}

// Input. ----------

var sc = bufio.NewScanner(os.Stdin)

func init() {
	sc.Buffer([]byte{}, math.MaxInt64)
	sc.Split(bufio.ScanWords)
}

func nextInt() int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}

	return i
}

func nextString() string {
	sc.Scan()
	if err := sc.Err(); err != nil {
		panic(err)
	}

	return sc.Text()
}

// ---------- Input.

// Util. ----------

func min(x, y int) int {
	return int(math.Min(float64(x), float64(y)))
}

func max(x, y int) int {
	return int(math.Max(float64(x), float64(y)))
}

// ---------- Util.


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

public class Main{

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int X = sc.nextInt();
        int Y = sc.nextInt();
        int rem = N-K;
        long ans = 0 ;
        if(rem>0)
            ans = K*X + (rem*Y);
        else
            ans = N*X;
        System.out.println(ans);
    }

}


Measured memory_bytes: 27056
#include<bits/stdc++.h>
using namespace std;
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(){
  int n;cin>>n;
  while(!is_prime(n)) n++;
  cout<<n;
}


Measured memory_bytes: 256
import math
import sys

input = sys.stdin.readline
a, b, c = map(int, input().split())
x = (a//2)*b*c
x = abs(abs(x-a*b*c)-x)
y = (b//2)*a*c
y = abs(abs(y-a*b*c)-y)
z = (c//2)*a*b
z = abs(abs(z-a*b*c)-z)

print(min(x, y, z))

Measured memory_bytes: 9156
#include <iostream>
#include<numeric>
#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
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)






int main() {
	string S;
	long long N;
	cin >> N;
	cin >> S;
	long long r = 0;
	long long g = 0;
	long long b = 0;
	rep(i, N) {
		if (S.at(i) == 'R') {
			r++;
		}
		else if (S.at(i) == 'G') {
			g++;
		}
		if (S.at(i) == 'B') {
			b++;
		}
	}
	long long s = r * g * b;
	for (long long i = 0; i < (N); i++) {
		for (long long j = 1; j < N; j++) {
			if (i + 2 * j < N && S.at(i) != S.at(j + i) && S.at(i) != S.at(i + 2 * j) && S.at(j + i) != S.at(j * 2 + i)) {
				s--;
			}
		}
	}
		cout << s << endl;
	


}

Measured memory_bytes: 3636
H,W= map(int,input().split())
emp_H= [['.']*(W+2)]
mine = [['.']+list(input())+ ['.'] for i in range(H)]
mine = emp_H + mine + emp_H

def count(ch):
  return 1 if ch == '#' else 0

for i in range(1,H+1):
  for j in range(1,W+1):
    if mine[i][j] == '#':
      continue
    else:
      mine[i][j] = count(mine[i-1][j-1])+count(mine[i][j-1])+count(mine[i+1][j-1])+count(mine[i-1][j])+count(mine[i][j])+count(mine[i+1][j])+count(mine[i-1][j+1])+count(mine[i][j+1])+count(mine[i+1][j+1])
for i in range(1,H+1):
  for j in range(1,W+1):
    print(mine[i][j],end='')
  print()



Measured memory_bytes: 3444
#include <bits/stdc++.h>
using namespace std;
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
template<class T> inline T sqr(T x) {return x*x;}
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long ll;
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(v, n) sort(v, v+n)
#define VSORT(v) sort(v.begin(), v.end())
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define INF 999999999
const double EPS = 1e-10;
const double PI  = acos(-1.0);
#define CLR(a) memset((a), 0 ,sizeof(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

int main(){
    cin.tie(0);
   	ios::sync_with_stdio(false);
    int n;
    string s;
    cin >> n>>s;
    int end=0;
    int a=0,b=0,c=0;
    int mcnt=0;
    int i=0;
    int res=0;
    while(1){
        if(s.at(i)==a+'0'&&mcnt==0){
            mcnt=1;
        }else if(s.at(i)==b+'0'&&mcnt==1){
            mcnt=2;
        }else if(s.at(i)==c+'0'&&mcnt==2){
            end=1;
            res++;
        }
        i+=1;
        if(i==n)end=1;
        if(end==1){
            end=0;
            i=0;
            mcnt=0;
            c+=1;
            if(c==10){
                c=0;
                b+=1;
                if(b==10){
                    b=0;
                    a+=1;
                    if(a==10){
                        break;
                    }
                }
            }
        }
    }
    cout<<res<<endl;
    return 0;
}

Measured memory_bytes: 384
require "set"
n = gets.chomp.to_i
s = gets.chomp

max = 0
(0..(n-2)).each do |i|
  x = s[0..i]
  y = s[(i+1)..-1]
  x_set = Set.new(x.split("").to_a)
  y_set = Set.new(y.split("").to_a)
  len = x_set.intersection(y_set).length
  max = len if len > max
end

puts max


Measured memory_bytes: 2044
def resolve():
    D = int(input())
    C = list(map(int, input().split()))
    S = [list(map(int, input().split())) for _ in range(D)]
    T = []
    last = [0 for _ in range(26)]
    
    def calc(day, typ):
        score = S[day][typ]
        for j in range(26):
            if j == typ:
                continue
            score -= C[j]*(day+1-last[j])
        return score

    for d in range(D):
        maxscore, maxcontest = -float("inf"), None
        for typ in range(26):
            _score = calc(d, typ)
            if maxscore < _score:
                maxscore = _score
                maxcontest = typ
        T.append(maxcontest)
    
    [print(t+1) for t in T]



if __name__ == '__main__':
    resolve()

Measured memory_bytes: 9544
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
const int MAXN = 1e3 + 5;
const int MAXM = 1e3 + 5;
const int MAXD = MAXN*3 + MAXM*3;

struct DSC
{
	int dsc[MAXD], cnt;
	DSC(void){ cnt=0;}
	inline int& operator [] (const int &x){ return dsc[x];}
	inline void insert(const int &x){ dsc[++cnt] = x;}
	inline void solve(void){ sort(dsc+1,dsc+cnt+1); cnt = unique(dsc+1,dsc+cnt+1)-dsc-1;}
	inline void find(int &x){ x = lower_bound(dsc+1,dsc+cnt+1, x) - dsc;}
}dsc;

struct Line
{
	int a,b,c;
}p[MAXN], q[MAXM];

struct Node
{
	int x,y;
};

bool rig[MAXD][MAXD], dwn[MAXD][MAXD];

queue<Node> que;
bool vis[MAXD][MAXD];
inline void push(int x,int y)
{
	if(x<=1 || y<=1 || x>dsc.cnt || y>dsc.cnt)
		printf("INF"), exit(0);
	if(vis[x][y]) return;
	vis[x][y] = 1;
	que.push((Node){x,y});
}

inline ll bfs(int sx,int sy)
{
	ll res=0;
	push(sx,sy);
	while(!que.empty())
	{
		int x=que.front().x, y=que.front().y;
		que.pop();
		res += (ll)(dsc[x]-dsc[x-1]) * (dsc[y]-dsc[y-1]);
		
		if(!dwn[x][y]) push(x+1,y);
		if(!rig[x][y]) push(x,y+1);
		if(!dwn[x-1][y]) push(x-1,y);
		if(!rig[x][y-1]) push(x,y-1);
	}
	return res;
}

int main(void)
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; ++i)
		scanf("%d%d%d",&p[i].a,&p[i].b,&p[i].c);
	for(int i=1; i<=m; ++i)
		scanf("%d%d%d",&q[i].a,&q[i].b,&q[i].c);
	
	int sx=0, sy=0;
	dsc.insert(0);
	for(int i=1; i<=n; ++i)
		dsc.insert(p[i].a), dsc.insert(p[i].b), dsc.insert(p[i].c);
	for(int i=1; i<=m; ++i)
		dsc.insert(q[i].a), dsc.insert(q[i].b), dsc.insert(q[i].c);
	dsc.solve();
	dsc.find(sx); dsc.find(sy);
	for(int i=1; i<=n; ++i)
		dsc.find(p[i].a), dsc.find(p[i].b), dsc.find(p[i].c);
	for(int i=1; i<=m; ++i)
		dsc.find(q[i].a), dsc.find(q[i].b), dsc.find(q[i].c);
	
	for(int i=1; i<=n; ++i)
	{
		int a=p[i].a, b=p[i].b, c=p[i].c;
		
		for(int j=a+1; j<=b; ++j)
			rig[j][c] = 1;
	}
	for(int i=1; i<=m; ++i)
	{
		int a=q[i].a, b=q[i].b, c=q[i].c;
		
		for(int j=b+1; j<=c; ++j)
			dwn[a][j] = 1;
	}
	
	printf("%lld",bfs(sx,sy));
	return 0;
}

Measured memory_bytes: 79196
import sys
N = int(input().strip())
grid = []
ref = 0
for i in range(N):
    array = list(map(int, input().strip().split(' ')))
    grid.append(array)
    if array[2]>0:
      ref = i
x = 0
y = 0
while y <= 100:
  x = 0
  while x <= 100:
    flag = 0
    h0 = grid[ref][2]+abs(x-grid[ref][0])+abs(y-grid[ref][1])
    for arrays in grid:
      h = max(0,h0-abs(x-arrays[0])-abs(y-arrays[1]))
      if h != arrays[2]:
        flag = 1
    if flag == 0:
      print(x,y,h0)
      sys.exit()
    x += 1
  y += 1

Measured memory_bytes: 3064
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> Pii;
typedef pair<Pii, int> Ppi;
int N, M; vector<Ppi> v;
int main() {
  scanf("%d %d", &N, &M);
  v.push_back({{0, 0}, 0});
  for(int i = 0, p, y; i < M; ++i) {
    scanf("%d %d", &p, &y);
    v.push_back({{p, y}, i});
  }
  sort(v.begin(), v.end());
  int ans[M][2];
  for(int i = 1, x; i < v.size(); ++i) {
    if(v[i].first.first != v[i-1].first.first) x = 1;
    ans[v[i].second][0] = v[i].first.first;
    ans[v[i].second][1] = x++;
  }
  for(int i = 0; i < M; ++i) {
    printf("%06d%06d\n", ans[i][0], ans[i][1]);
  }
}

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

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
ld EPS = 1e-12;
int INF = numeric_limits<int>::max() / 2;
int MOD = 1e9 + 7;
#define rep(i,n) for(int i = 0; i < n; i++)
#define all(obj) (obj).begin(), (obj).end()
#define debug(x) cerr << #x << ": " << x << '\n'
 
int main(){
    int n, m;
    cin >> n >> m;
    int a[1000], b[1000], c[1000], dist[100][100];
    for(int i = 0; i < m; ++i){
        cin >> a[i] >> b[i] >> c[i];
        a[i]--,b[i]--;
    }

    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            if(i == j) dist[i][j] = 0;
            else dist[i][j] = INF;
        }
    }
    
    for(int i = 0; i < m; ++i){
        dist[a[i]][b[i]] = min(dist[a[i]][b[i]], c[i]);
        dist[b[i]][a[i]] = min(dist[b[i]][a[i]], c[i]);
    }
    
    for(int k = 0; k < n; ++k){
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    
    int ans = m;
    
    for(int i = 0; i < m; ++i){
        bool shortest = false;
        for(int j = 0; j < n; ++j) if(dist[j][a[i]] + c[i] == dist[j][b[i]]) shortest = true;
        if(shortest) ans--;
    }
    
    cout << ans << endl;
    return 0;
}

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

typedef long long ll;
#define rep(i,n) for(i=0;i<n;++i)
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define mp make_pair
#define pb push_back
#define fi first
#define sc second

bool inside(int x,int y)
{
	return(0<=x&&x<10 && 0<=y&&y<10);
}

int main()
{
	int i,j,k;
	int dx[5]={1,-1,0,0,0};
	int dy[5]={0,0,0,-1,1};

	int C;
	cin >>C;
	for(int cases=0;cases<C;++cases)
	{
		int f[10][10]={0};
		rep(i,10)rep(j,10) scanf(" %d",&f[i][j]);

		int ans[10][10]={0};

		//1???????????????????????????????±????
		int mask;
		for(mask=0; mask<(1<<10); ++mask)
		{
			//???????????§?°??????????????¨????
			int ta[10][10]={0};
			//?????£???????????¶???
			int t[10][10]={0};
			rep(i,10)rep(j,10) t[i][j]=f[i][j];
			//1??????????????¢
			rep(i,10)
			{
				if(mask>>i&1)
				{//?????¢?????????
					ta[0][i]=1;
					rep(j,5)
					{
						int nx=i+dx[j];
						int ny=0+dy[j];
						if(inside(nx,ny)) t[ny][nx]=!t[ny][nx];
					}
				}
			}

			for(i=0;i<10-1;++i)
			{//i???????????¨???
				rep(j,10)
				{
					if(t[i][j]==1)
					{
						ta[i+1][j]=1;
						rep(k,5)
						{
							int nx=j+dx[k];
							int ny=i+1+dy[k];
							if(inside(nx,ny)) t[ny][nx]=!t[ny][nx];
						}
					}
				}
			}

			bool valid=true;
			rep(i,10)rep(j,10) valid&=(t[i][j]==0);

			if(valid)
			{
				rep(i,10)rep(j,10) ans[i][j]=ta[i][j];
				break;
			}
		}

		//output
		rep(i,10)
		{
			rep(j,10)
			{
				if(j) printf(" ");
				printf("%d",ans[i][j]);
			}
			printf("\n");
		}
	}
}

Measured memory_bytes: 3228
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repp(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define repm(i,n) for(int (i)=(n);(i)>0;(i)--)
#define INF (1ll<<60)
typedef long long lint;
const lint MOD =1000000007;

int main(){
 lint N;
 string s;
 lint count=0,count2=0;
 lint ans=0;
 vector<lint> X;
 cin>>s;
    if(s[0]=='<')X.push_back(0);
    else count++;
    
 N=s.size();
 
    rep(i,N-1){
        if(s[i]=='<'){ 
           X.push_back(X[i]+1);
        }
        if(s[i]=='>'){
           int j=1;
           count++;
           while(s[i+j]=='>'){
               count++;
               j++;
           }
           if(i==0){
               repm(k,j+1){
               X.push_back(k-1);
           }}
           else if(j>X[i]){
               X.erase(X.begin()+i);
               repm(k,j+1){
               X.push_back(k-1);
               }
           }
          else {repm(k,j){
            
               X.push_back(k-1);
           }}
           i+=j-1;
        }
    }
    if(s[N-1]=='<')X.push_back(X[N-1]+1);
    if(N==1)ans=1;
    rep(i,X.size()){
        ans+=X[i];
    }
    cout<<ans;
}

Measured memory_bytes: 7160
N = int(input())
A = []
B = []
C = []
for i in range(N) :
    a,b,c = map(int,input().split())
    A.append(a)
    B.append(b)
    C.append(c)

NOW = [[-1,-1,-1] for i in range(N)]
NOW[0] = [A[0],B[0],C[0]]

for i in range(1,N) :
    NOW[i][0] = max(NOW[i-1][1], NOW[i-1][2]) + A[i]
    NOW[i][1] = max(NOW[i-1][2], NOW[i-1][0]) + B[i]
    NOW[i][2] = max(NOW[i-1][0], NOW[i-1][1]) + C[i]

ans = max(NOW[-1])
print(ans)


Measured memory_bytes: 34660
// Written By NewbieChd
#include <cstdio>
#include <cctype>
using namespace std;

const int BUF = 1000000;
char buf[BUF], *p1, *p2;
inline char getChar() { return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, BUF, stdin), p1 == p2) ? EOF : *p1++; }
inline int read() {
    register int f = 0;
    char c;
    while (!isdigit(c = getChar())) {}
    do
        f = f * 10 + (c ^ 48);
    while (isdigit(c = getChar()));
    return f;
}

const int maxN = 100003;

int main() {
    int n = read(), k = read(), lim = (n - 1) * (n - 2) >> 1, i, j;
    if (k > lim) {
        printf("-1\n");
        return 0;
    }
    printf("%d\n", n - 1 + lim - k);
    for (i = 2; i <= n; ++i)
        printf("1 %d\n", i);
    lim -= k;
    for (i = 2; i < n && lim; ++i)
        for (j = i + 1; j <= n && lim; ++j)
            printf("%d %d\n", i, j), --lim;
    return 0;
}


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

using namespace std;

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

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e5 + 9;
int a[N];
int b[N];
bool chan[N];

int main(){
  fastIO;
  int n;
  cin >> n;
  for(int i = 1; i <= n; i ++ )
    cin >> a[i];
  for(int i = 1; i <= n; i ++ )
    cin >> b[i];
  vector<int> shit;
  ll sum = 0;
  for(int i = 1; i <= n; i ++ ){
    shit.push_back(a[i] - b[i]);
    sum += a[i] - b[i];
  }
  if(sum < 0){
    cout << -1;
    return 0;
  }
  sort(shit.begin(), shit.end());
  int p = n-1;
  ll ad;
  for(int i = 0 ; i < n; i ++ ){
    if(shit[i] >= 0) break;
    while(shit[i] < 0){
      chan[i]=true;
      chan[p]=true;
      ad = min(shit[p],-shit[i]);
      shit[i] += ad;
      shit[p] -= ad;
      if(shit[p]==0)p--;
    }
  }
  int ans = 0;
  for(int i = 0 ; i < n ; i ++ )
    ans += chan[i];
  cout << ans;
  return 0;
}


Measured memory_bytes: 1788
#include <stdio.h>

int main(void){
 int n=0;

  scanf("%d",&n);
 
  int d[n];
  
  for(int i=0;i<n;i++){
 	scanf("%d",&d[i]);
 }

  int sum=0;
  
  
  //1番目と2番目-n番目のせき
  //2番目と3番目-n番目のせき
  //3番目と4番目以降
  //m番目とm+1番目以降の積
  //...
  //n-1番目とn番目の積
  //nになったらおわり
  for(int i=0;i<n;i++){
  	for(int j=i+1;j<n;j++){
     sum = sum + d[i]*d[j];
    }
  }
  printf("%d",sum);

}


Measured memory_bytes: 128
N = int(input())
SS = input()

S = [0] * (2 * N + 1)
for i in range(N):
    if SS[i] == "R":
        S[i] = 1

    if SS[i] == "G":
        S[i] = 2

    if SS[i] == "B":
        S[i] = 4

cnt = [[0] * 3 for i in range(N)]
if S[0] == 1:
    cnt[0][0] = 1
elif S[0] == 2:
    cnt[0][1] = 1
else:
    cnt[0][2] = 1


for i in range(1, N):
    cnt[i][0] = cnt[i - 1][0]
    cnt[i][1] = cnt[i - 1][1]
    cnt[i][2] = cnt[i - 1][2]
    if S[i] == 1:
        cnt[i][0] += 1

    if S[i] == 2:
        cnt[i][1] += 1

    if S[i] == 4:
        cnt[i][2] += 1


ans = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        if S[i] != S[j]:
            to = S[i] + S[j]

            if to == 3:
                ans += cnt[N - 1][2] - cnt[j][2]
                if S[j + j - i] == 4:
                    ans -= 1

            if to == 5:
                ans += cnt[N - 1][1] - cnt[j][1]
                if S[j + j - i] == 2:
                    ans -= 1

            if to == 6:
                ans += cnt[N - 1][0] - cnt[j][0]
                if S[j + j - i] == 1:
                    ans -= 1


print(ans)


Measured memory_bytes: 68984
import java.util.*;

class Main {
	public static void main (String[] args) {
    	Scanner sc = new Scanner(System.in);
      	int n = sc.nextInt();
      	int pay;//支払額、おつり
      
      	if (n % 1000 == 0) {
          System.out.println(0);
        } else {
        	pay = (n / 1000 + 1) * 1000;
          	System.out.println(pay - n);
        }
    }
}

Measured memory_bytes: 35956
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <numeric>
#include <string>
#include <cstring>
#include <list>
#include <unordered_set>
#include <tuple>
#include <cmath>
#include <limits>
#include <type_traits>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <set>
#include <bitset>
#include <regex>
#include <random>
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define rep(i,n)for(ll i=0;i<n;++i)
#define exout(x) printf("%.10f\n", x)
const double pi = acos(-1.0);
const ll MOD = 1000000007;
const ll INF = 1e18;
const ll MAX_N = 201010;

//組み合わせの余りを求める
ll fac[MAX_N], finv[MAX_N], inv[MAX_N];

void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX_N; i++) {
		fac[i] = fac[i - 1] * i;
	}
}

// 二項係数計算
long long COM(ll n, ll k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] / (fac[k] * fac[n - k]);
}


//最大公約数
ll gcd(ll x, ll y) {
	return y ? gcd(y, x % y) : x;
}

ll lcm(ll x, ll y) {
	if (x == 0 || y == 0)return 0;
	return (x / gcd(x, y) * y);
}

ll dx[4] = { 0,0,-1,1 };
ll dy[4] = { -1,1,0,0 };
ll dp[10101][110];

//long longしか使わない
//素数は1より大きい
//lower_boundは指定したkey以上の要素の一番左のイテレータをかえす
//upper_boundは指定したkeyより大きい要素の一番左のイテレータをかえす
int main() {
	ll n;
	cin >> n;
	vector<ll>a(n), sum(n);
	rep(i, n) {
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	rep(i, n) {
		sum[i] = a[i];
	}
	rep(i, n - 1) {
		sum[i + 1] += sum[i];
	}
	ll ans = n;
	for (ll i = n - 2;i >= 0;--i) {
		if (sum[i] * 2 < a[i + 1]) {
			ans -= i;
			ans--;
			break;
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 4832
package main
import (
  "bufio"
  "os"
  "strconv"
  "strings"
  "fmt"
)

func Solve() {
  var N int
  NextInt(&N)
  Q := make([]int, N)
  S := make([]string, N)
  A := make([]string, 2 * N + 1)
  for i := range A[1:] { A[i + 1] = "R" }
  Query := func() string {
    for i, q := range Q { S[i] = strconv.Itoa(q) }
    Write("? " + strings.Join(S, " "))
    Output()
    return NextLine()
  }
  for i := range Q { Q[i] = i + 1 }
  QA := make([]string, 2 * N + 1)
  QA[1] = Query()
  QA[N + 1] = "Red"
  if QA[1] == QA[N + 1] { QA[N + 1] = "Blue" }
  low, high := 1, N + 1
  for 1 < high - low {
    med := (high + low) / 2
    for i := range Q { Q[i] = i + med }
    QA[med] = Query()
    if QA[med] == QA[low] {
      low = med
    } else {
      high = med
    }
  }
  n := low + N
  if QA[high] == "Blue" {
    A[n] = "B"
  } else {
    A[n - N] = "B"
  }
  for i := range Q { Q[i] = i + high }
  for i := n % (2 * N); i != n - N - 1; i = (i + 1) % (2 * N) {
    Q[N - 1] = i + 1
    if Query() == "Blue" { A[i + 1] = "B" }
  }
  for i := n - N + 1; i < n; i++ { A[i] = "?" }
  r, b := 0, 0
  for i, a := range A {
    if a == "R" && r < N / 2 { Q[r] = i; r++ }
    if a == "B" && b < N / 2 { Q[N / 2 + b] = i; b++ }
  }
  for i := n - N + 1; i < n; i++ {
    Q[N - 1] = i
    A[i] = "R"
    if Query() == "Blue" { A[i] = "B" }
  }
  Write("! " + strings.Join(A, ""))
}

func main() {
  Solve()
  Output()
}

var reader = bufio.NewReaderSize(os.Stdin, 1000000)
var writer = bufio.NewWriter(os.Stdout)
func NextLine() string {
  buffer := make([]byte, 0)
  for true {
    line, isPrefix, err := reader.ReadLine()
    if err != nil { panic(err) }
    buffer = append(buffer, line...)
    if !isPrefix { break }
  }
  return string(buffer)
}
func NextInt(A ...*int) {
  L := strings.Split(NextLine(), " ")
  for i, a := range A {
    *a, _ = strconv.Atoi(L[i])
  }
}
func NextIntVec(A *[]int) {
  L := strings.Split(NextLine(), " ")
  (*A) = make([]int, len(L))
  for i, l := range L {
    (*A)[i], _ = strconv.Atoi(l)
  }
}
func NextFloat(A ...*float64) {
  L := strings.Split(NextLine(), " ")
  for i, a := range A {
    *a, _ = strconv.ParseFloat(L[i], 64)
  }
}
func NextFloatVec(A *[]float64) {
  L := strings.Split(NextLine(), " ")
  (*A) = make([]float64, len(L))
  for i, l := range L {
    (*A)[i], _ = strconv.ParseFloat(l, 64)
  }
}
func Write(s interface{}) {
  fmt.Fprintln(writer, s)
}
func WriteIntVec(A []int) {
  S := make([]string, len(A))
  for i, a := range A {
    S[i] = strconv.Itoa(a)
  }
  Write(strings.Join(S, " "))
}
func Output() {
  _ = writer.Flush()
}
func MaxInt(A ...int) int {
  max := A[0]
  for _, a := range A {
    if max < a { max = a }
  }
  return max
}
func MinInt(A ...int) int {
  min := A[0]
  for _, a := range A {
    if a < min { min = a }
  }
  return min
}
func SumInt(A ...int) int {
  sum := 0
  for _, a := range A {
    sum += a
  }
  return sum
}
func AbsInt(x int) int {
  if x < 0 { x = -x }
  return x
}

Measured memory_bytes: 1364