akhauriyash/Code-Regression huggingface dataset:
/* BISMILLAHIR RAHMANIR RAHIM */
#include<bits/stdc++.h>
#define INF 9999999
#define ll long long
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin>>n;
    int dp[n][3];
    vector<int>a(n),b(n),c(n);
    for(int i=0; i<n; i++)
        cin>>a[i]>>b[i]>>c[i];
     dp[0][0]=a[0];
     dp[0][1]=b[0];
     dp[0][2]=c[0];
     for(int i=1;i<n;i++){
       dp[i][0]=a[i]+max(dp[i-1][1],dp[i-1][2]);
         dp[i][1]=b[i]+max(dp[i-1][0],dp[i-1][2]);
         dp[i][2]=c[i]+max(dp[i-1][0],dp[i-1][1]);
      }
     cout<<max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]))<<endl;
    return 0;
}


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

int check[101];
struct node{
    int x,y;
};

bool comp(struct node &A,struct node B){
    if(A.x < B.x) return 1;
    return 0;
}

int main(int argc, const char * argv[]) {
 
    int n;
    struct node red[101];
    struct node blue[101];
    
    scanf("%d",&n);
    
    for(int i=0,a,b;i<n;i++){
        scanf("%d %d",&a,&b);
        red[i].x = a;
        red[i].y = b;
    }
    
    for(int i=0,c,d;i<n;i++){
        scanf("%d %d",&c,&d);
        blue[i].x = c;
        blue[i].y = d;
    }
    sort(blue,blue+n,comp);
    
//    for(int i=0;i<n;i++){
//        printf("%d \n",blue[i].x);
//    }
    int ans = 0;
    for(int i=0;i<n;i++){ //blue
        int mm = -1;
        int num = -1;
        for(int j=0;j<n;j++){ //red //가장 가까운것
            
            if(!check[j] && blue[i].x > red[j].x && blue[i].y > red[j].y){
                
                if(mm < red[j].y){
                    mm = red[j].y;
                    num = j;
                }
                
            }
        }
        
        if(num!=-1){
            check[num]=true;
            ans++;
        }
    }
    
    printf("%d\n",ans);
    
    return 0;
}


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

using namespace std;
struct A
{
    int con=0;
    int how;

}a[100005],b[100005];
bool F(A a,A b)
{
    return a.con>b.con;
}
int main()
{
    int N,M,i,j,k,t;
    scanf("%d",&N);
    for(i=0;i<N;i++)
    {
        scanf("%d",&t);
        if(i%2==0)
        {
            a[t].how=t;
            a[t].con++;
        }
        else
        {
            b[t].how=t;
            b[t].con++;
        }
    }
    sort(a,a+100001,F);
    sort(b,b+100001,F);

    if(a[0].how==b[0].how)
    {
        printf("%d\n",min(N-a[0].con-b[1].con,N-a[1].con-b[0].con));
    }
    else printf("%d\n",N-a[0].con-b[0].con);


    return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <climits>

using namespace std;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)

typedef long long LL;
typedef vector<int> VI;

const static int MAX_NUM_DIGITS = 60;

const static uint64_t MOD = 1000000007LL;

int main() {
  int N;
  cin >> N;
  vector<uint64_t> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  vector<vector<int>> num_ones_vec(MAX_NUM_DIGITS, std::vector<int>(N, 0));
  for (int digit = 0; digit < MAX_NUM_DIGITS; digit++) {
    int one_count = 0;
    for (int i = 0; i < N; i++) {
      if (((A[i] >> digit) & 1) == 1) {
        one_count++;
      }
      num_ones_vec[digit][i] = one_count;
    }
  }
  uint64_t ans = 0;
  uint64_t base = 1;
  for (int digit = 0; digit < MAX_NUM_DIGITS; digit++) {
    for (int i = 0; i < N-1; i++) {
      int rest_num_ones = num_ones_vec[digit][N-1] - num_ones_vec[digit][i];
      int rest_num_zeros = N-1-i-rest_num_ones;
      if (((A[i] >> digit) & 1) == 1) {
        ans += (base % MOD) * (rest_num_zeros % MOD);
      } else {
        ans += (base % MOD) * (rest_num_ones % MOD);
      }
      ans %= MOD;
    }
    base *= 2;
  }
  cout << ans << endl;
  return 0;
}


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

class _C
{
	void _()
	{
		var _n = _Ns();
		var N = _n[0];

		//
		var l = new string[N];
		for (int i=0;i<N;i++) {
			l[i] = _S();
		}

		//
		Array.Sort(l);

		for (int i=0;i<N ;i++)
			Console.Write(l[i]);

		Console.WriteLine();			

	}

	static void Main(string[] args)
  {
    new _C()._();
  }

  #region

  string _S()
  {
    return Console.ReadLine();
  }

  string[] _Ss()
  {
    return Console.ReadLine().Split();
  }

  int[] _N(int n)
  {
    var x = new int[n];
    for (var i = 0; i < n; i++)
    {
      x[i] = int.Parse(Console.ReadLine());
    }
    return x;
  }

  int[] _Ns()
  {
    var ss = Console.ReadLine().Split();

    var x = new int[ss.Length];
    for (var i = 0; i < ss.Length; i++)
      x[i] = int.Parse(ss[i]);

    return x;
  }
  #endregion
}

Measured memory_bytes: 3160
#include <stdio.h>

#define N 20

int main() {
	static int pp[N];
	int n, i, cnt;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d", &pp[i]);
	cnt = 0;
	for (i = 1; i < n - 1; i++) {
		int a, b, c;

		a = pp[i - 1], b = pp[i], c = pp[i + 1];
		if ((b > a && b < c) || (b < a && b > c))
			cnt++;
	}
	printf("%d\n", cnt);
	return 0;
}


Measured memory_bytes: 128
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>

using namespace std;

#define mod 1000000007

int main()
{
	int n;
	cin >> n;
	vector<pair<int, int> > v;
	for(int i = 1; i <= n; i++){
		int x;
		cin >> x;
		v.push_back(make_pair(x, i));
	}
	sort(v.begin(), v.end());
	map<int, int> canputnum;
	for(int i = 1; i <= n; i++){
		canputnum[i] = i - 1;
	}
	vector<int> ans;
	for(int i = 0; i < v.size(); i++){
		int x = v[i].first;
		int num = v[i].second;
		for(int j = 0; j < canputnum[num]; j++){
			ans.push_back(num);
		}
		canputnum[num] = 0;
		if(ans.size() < x - 1){
			for(int j = 0; j < v.size(); j++){
				int num = v[(i + j) % n].second;
				while(ans.size() < x - 1 && canputnum[num] > 0){
					ans.push_back(num);
					canputnum[num]--;
				}
			}
		}
		// cout << ans.size() << endl;
		if(ans.size() == x - 1){
			ans.push_back(num);
			canputnum[num] = n - num;
		} else {
			cout << "No" << endl;
			return 0;
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < canputnum[i]; j++){
			ans.push_back(i);
		}
	}
	cout << "Yes" << endl;
	for(int i = 0; i < n * n; i++){
		cout << ans[i];
		if(i == n * n - 1) cout << endl;
		else cout << " ";
	}
}

Measured memory_bytes: 2296
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String str;

		while(true){
			str = sc.nextLine();
			if(str.equals("END OF INPUT")){
				break;
			}

			int count = 0;
			int len = str.length();
			String ans = "";
			for(int i=0;i<len;i++){
				if(str.charAt(i) == ' '){
					ans += count+"";
					count = 0;
				}else{
					count++;
				}
			}
			ans += count+"";
			System.out.println(ans);
		}
	}

}

Measured memory_bytes: 0
#include <iostream>

static const int MaxNum = 9;
static void print_qq()
{
    for (int i = 1; i <= MaxNum; ++i) {
        for (int j = 1; j <= MaxNum; ++j) {
            std::cout << i << "x" << j << "=" << i * j << std::endl;
        }
    }
}

int main()
{
    print_qq();
}

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

using namespace std;

int main() {

	int n, max=0, s[100];

	for(int i=0; i<100; i++) {
		s[i]=0;
	}

	while(cin >> n) {
		s[n-1]++;
	}

	for(int i=0; i<100; i++) {
		if(s[i]>max)
			max=s[i];
	}

	for(int i=0; i<100; i++) {
		if(s[i]==max)
			cout << i+1 << endl;
	}

	return 0;

}

Measured memory_bytes: 0
import java.util.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main {

	int INF = 1 << 28;

	void run() {
		Scanner sc = new Scanner(System.in);
		for(;;) {
			int n = sc.nextInt();
			int k = sc.nextInt();
			if( (n|k) == 0 ) break;
			
			int[] br = new int[k];
			boolean flg = true;
			for(int i=0;i<k;i++) br[i] = sc.nextInt();
			for(int i=0;i<n;i++) for(int j=0;j<k;j++) {
				br[j] -= sc.nextInt();
				if( br[j] < 0 ) flg = false;
			}
			
			System.out.println((flg? "Yes": "No"));
		}
	}

	public static void main(String[] args) {
		new Main().run();
	}

	void debug(Object... os) {
		System.err.println(Arrays.deepToString(os));
	}
}

Measured memory_bytes: 12000
#include "bits/stdc++.h"
using namespace std;
#define REP(i, n) for(ll i = 0;i < n;i++)
#define ll long long
#define MOD 1000000007
#define llMAX 9223372036854775807
#define llMIN -9223372036854775808
using vi = vector<ll>; // intの1次元の型に vi という別名をつける
using vvi = vector<vi>; // intの2次元の型に vvi という別名をつける

ll k,q;

int main(){
  ll ans=0;
  cin >> k>>q;
  vi d(k),dm(k),n(q),x(q),m(q);
  REP(i,k) cin>>d[i];

  REP(i,q){
    cin>>n[i]>>x[i]>>m[i];
  }


  REP(i,q){

    ll zc=0;
    ll zc2=0;
    ll smal=0;
    ll sm=0;
    ll nm=(n[i]-1)%k;
    REP(j,k){
      dm[j]=d[j]%m[i];
      if (dm[j]==0){
        zc++;
        if (j<nm)zc2++;
      }
      smal+=dm[j];
    }
    x[i]%=m[i];
    ll maxnum=x[i]+((n[i]-1)/k)*smal;
    
    REP(j,nm){
      sm+=dm[j];
    }
    maxnum+=sm;
    ans=n[i]-1;
    ll koe=maxnum/m[i];
    ans-=koe;
    ans-=zc*((n[i]-1)/k);
    ans-=zc2;
    cout<<ans<<endl;

    
  }


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

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

using namespace std;

int main() {
    int n;
    cin >>n;
    int value[n];
    int cost[n];
    int diff[n];

    for (int i =0; i<n; i++) cin >> value[i];
    for (int i =0; i<n; i++) cin >> cost[i];
    for (int i =0; i<n; i++) diff[i] = value[i] - cost[i];
    int max = 0;
    for (int i =0; i<n; i++){
        if (diff[i] > 0) max += diff[i];
    }
    cout << max <<endl;

    return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<complex>
#include<set>
#include<utility>

using namespace std;

typedef complex<double> P;

int x[1234],y[1234];
P p[1234];
set<pair<int,int> > ps;
int N;
double eps=1e-9;

double cross(P a,P b){
  return a.real()*b.imag()-a.imag()*b.real();
}

int nol(P a,P b){
  int n=0;
  for(int i=0;i<N;i++){
    n+=fabs(cross(p[i]-a,b-a))<eps;
  }
  return n;
}

bool check(P a,P b){
  if(nol(a,b)>2)return false;
  for(int i=0;i<N;i++){
    P vp=p[i]-a;
    P r=vp*polar(1.,(arg(b-a)-arg(vp))*2)+a;
    int y=r.imag()+.5-(r.imag()<0);
    int x=r.real()+.5-(r.real()<0);
    if(abs(r-P(x,y))>eps||!ps.count(make_pair(y,x)))return false;
  }
  return true;
}

int main(){
  cin>>N;
  for(int i=0;i<N;i++){
    cin>>x[i]>>y[i];
    ps.insert(make_pair(y[i],x[i]));
    p[i]=P(x[i],y[i]);
  }
  bool sym=false;
  if(nol(p[0],p[1])!=N){
    for(int i=0;i<2;i++){
      for(int j=i+1;j<N;j++){
	auto m=(p[i]+p[j])/2.;
	sym|=check(m,(p[i]-m)*P(0,-1)+m);
      }
    }
    sym|=check(p[0],p[1]);
  }
  cout<<(sym?"Yes":"No")<<endl;
}

    

Measured memory_bytes: 1360
#include<bits/stdc++.h>
 
using namespace std;
 
int main()
{
    long long a,b,n;
    cin>>n>>a>>b;
    if(n==1)
    {
        if(a==b)
        cout<<1;
        else
        cout<<0;
    }
    else 
    {
    if(a==b)
    cout<<1;
    else if(a>b)
    cout<<0;
    else
    cout<<((b-a)*(n-1))-(b-a-1);
    }
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        int i,j;
        for (i=1;i<10;i++){
            for(j=1;j<10;j++){
                System.out.println(String.format("%dx%d=%d",i,j,i*j));
            }
        }
}
}


Measured memory_bytes: 24908
n=int(input())
s=input()
rgb=[(0,0,0)]
for i in range(n):
	a=rgb[-1][0]
	b=rgb[-1][1]
	c=rgb[-1][2]
	if s[i]=="R":
		a+=1
	elif s[i]=="G":
		b+=1
	else:
		c+=1
	rgb.append((a,b,c))
ans=0
for i in range(n-2):
	for j in range(i+1,n-1):
		if s[i]!=s[j]:
			if "B" not in (s[i],s[j]):
				ans+=rgb[-1][2]-rgb[j+1][2]
				if 2*j-i<n:
					if s[2*j-i]=="B":
						ans-=1
			elif "G" not in (s[i],s[j]):
				ans+=rgb[-1][1]-rgb[j+1][1]
				if 2*j-i<n:
					if s[2*j-i]=="G":
						ans-=1
			else:
				ans+=rgb[-1][0]-rgb[j+1][0]
				if 2*j-i<n:
					if s[2*j-i]=="R":
						ans-=1
print(ans)

Measured memory_bytes: 68920
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cassert>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;


typedef long long i64;
const int inf = (int)1.05e9;

const i64 mod = 998244353;

int main()
{
	int n;
	vector<int> ds;

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

	if(ds[0] != 0) {
		printf("%d\n", 0);
		return 0;
	}

	vector<pair<int,int>> idxs;

	for(int i = 1; i < n; i++) {
		idxs.push_back({ds[i], i});
	}
	sort(idxs.begin(), idxs.end());

	vector<int> count(n, 0);
	count[0] = 1;
	i64 ans = 1;

	for(int i = 0; i < n - 1; i++) {

		int v = idxs[i].second;
		int d = idxs[i].first;

		if(d == 0) {
			ans = 0;
			break;
		}

		ans = ans * count[d - 1] % mod;
		count[d] += 1;
	}

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

	return 0;
}

/* waffle */


Measured memory_bytes: 1784
N = int(input())
H = list(map(int, input().split()))
ans = 0
temp = 0

for i in range(N-1):
    if H[i] >= H[i+1]:
        temp += 1
    else:
        if temp > ans:
            ans = temp
            temp = 0
        else:
            temp = 0

print(max(temp,ans))

Measured memory_bytes: 14224
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#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()
{
    ll n, p, tmp = 0, base = 1;

    cin >> n >> p;
    vector<char> s(n);
    ll ans = 0;

    rep(i, n)
    {
        cin >> s[i];
    }

    if (10 % p == 0)
    {
        rep(i, n)
        {
            if ((s[i] - '0') % p == 0)
            {
                ans += i + 1;
            }
        }
    }
    else
    {
        vector<int> mod(p, 0);
        mod[0]++;
        rep(i, n)
        {
            tmp = (tmp + base * (s[n - 1 - i] - '0')) % p;
            ans += mod[tmp];
            mod[tmp]++;

            base = (base * 10) % p;
        }

        // rep(i, p)
        // {
        //     ans += mod[i] * (mod[i] - 1) / 2;
        // }
        // ans += mod[0];
    }
    cout << ans << endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define pi 3.14159
using namespace std;

int main()
 {
 	 long long int x,r,p,m,s;
 	 cin>>x;
 	 p=x/500;
 	 r=x%500;
 	 m=r/5;
 	 s=p*1000+m*5;
 	 cout<<s<<endl;
 	return 0;
 }

Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define all(v) v.begin(),v.end()
#define P pair<int,int>
#define len(s) (int)s.size()
#define pb push_back

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;
}
constexpr int mod = 1e9+7;
//constexpr int inf = 3e18;

int D;
int C[26];
int A[365][26];
int con[365];
set<int>st[26];
int score(){
	vector<int>last(26,-1);
	int res=0;
	rep(i,D){
		last[con[i]]=i;
		res+=A[i][con[i]];
		rep(j,26){
			res-=C[j]*(i-last[j]);
		}
	}
	return res;
}
int change(int x,int y){
	int res=A[x][y]-A[x][con[x]];
	auto pre_old=--st[con[x]].lower_bound(x);
	auto next_old=st[con[x]].upper_bound(x);
	res+=(*next_old-x-1)*(*next_old-x)/2*C[con[x]];
	res-=(x-*pre_old+*next_old-*pre_old-1)*(*next_old-x)/2*C[con[x]];
	auto pre_new=--st[y].lower_bound(x);
	auto next_new=st[y].lower_bound(x);
	res+=(x-*pre_new+*next_new-*pre_new-1)*(*next_new-x)/2*C[y];
	res-=(*next_new-x-1)*(*next_new-x)/2*C[y];
	return res;
}
double rand_double(){
	return (double)rand()/RAND_MAX;
}
signed main(){
	cin>>D;
	rep(i,26){
		cin>>C[i];
		st[i].insert(-1);st[i].insert(D);
	}
	rep(i,D){
		int mx=0,idx;
		rep(j,26){
			cin>>A[i][j];
			if(chmax(mx,A[i][j]))idx=j;
		}
		con[i]=idx;
		st[idx].insert(i);
	}
	int score_=score();
	cerr<<score_<<endl;
	double C=1970*10000;
	while(1000.*clock()/CLOCKS_PER_SEC<=1970){
		int x=rand()%D,y;
		do{
			y=rand()%26;
		}while(con[x]==y);
		int diff=change(x,y);
		double ti=1970-1000.*clock()/CLOCKS_PER_SEC;

		if(diff>=0||ti/C>rand_double()){
			score_+=diff;
			st[con[x]].erase(x);
			con[x]=y;
			st[y].insert(x);
		}
	}
	rep(i,D)cout<<con[i]+1<<"\n";
	cerr<<score_<<endl;
}


Measured memory_bytes: 3728
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int n, k, a[107], dp[107][200007];
const int mod = 1e9 + 7;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> k;
	dp[0][k] = 1;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		int r = k, sum = 0;
		for(int j = k; j >= 0; j--){
			sum += dp[i - 1][j];
			if(sum >= mod) sum -= mod;
			sum = sum - dp[i - 1][j + a[i] + 1] + mod;
			sum %= mod;
			dp[i][j] = sum;
		}
	}
	cout << dp[n][0];
}


Measured memory_bytes: 78848
#include <iostream>
#include <string>
#include <set>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <unordered_map>
#include <vector>
#define task ""
using namespace std;
using ll = long long;
using ld = long double;

const int N = 2e5 + 2;
int n;
ll ans;

void Read(){
	cin >> n;
	for(int i = 1; i < n; ++i){
		int u, v;
		cin >> u >> v;
		if(u > v)
			swap(u, v);
		ans -= 1ll * u * (n - v + 1);
	}
}

void Solve(){
	cout << ans + 1ll * (n + 1) * (n + 2) * n / 6ll;
}

main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	Read();
	Solve();
}


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

int kadaneAlg(int arr[], const int &len) {
    int max_global;
    int max_current = max_global = arr[0];

    for (int i = 1; i < len; i++) {
        max_current = std::max(arr[i], arr[i] + max_current);
        if (max_current > max_global) max_global = max_current;
    }
    return max_global;
}

int main()
{
    int N;
    while(1) {
        std::scanf("%d", &N);
        if (N == 0) break;
        int arr[N];
        for (int i = 0; i < N; i++) scanf("%d", &arr[i]);
        std::printf("%d\n", kadaneAlg(arr, N));
    }
    return 0;
}



Measured memory_bytes: 3168
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define var auto
using namespace std;
using ll = long long;
using P = pair<int, int>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const ll INF = 1LL << 60;
ll dp[100010];
// 最小化問題なので INF で埋める

ll h[100010];

// dp[i] の最小コストを求める
ll rec(int i) {
  if (dp[i] < INF) return dp[i];

  if (i == 0) return 0;

  // dp[i] の最小コストは。dp[i-1] or dp[i-2] から計算できる
  ll res = INF;
  chmin(res, rec(i-1) + abs(h[i] - h[i-1]));
  if (i > 1) {
    chmin(res, rec(i-2) + abs(h[i] - h[i-2]));
  }

  dp[i] = res;
  return dp[i];
}

int main() {
  int n;
  cin >> n;
  rep(i,n) cin >> h[i];
  rep(i,100010) dp[i] = INF;

  cout << rec(n-1) << endl;
}


Measured memory_bytes: 6528
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<map>
#include<set>
#include<bitset>
using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1<<30;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;
int dx[8]={1,0,-1,0,1,1,-1,-1} , dy[8]={0,1,0,-1,1,-1,1,-1} ;

int main(){
    int a[3];
    rep(i,3)cin>>a[i];
    sort(a,a+3);
    cout<<a[2]-a[0]<<endl;
    return 0;
}


Measured memory_bytes: 256
n,m = input().split()
m = int(m)
s =  [list(map(int,input().split())) for i in range(m)]
brk =0
n = int(n)
nl = [0]*n
chk = [0]*n
for i in s:
    if chk[i[0]-1] >0 and nl[i[0]-1] != i[1]:
        brk = 1
        break
    elif i[0] == 1 and i[1] ==0 and n>1:
        brk = 1
        break
    else:
        nl[i[0]-1] = i[1]
        chk[i[0]-1] += 1

if brk == 1: print("-1")
elif nl[0] == 0 and n>1:
  nl[0] =1
  L=[str(a) for a in nl]
  #print(L)
  fn = int("".join(L))
  print(fn)

else:
  L=[str(a) for a in nl]
  #print(L)
  fn = int("".join(L))
  print(fn)

Measured memory_bytes: 3064
using System;
using System.Linq;//リストの使用
using System.Collections.Generic;
using System.Text;//テキストの高速出力に必要
class Program
{
	static void Main()
	{
		string[] input = Console.ReadLine().Split(' ');
		long n = long.Parse(input[0]);
		long w = long.Parse(input[1]);
    long[,] dp = new long[n+1,10001];//dp[見た個数,価値]=重さの最小値

    long[,] vertexes = new long[n,2];//ここに受け取る
    for(long i = 0; i < n; i++)
    {
      long[] nums = Array.ConvertAll(Console.ReadLine().Split(' '),long.Parse);//１行ごとに受け取る
      vertexes[i,0] = nums[0];
      vertexes[i,1] = nums[1];
    }

    for(int i = 0; i <= n; i++)//初期化
    {
      for(int j = 0; j <= 10000; j++)
      {
        dp[i,j] = long.MaxValue;
      }
    }
    for(int i = 0; i <= n; i++)
    {
      dp[i,0] = 0;
    }

    for(int i = 1; i <= n; i++)
    {
      for(int j = 0; j <= 10000; j++)
      {
        if(dp[i-1,j] != long.MaxValue)
        {
          dp[i,j] = Math.Min(dp[i,j], dp[i-1,j]);
        }
        
        if(j-vertexes[i-1,0] >= 0)//取るならば
        {
          if(dp[i-1,j-vertexes[i-1,0]] != long.MaxValue)
          {
            dp[i,j] = Math.Min(dp[i,j], dp[i-1,j-vertexes[i-1,0]] + vertexes[i-1,1]);
            //Console.WriteLine(dp[i,j]+" "+i+" "+j);
          }
        }
      }
    }

    for(int i = 10000; i >= 0; i--)
    {
      if(dp[n,i] <= w)//重さが制限を満たすならば
      {
        Console.WriteLine(i);
        break;
      }
    }
	}
}


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

ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

map<ll,int> prime_fac(ll n) {
  map<ll,int> res;
  for(ll i=2;i*i<=n;i++)
    while(n%i==0)
      res[i]++,n/=i;
  if(n>1) res[n]++;
  return res;
}

ll modpow(ll a, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res % mod;
}
int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

  ll n;cin>>n;
  vector<ll> a(n);
  ll mod = pow(10, 9) + 7;

  map<ll,int> M;

  for(int i=0;i<n;i++){
    cin>>a[i];
    auto p = prime_fac(a[i]);
    for(auto kv : p) {
      M[kv.first] = max(M[kv.first], kv.second);
    }
  }

  ll k = 1;
  // k = lcm(k,a[i]) % mod;
  for(auto kv : M) {
    k *= modpow(kv.first, kv.second, mod) % mod;
    k %= mod;
  }

  ll ans=0;
  for(int i=0;i<n;i++){
    ans += k * modinv(a[i], mod) % mod;
    ans %= mod;
  }
  cout<<ans<<endl;
  
  return 0;
}


Measured memory_bytes: 1024
#include "bits/stdc++.h"
using namespace std;
#define MODULO 1000000007
#define PI 3.14159265359
typedef long long int ll;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    long int n,d;
    cin>>n>>d;
    d=d*d;
    long int res=0;
    while(n>0)
    {
    	long int x,y;
    	cin>>x>>y;
        long int z=(x*x)+(y*y);
    	if(z<=d)
    	res++;
    	n--;
	}
	cout<<res<<endl;
    return 0;
}


Measured memory_bytes: 3640
N,x = map(int,input().split())
A = sorted(list(map(int,input().split())))
cnt = 0
tot = A[0]
while cnt<N and tot<=x:
    cnt += 1
    if cnt<N:
        tot += A[cnt]
if cnt==N and tot<x:
    cnt -= 1
print(cnt)

Measured memory_bytes: 38256
#include <algorithm>
#include <bits/stdc++.h>
#include <cstdint>
#include <iostream>
#include <iterator>
#include <vector>

// lib/util.hpp
#ifndef UTIL_HPP
#define UTIL_HPP


typedef ::std::int_fast64_t i64;
typedef ::std::uint_fast64_t u64;
typedef ::std::int_fast32_t i32;
typedef ::std::uint_fast32_t u32;

namespace tools {
  template <typename T>
  void read(::std::istream& is, ::std::vector<T>& vector, const typename ::std::vector<T>::size_type size) {
    vector.reserve(size);
    ::std::copy_n(::std::istream_iterator<T>(is), size, ::std::back_inserter(vector));
  }
  template <typename T>
  void read(::std::vector<T>& vector, const typename ::std::vector<T>::size_type size) {
    ::tools::read(::std::cin, vector, size);
  }

  template <typename T, ::std::size_t N>
  void read(::std::istream& is, ::std::array<T, N>& array) {
    ::std::copy_n(std::istream_iterator<T>(is), N, array.begin());
  }
  template <typename T, ::std::size_t N>
  void read(::std::array<T, N>& array) {
    ::tools::read(::std::cin, array);
  }
}

#endif

// main.cpp

int main() {
  i64 N;
  std::cin >> N;
  std::vector<i64> L;
  tools::read(L, N);

  std::sort(L.begin(), L.end());
  i64 answer = 0;
  for (i64 i = 0; i < N; ++i) {
    for (i64 j = i + 1; j < N; ++j) {
      answer += static_cast<i64>(std::distance(
        std::upper_bound(L.begin(), L.end(), L[j] - L[i]),
        --std::upper_bound(L.rbegin(), L.rend(), L[j] + L[i], std::greater<i64>()).base()
      )) + 1 - (L[j] < 2 * L[i] ? 2 : 1);
    }
  }

  std::cout << answer / 3 << std::endl;
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#define MIN(a,b) ((a)<(b))?(a):(b)

struct material{
	int a;
	int b;
	int c;
} d[40];
int n,ma,mb,am=0,bm=0,c=0,min=INT_MAX;

void solve(int q){
	int i;
	if(c>min) return;
	if(q==n){
		if(c!=0 && ma*bm==mb*am){
			min=MIN(min,c);
		}
		return;
	}
	for(i=0;i<2;i++){
		am+=i*d[q].a;
		bm+=i*d[q].b;
		c+=i*d[q].c;
		solve(q+1);
		am-=i*d[q].a;
		bm-=i*d[q].b;
		c-=i*d[q].c;
	}
}

int cmp(const void *a, const void *b){
	return ((struct material*)b)->c-((struct material*)a)->c;
}
int main(int argc, char const *argv[]) {
	int i;
	scanf("%d %d %d",&n,&ma,&mb);
	for(i=0;i<n;i++){
		scanf("%d %d %d",&d[i].a,&d[i].b,&d[i].c);
	}
	qsort(d,n,sizeof(struct material),cmp);
	solve(0);
	if(min==INT_MAX) printf("-1\n");
	else printf("%d\n",min);
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> P;
typedef vector<P> vpl;
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int inf = 1<<30;
const ll linf = 1LL<<62;
const int MAX = 510000;
ll dy[8] = {0,1,0,-1,1,-1,1,-1};
ll dx[8] = {1,0,-1,0,1,-1,-1,1};
const double pi = acos(-1);
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;}
template<typename T1,typename T2> inline void print2(T1 a, T2 b){cout << a << " " << b << endl;}
template<typename T1,typename T2,typename T3> inline void print3(T1 a, T2 b, T3 c){
	cout << a << " " << b << " " << c << endl;
}
#define INT_MAX 1<<30
const ll mod = 1e9+7;



int main(){
	ll n,a,b; cin >> n >> a >> b;
	if((b-a)%2==0) cout << (b-a)/2 << endl;
	else{
		cout << min(a+(b-a)/2, (n-b+1)+(b-a)/2) << endl;
	}
}


Measured memory_bytes: 256
import sys
input=lambda :sys.stdin.readline().rstrip()

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

k = 1+n%2
f_inf = float('inf')

dp = [[-f_inf for _ in range(4)] for _ in range(200005)]
dp[0][0] = 0
for i in range(n):
    for j in range(k+1):
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j])
        now = dp[i][j]
        if (i+j)%2 == 0: now += A[i]
        dp[i+1][j] = max(dp[i+1][j], now)

ans = dp[n][k]
print(ans)

Measured memory_bytes: 78624
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
vector<int> G[200010];
long long mod = 1000000007;
const int MX = 200010;
ll f[MX],inv[MX],fi[MX];
ll pw(ll a,ll x){
    ll ret = 1;
    while(x){
        if(x&1){
            (ret *= a) %= mod; x--;
        }
        (a *= a) %= mod; x /= 2;
    }
    return ret;
}
ll inverse(ll x){
    return pw(x,mod - 2);
}

void solve(){
    ll i;
    f[0] = 1; fi[0] = 1;
    for(i=1;i<MX;i++) f[i] = f[i - 1]*i%mod;
    fi[MX - 1] = inverse(f[MX - 1]);
    for(i=MX - 2;i>=1;i--) fi[i] = fi[i + 1]*(i + 1)%mod;
    for(i=1;i<MX;i++) inv[i] = f[i]*fi[i - 1]%mod;
}

ll ans[200010],dp[200010],sz[200010];
ll dfs(int s,int p){
    ll ret = 1,val = 1;
    for(int v:G[s]){
        if(v==p) continue;
        ll x = dfs(v,s);
        (val *= dp[v]) %= mod; (val *= fi[x]) %= mod;
        ret += x;
    }
    (val *= f[ret - 1]) %= mod;
    dp[s] = val; sz[s] = ret;
    return ret;
}

int n;
void dfs1(int s,int p){
    ans[s] = dp[s];
    for(int v:G[s]){
        if(v==p) continue;
        ll x = dp[v],y = dp[s],s1 = sz[v],s2 = sz[s];
        sz[v] = n; sz[s] = n - s1;
        (dp[s] *= fi[n - 1]%mod*f[s1]%mod*inverse(x)%mod*f[sz[s] - 1]%mod) %= mod;
        (dp[v] *= f[n - 1]%mod*dp[s]%mod*fi[sz[s]]%mod*fi[s1 - 1]%mod) %= mod;
        dfs1(v,s);
        dp[v] = x; dp[s] = y; sz[v] = s1; sz[s] = s2;
    }
}

int main(){
    int i;
    cin >> n;
    for(i=0;i<n - 1;i++){
        int a,b; cin >> a >> b; a--; b--;
        G[a].push_back(b); G[b].push_back(a);
    }
    solve();
    dfs(0,-1); dfs1(0,-1);
    for(i=0;i<n;i++){
        cout << ans[i] << endl;
    }
}

Measured memory_bytes: 23284
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}
ll tmp[200001];
void pakuri_sort(int N, ll A[]) {
	const int b = 8;
	rep(k, 4) {
		int kazu[1 << b] = {}, kazu2[1 << b] = {};
		rep(i, N) kazu[A[i] >> k * b & ((1 << b) - 1)]++;
		rep(i, (1 << b) - 1) kazu[i + 1] += kazu[i];
		for (int i = N - 1; i >= 0; i--) tmp[--kazu[A[i] >> k * b & ((1 << b) - 1)]] = A[i];
		k++;
		rep(i, N) kazu2[tmp[i] >> k * b & ((1 << b) - 1)]++;
		rep(i, (1 << b) - 1) kazu2[i + 1] += kazu2[i];
		for (int i = N - 1; i >= 0; i--) A[--kazu2[tmp[i] >> k * b & ((1 << b) - 1)]] = tmp[i];
	}
}

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


	int N = getint(), D = getint(), A = getint();
	ll XH[200001];
	rep(i, N) {
		int x = getint();
		XH[i] = (ll(getint()) << 32) + x;
	}
	pakuri_sort(N, XH);
	XH[N] = (1ll << 62) - 1;
	rep(i, N) tmp[i] = 0;

	int ima = 0;
	const ll m = (1ll << 32) - 1;
	ll kotae = 0;
	int k = 0;
	int d = min(1000000000, 2 * D);
	rep(i, N) {
		ima += tmp[i];
		int nokori = (XH[i] >> 32) - ima;
		if (nokori > 0) {
			int kaisuu = (nokori + A - 1) / A;
			while ((XH[i] & m) + d >= (XH[k] & m)) k++;
			ima += kaisuu * A;
			tmp[k] -= kaisuu * A;
			kotae += kaisuu;
		}
	}

	printf("%lld", kotae);

	Would you please return 0;
}

Measured memory_bytes: 3456
package main

import (
	"bufio"
	"fmt"
	"os"
)

var sc = bufio.NewScanner(os.Stdin)

type triple struct {
	x, y, h int
}

func ri() (n int) {
	sc.Scan()
	for _, v := range sc.Bytes() {
		n = n*10 + int(v-48)
	}
	return
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	sc.Split(bufio.ScanWords)
	n := ri()
	a := make([]triple, n)
	for i := 0; i < n; i++ {
		a[i] = triple{x: ri(), y: ri(), h: ri()}
	}
	for cx := 0; cx <= 100; cx++ {
		for cy := 0; cy <= 100; cy++ {
			m := make(map[int]int)
			var ch int
			for i := 0; i < n; i++ {
				if a[i].h == 0 {
					continue
				}
				ch = a[i].h + abs(a[i].x-cx) + abs(a[i].y-cy)
				m[ch]++
				if len(m) > 1 {
					break
				}
			}
			if len(m) != 1 {
				continue
			}
			ok := true
			for i := 0; i < n; i++ {
				if max(ch-abs(a[i].x-cx)-abs(a[i].y-cy), 0) != a[i].h {
					ok = false
					break
				}
			}
			if ok {
				fmt.Println(cx, cy, ch)
				return
			}
		}
	}
}


Measured memory_bytes: 640
#include <iostream>
#include<string>
#include<algorithm>
#include<queue>
#include<cmath>
#include<set>
typedef long long int ll;
using namespace std;
 
int main(){
    int64_t N;
    int64_t T[1000],A[1000];
    cin >> N;
    for(int i=0;i<N;i++){
        cin >> T[i] >> A[i];
    }
    int64_t taka=T[0];
    int64_t aoi=A[0];
    for(int i=1;i<N;i++){
        int64_t tmp_taka=taka/T[i];
        int64_t tmp_aoi=aoi/A[i];
        if(taka%T[i]!=0){
            tmp_taka++;
        }
        if(aoi%A[i]!=0){
            tmp_aoi++;
        }
        int64_t tmp=max(tmp_taka,tmp_aoi);
        taka=tmp*T[i];
        aoi=tmp*A[i];
    }
    cout << taka+aoi << endl;
    
    
    
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<utility>
using namespace std;
int ans,n;
int x[16],y[16];
bool used[16];
pair<int,int>id[8];
void dfs(int d)
{
	if(d*2==n)
	{
		pair<int,int>p[8];
		for(int i=0;i<d;i++)p[i]=make_pair(x[id[i].first]-x[id[i].second],y[id[i].first]-y[id[i].second]);
		int now=0;
		for(int i=0;i<d;i++)
		{
			for(int j=i+1;j<d;j++)
			{
				if(p[i].first*p[j].second==p[i].second*p[j].first)now++;
			}
		}
		if(ans<now)ans=now;
		return;
	}
	int i=0;
	while(used[i])i++;
	for(int j=i+1;j<n;j++)
	{
		if(used[j])continue;
		used[i]=used[j]=1;
		id[d].first=i;
		id[d].second=j;
		dfs(d+1);
		used[i]=used[j]=0;
	}
}
main()
{
	cin>>n;
	for(int i=0;i<n;i++)cin>>x[i]>>y[i];
	dfs(0);
	cout<<ans<<endl;
}



Measured memory_bytes: 3112
#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
typedef pair<int, int> ii;
const int INF = 1 << 29;
const int MOD = 1e9 + 7;

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

int main() {
  vector<int> a;
  for (int i = 7; i <= 55555; ++i) {
    if (i % 5 == 1 && prime(i)) {
      a.push_back(i);
    }
  }
  // cout << a.size() << endl;
  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cout << a[i] << " ";
  }
  cout << endl;
  return 0;
}


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

aset = None

for _ in range(n):
  alist = list(map(int, input().strip().split()))[1:]
  if aset is None:
    aset = set(alist)
  else:
    aset = aset.intersection(set(alist))
print(len(aset))

Measured memory_bytes: 3060
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#include <list>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
//#define cerr if(false) cerr
#ifdef DEBUG
#define show(...) cerr << #__VA_ARGS__ << " = ", debug(__VA_ARGS__);
#else
#define show(...) 42
#endif
using namespace std;
using ll = long long;
using pii = pair<int, int>;
template <typename T, typename S>
ostream& operator<<(ostream& os, pair<T, S> a) {
    os << '(' << a.first << ',' << a.second << ')';
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    for (auto x : v) os << x << ' ';
    return os;
}
void debug() {
    cerr << '\n';
}
template <typename H, typename... T>
void debug(H a, T... b) {
    cerr << a;
    if (sizeof...(b)) cerr << ", ";
    debug(b...);
}
int main(){
    double l;
    cin >> l;
    l/=3.0;
    printf("%.10lf\n", l * l * l);
}


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#define LL long long 
using namespace std;
const int maxn = 300  + 10;
const int maxm = 200000 + 10;
const int inf = 1000000001;

struct Edge {
	int u,v,d;
	
	Edge(int a=0,int b=0,int c=0) {
		u=a; v=b; d=c;
	}
}q[maxm];

bool operator < (Edge a,Edge b) {
    return  a.d<b.d;
}

int n,m;
int a[maxn][maxn],b[maxn][maxn];
int cnt;
LL res;
bool able;

void solve() {
	able=1;	
	
	for(int k=1;k<=n;k++)
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++) {
		b[i][j]=min(b[i][j],b[i][k]+b[k][j]);
	}
	
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++) 
	if(a[i][j]!=b[i][j]) {
		able=0;
		return;	
	}
	
	for(int i=1;i<=n;i++)
	for(int j=i+1;j<=n;j++) 
		q[++m]=Edge(i,j,a[i][j]);
	
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
		b[i][j]=inf;
	for(int i=1;i<=n;i++) b[i][i]=0;
	cnt=n*(n-1);
	sort(q+1,q+m+1);
	
	//return;
	for(int i=1;i<=m;i++) if(b[q[i].u][q[i].v]>q[i].d) {
		res+=q[i].d;
		//printf("test %lld\n",res);
		//printf("Test %d %d %d\n",q[i].u,q[i].v,q[i].d);
		b[q[i].u][q[i].v]=b[q[i].v][q[i].u]=q[i].d;
		cnt-=2;
		//printf("ok\n");
		for(int j=1;j<=n;j++)
		for(int k=1;k<=n;k++) 
		if(j!=q[i].v && k!=q[i].u && b[j][k]>a[j][k] && b[j][q[i].u]!=inf 
		  &&b[q[i].v][k]!=inf && a[j][k]-b[q[i].u][q[i].v]==b[j][q[i].u]+b[q[i].v][k]) {
			b[j][k]=a[j][k];
			b[k][j]=a[j][k];
			cnt-=2;
			if(!cnt) return;
		}
	}
}

int main() {
	//freopen("1.txt","r",stdin);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) 
	for(int j=1;j<=n;j++) {
		scanf("%d",&a[i][j]);
		b[i][j]=a[i][j];
	}
	solve();
	if(!able) cout << "-1\n" ;
	else cout<< res << "\n";
	return 0;
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repo(i,n) for(int i = 1; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define np next_permutation
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define mod 998244353
#define pi acos(-1.0)
const ll INF = 1LL<<61;
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; }
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
ll jou(ll N, ll P){if(P==0) return 1;
    if(P%2==0){ll t = jou(N, P/2);return t*t % mod;
    }return (N * jou(N, P-1)) % mod;}  //jou(n,mod-2)で逆元
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'大文字'+=32;    で小文字に
//  cout << fixed << setprecision (20);   小数点以下2０桁まで
//実行時間制約2秒では２×10^8回くらいまで計算できる



int main(){
  ll n,s;
  cin>>n>>s;
  
  vector<ll> p(n);
  rep(i,n){
    cin>>p[i];
  }

  vector<vector<ll>> ans(n+1,vector<ll>(s+1,0));
  ans[0][0]=1;
  rep(i,n){
    rep(j,s+1){
      ans[i+1][j]+=2*ans[i][j];
      ans[i+1][j]%=mod;
      if(j+p[i]<=s) {
        ans[i+1][j+p[i]]+=ans[i][j];
        ans[i+1][j+p[i]]%=mod;
      }
    }
  }

  cout << ans[n][s]%mod << endl;

}


Measured memory_bytes: 73656
/******* all required header files *******/
#include<iostream>
#include<algorithm>
#include<cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
using namespace std;

/*****All definitions*******/
#define w(t) int t; cin>>t; while(t--)
#define vi vector<int>
#define vs vector<string>
#define mp make_pair
#define ll long long int
/***************************/

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	string str1, str2;
	cin >> str1;
	cin >> str2;
	int count = 0;
	for (int i = 0; i < str1.size(); i++)
	{
		if (str1[i] == str2[i])
			count++;
	}
	if (count == str1.size())
	{
		if (str2.size() == str1.size() + 1)
		{
			cout << "Yes" << "\n";
			return 0;
		}
		else
		{
			cout << "No" << "\n";
			return 0;
		}
	}
	else cout << "No" << "\n";
	return 0;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define ll long long
#define ll_MAX LONG_LONG_MAX
#define ll_MIN LONG_LONG_MIN
#define pi pair<ll,ll>
#define endl "\n"
#define MAXN 100005
using namespace std;

ll n,k,x,y,cnt;
map<ll,ll> mg;

void solve()
{
	cin>>n>>k;
	for(ll i=1;i<=k;i++)
	{
		cin>>x;
		for(ll j=1;j<=x;j++)
		{
			cin>>y;
			mg[y]++;
		}
	}
	for(ll i=1;i<=n;i++)
	{
		if(mg[i]==0) cnt++;
	}
	cout<<cnt<<endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	cout.tie(NULL);
    solve();
}


Measured memory_bytes: 3620
N = int(input())
A = [int(x) for x in input().split()]

times=0
flg=1

while True:
    for i in range(N):
        if A[i]%2==0 :
            A[i] =A[i]/2
        else:
            flg=0
            break
    if flg==1 :
        times +=1
    else :
        break    

print(times)


Measured memory_bytes: 2940
N=int(input())
T,A=map(int,input().split())
H=[int(i) for i in input().split()]
ans=20000
j=0
for i in range(N):
  if ans>abs((T-H[i]*0.006)-A):
    ans=abs((T-H[i]*0.006)-A)
    j=i+1
print(j)

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

typedef long long int ll;

int main()
{
    ll n;
    cin>> n;
    if(n % 2 == 0){
        cout << n / 2;
    }
    else{
        cout << n / 2 + 1;
    }
    
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
typedef long long int ll;
int N;
string s;
bool sol[100005];

bool solve(bool a, bool b){
	sol[1] = a;
	sol[2] = b;
	if(s[1] == 'o' ^ a) sol[N] = !b;
	else sol[N] = b;
	for(int i=3;i<=N-1;++i){
		sol[i] = ((s[i-1]=='o') ^ sol[i-1])?!sol[i-2]:sol[i-2];
	}
	bool chN = ((s[N-1]=='o') ^ sol[N-1])?!sol[N-2]:sol[N-2];
	if(chN != sol[N]) return false;
	bool ch1 = ((s[N]=='o') ^ sol[N])?!sol[N-1]:sol[N-1];
	if(ch1 != sol[1]) return false;
	return true;
}
int main(){
	cin >> N ;
	cin >> s;
	s = " "+s;
	if(solve(true,true)){
		for(int i=1;i<=N;++i){
			cout << (sol[i]?'S':'W');
		}
		cout << endl;
		return 0;
	}
	if(solve(true,false)){
		for(int i=1;i<=N;++i){
			cout << (sol[i]?'S':'W');
		}
		cout << endl;
		return 0;
	}
	if(solve(false,true)){
		for(int i=1;i<=N;++i){
			cout << (sol[i]?'S':'W');
		}
		cout << endl;
		return 0;
	}
	if(solve(false,false)){
		for(int i=1;i<=N;++i){
			cout << (sol[i]?'S':'W');
		}
		cout << endl;
		return 0;
	}
	cout << -1 << endl;
}

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

int main(){
    ll N,K;
    cin >> N >> K;
    vector<ll> A(N);
    ll M = -1;
    rep(i,N){
        cin >> A[i];
        M = max(M,A[i]);
    }
    ll gc = A[0];
    rep(i,N-1){
        gc = __gcd(gc,A[i+1]);
    }
    if((M-K) % gc == 0 && M >= K){
        cout << "POSSIBLE" << endl;
    }else{
        cout << "IMPOSSIBLE" << endl;
    }

}


Measured memory_bytes: 1024
#pragma GCC optimize ("O3")
// #pragma GCC target ("avx")
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define NDEBUG
#define eprintf(...) do {} while (0)
#endif
#include<cassert>

using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

int N;

void MAIN() {
    scanf("%d", &N);

    int ans = 0;
    REP (i, N) {
	int a;
	scanf("%d", &a);
	if (i % 2 == 0 && a % 2 == 1) ans++;
    }

    printf("%d\n", ans);
}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}



Measured memory_bytes: 3752
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		String line = sc.nextLine();
		String[] lines = line.split(" ");
		int N = Integer.parseInt(lines[0]);
		int D = Integer.parseInt(lines[1]);
		int[][] X = new int[N][D];
		int count = 0;

		for (int i = 0; i < N; i++) {
			line = sc.nextLine();
			lines = line.split(" ");
			for (int j = 0; j < D; j++) {
				X[i][j] = Integer.parseInt(lines[j]);
			}
		}


		for (int n = 0; n < N; n++) {
			for(int n2 = n+1; n2 < N; n2++) {
				double sum = 0;
				for (int i = 0; i < D; i++) {
					int diff = Math.abs(X[n][i] - X[n2][i]);
					sum += diff * diff;
				}

				if(isSquareNumber(sum)) {
					count++;
				}
			}
		}

		System.out.println(count);
	}

    static // 平方数かどうかを調べる。
    boolean isSquareNumber (double number) {
        double sqrtOfNumber = Math.sqrt(number);
//    	System.out.println(sqrtOfNumber);
        return (isInteger(sqrtOfNumber));
    }

    static // 整数かどうかを調べる。
    boolean isInteger (double number) {
        return (number == Math.floor(number));
    }

}


Measured memory_bytes: 35772
#include<stdio.h>
int main()
{
  int h,w,i,j;
  while(1){
  scanf("%d %d",&h,&w);
    if(h==0&&w==0)
      break;
  for(i=0;i<h;i++){
    for(j=0;j<w;j++)
      printf("#");
  printf("\n");
  }
printf("\n");
  }
   return 0;
 }

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

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

    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    for (int i = n - 1; i >= 1; i--) cout << a[i] << " ";
    cout << a[0] << endl;

    return 0;
}


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

#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i, m, n) for(int i = (int)(m); i < (int)(n); ++i)


int main()
{
    int A, B;
    cin >> A >> B;

    int ans = -1;
    FOR(i, 1, 100000){
        if(2*i/25 == A and i/10 == B){
            ans = i;
            break;
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
use std::io::*;
use std::str::*;

fn read<T: FromStr>() -> T {
  let mut buf = String::new();
  stdin().read_line(&mut buf).ok();
  buf.trim().parse::<T>().ok().unwrap()
}

fn read_pair<T1: FromStr, T2: FromStr>() -> (T1, T2) {
  let mut buf = String::new();
  stdin().read_line(&mut buf).ok();
  let mut it = buf.trim().split_whitespace();
  let x = it.next().unwrap().parse::<T1>().ok().unwrap();
  let y = it.next().unwrap().parse::<T2>().ok().unwrap();
  (x, y)
}

fn read_pairs<T1: FromStr, T2: FromStr>(n: u32) -> Vec<(T1, T2)> {
  let mut vec: Vec<(T1, T2)> = vec![];
  for _ in 0 .. n {
    vec.push(read_pair());
  }
  vec
}

fn main() {
  let s: u32 = read();
  let lrs: Vec<(u32,u32)> = read_pairs(s);
  let ans: u32 = lrs.into_iter().map(|p| p.1 - p.0 + 1).sum();
  println!("{}", ans);
}


Measured memory_bytes: 4352