akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>

#define REP(i,n) for(auto i=0;i<n;++i)
#define REPR(i,n) for(auto i=n;i>=0;--i)
#define REPI(itr,v) for(auto itr=v.begin();itr!=v.end();++itr)
#define REPIR(itr,v) for(auto itr=v.rbegin();itr!=v.rend();++itr)
#define FOR(i,a,b) for(auto i=a;i<b;++i)
#define SORT(v,n) sort(v, v+n)
#define SORTV(v) sort(v.begin(), v.end())
#define ALL(v) v.begin(),v.end()
#define llong long long
#define ll long long
#define INF 999999999
#define MOD 1000000007
#define pb push_back
#define pf push_front
#define MP make_pair
#define SV(n,v) {int tmp;for(int i=0;i<n;++i){scanf("%d",&tmp);v.push_back(tmp);}}

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

using namespace std;

typedef pair<int,int> pii;

int main(){

  llong n, k;
  cin >> n >> k;

  llong t = n / k;
  cout << min(n - t * k, llabs(n - (t+1) * k)) << endl;
  return 0;
}



Measured memory_bytes: 3552
#include<stdio.h>
int main(){
    int i, j;
    int r, c;
    int a[101][101]={0};
    
    scanf("%d %d", &r, &c);
    for(i=0; i<r; i++){
        for(j=0; j<c; j++){
            scanf("%d", &a[i][j]);
            a[i][c]+=a[i][j];
            a[r][j]+=a[i][j];
            a[r][c]+=a[i][j];
        }
    }
    for(i=0; i<r+1; i++){
        for(j=0; j<c+1; j++){
            if(j!=c){
                printf("%d ", a[i][j]);
            }
            else printf("%d\n", a[i][j]);
        }
    }
    return 0;
}

Measured memory_bytes: 2784
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
using ll = long long;
#define vl vector<long long>
#define vll vector<vector<long long>>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
using pll = pair<long long,long long>;
const long long INF = 1LL << 60;
const long long MOD = 1000000007;
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;
}
//以上テンプレ

int main(){
    string S;
    cin>>S;
    ll a=S.at(0)-'0';
    string Ans="abd=";
    ll count=a;
    bool end=false;
    for(ll bit=0;bit<(1<<3);++bit){
        if(end){
            break;
        }
        rep(i,3){
        if(bit&(1<<i)){
            Ans.at(i)='+';
            count+=S.at(i+1)-'0';
        }else{
            Ans.at(i)='-';
            count-=S.at(i+1)-'0';
        }
        if(i==2){
        if(count==7){
            end=true;
            break;
        }else{
            count=a;
        }
        }
        }
    }
    rep(i,4) cout<<S.at(i)<<Ans.at(i);
    cout<<"7"<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,c;
	cin>>a>>b>>c;
	for(int i=1;i<=1000001;i++)
	{
		if(i*a%b==c)
		{
			cout<<"YES"<<endl;
			return 0;
		}
	}
	cout<<"NO"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ll N,A,B,C;cin >> N >> A >> B >> C;vector<string> s(N);
    for(int i =0;i <N;i++) cin >> s[i];
    string ansS;
    for(int i = 0; i <N;i++){
        if (s[i] == "AB"){
            if (A == 0 && B == 0) break;
            if (A == 1 && B == 1 && C == 0){
                if (i != N - 1){
                    if (s[i + 1] == "AC"){
                        A++;B--;ansS.push_back('A');
                        continue;
                    }
                    else if (s[i + 1] == "BC") {
                        A--;B++;ansS.push_back('B');
                        continue;
                    }
                }
            }
            if (A >= B){
                A--;B++;ansS.push_back('B');

            }
            else{
                A++;B--;ansS.push_back('A');
            }
        }
        else if (s[i] == "AC"){
            if (A == 0 && C == 0) break;
            if (A == 1 && B == 0 && C == 1){
                if (i != N-1){
                    if (s[i + 1] == "AB"){
                        A++;C--;ansS.push_back('A');
                        continue;
                    }
                    else if (s[i + 1] == "BC"){
                        A--;C++;ansS.push_back('C');
                        continue;
                    }
                }
            }
            if (A >= C){
                A--;C++;ansS.push_back('C');
            }
            else{
                A++;C--;
                ansS.push_back('A');
            }
        }
        else if (s[i] == "BC"){
            if (B == 0 && C == 0) break;
            if (A == 0 && B == 1 && C == 1){
                if (i != N - 1){
                    if (s[i + 1] == "AB"){
                        B++;C--;
                        ansS.push_back('B');
                        continue;
                    }
                    else if (s[i + 1] == "AC"){
                        B--;C++;
                        ansS.push_back('C');
                        continue;
                    }
                }
            }
            if (B >= C){
                B--;C++;
                ansS.push_back('C');
            }
            else{
                B++;C--;
                ansS.push_back('B');
            }
        }
    }
    if (ansS.size() != N) cout << "No" << endl;
    else{
        cout << "Yes" << endl;
        for(int i =0;i <N;i++) cout << ansS[i] << endl;
    }
}

Measured memory_bytes: 6692
import java.util.*;

class Main {
    static ArrayList<Integer>[] map;
    static final int inf = Integer.MAX_VALUE/10;
    static int[] other;
    static int[] X;
    static int[][] dp;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        map = new ArrayList[n+1];
        for(int i=0;i<=n;i++) map[i] = new ArrayList<>();
        other = new int[n+1];
        X = new int[n+1];
        for(int i=2;i<=n;i++){
            int p = sc.nextInt();
            map[p].add(i);
        }
        for(int i=1;i<=n;i++) X[i] = sc.nextInt();
        dfs(1);
        String ans = other[1]<inf?"POSSIBLE":"IMPOSSIBLE";
        System.out.println(ans);
    }

    static void dfs(int s){
        int len = map[s].size();
        if(len==0) return;
        for(int i=0;i<len;i++) dfs(map[s].get(i));
        dp = new int[len+1][X[s]+1];
        for(int i=0;i<dp.length;i++) Arrays.fill(dp[i],inf);
        dp[0][0] = 0;
        for(int i=1;i<=len;i++){
            int curX = X[map[s].get(i-1)];
            int curF = other[map[s].get(i-1)];
            for(int j=0;j<=X[s];j++){
                if(j>=curX) dp[i][j] = Math.min(dp[i][j],dp[i-1][j-curX]+curF);
                if(j>=curF) dp[i][j] = Math.min(dp[i][j],dp[i-1][j-curF]+curX);
            }
        }
        other[s] = inf;
        for(int j=0;j<=X[s];j++){
            other[s] = Math.min(other[s],dp[len][j]);
        }
    }
}


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

#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define repd(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define forr(i,a,b) for(ll i=(a);i<=(b);i++)
#define ford(i,a,b) for(ll i=(a);i>=(b);i--)
#define all(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define size(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000 //10^12
#define MOD 10000007 //10^9+7
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define MAXR 100000 //10^5:最大のrange(素数列挙などで使用)



int main(void) {
    long int N,i,j;
    cin >> N;
    long int n[1999999];
    long int m[1999999];
    for(i=0;i<N-1;++i){
       cin >> n[i];
      
    }
     for(i=0;i<N-1;++i){
     
       m[n[i]-1]++;
    }
    for (j=0;j<N;++j){
        
         cout << m[j] << "\n";
    

    }   
    
  return 0;
}

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

int main(){
    int K, S;
    int cnt = 0;
    cin >> K >> S;
    
    for(int X=0; X < K+1; X++){
        for(int Y=0; Y < K+1; Y++){
            int Z = S - X - Y;
            if(0 <= Z and Z<=K) cnt++;
            
        }
    }

    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
 
int strings_count[101];
int strings_from[101][100];
int visited[101];

int longest_from(int start);

int main()
{
	while (1) {
		int n;
		int i;
		int longest;

		scanf("%d", &n);
		if (n == 0) {
			break;
		}

		memset(strings_from, 0, sizeof(strings_from));
		memset(strings_count, 0, sizeof(strings_count));
		memset(visited, 0, sizeof(visited));

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

		longest = 0;
		for (i = 1; i <= 100; i++) {
			if (strings_count[i] > 0) {
				int longest_tmp;
				longest_tmp = longest_from(i);
				if (longest_tmp > longest) {
					longest = longest_tmp;
				}
			}
		}

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

	return 0;
}

int longest_from(int start)
{
	int i;
	int longest;
	longest = 0;
	visited[start] = 1;
	for (i = 0; i < strings_count[start]; i++) {
		int next;
		next = strings_from[start][i];
		if (!visited[next]) {
			int longest_tmp;
			longest_tmp = longest_from(next);
			if (longest_tmp > longest) {
				longest = longest_tmp;
			}
		}
	}
	visited[start] = 0;
	return longest + 1;
}

Measured memory_bytes: 644
#include<cstdio>
#include<algorithm>
using namespace std;
inline int read()
{
	int x,f=1;char c;
	while((c=getchar())<'0'||c>'9')if(c=='-')f=0;
	for(x=c-'0';(c=getchar())>='0'&&c<='9';)x=x*10+c-'0';
	return f?x:-x;
}
#define MN 200000
#define MK 19
int x[MN+5],a[MK+1],an,l[MK+1][MN+5],r[MK+1][MN+5],lf[1<<MK],rf[1<<MK],c[MN+5];
int main()
{
	int n,v,i,j;
	n=read();v=read();
	for(i=1;i<=n;++i)x[i]=read();
	for(;;v>>=1){a[++an]=v;if(!v)break;}swap(a[1],a[an]);
	for(i=1;i<=an;++i)
	{
		for(l[i][n+1]=j=n;j;--j)l[i][j]=x[j+1]-x[j]<=a[i]?l[i][j+1]:j;
		for(r[i][0]=j=1;j<=n;++j)r[i][j]=x[j]-x[j-1]<=a[i]?r[i][j-1]:j;
	}
	for(i=0;i<1<<an-1;++i)rf[i]=n+1;
	for(i=0;i<1<<an-1;++i)for(j=1;j<an;++j)if(!(i&(1<<j-1)))
		lf[i|(1<<j-1)]=max(lf[i|(1<<j-1)],l[j][lf[i]+1]),
		rf[i|(1<<j-1)]=min(rf[i|(1<<j-1)],r[j][rf[i]-1]);
	for(i=0;i<1<<an-1;++i)if(l[an][lf[i]+1]>=rf[i^((1<<an-1)-1)]-1)
		++c[r[an][lf[i]+1]],--c[l[an][lf[i]+1]+1];
	for(i=1;i<=n;++i)puts((c[i]+=c[i-1])?"Possible":"Impossible");
}

Measured memory_bytes: 39040
<?php
//error_reporting(0);
$N = trim(fgets(STDIN));
//list($N,$K) = explode(" ",trim(fgets(STDIN)));
//$a = explode(" ",trim(fgets(STDIN)));
//$H = explode(" ",trim(fgets(STDIN)));

$len = strlen($N);
$m = 99999999;
for($i=0;$i<$len-2;$i++) {
  $v = substr($N,$i,3);
  $m = min(abs($v-753),$m);
}
printf("%d\n",$m);

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

int main() {
	int n, l;
	cin >> n >> l;
	int min = 300;
	for (int i = 0; i < n; i++)
		if (abs(l + i) < abs(min))
			min = l + i;

	cout << n * (2 * l + n - 1) / 2 - min;
}


Measured memory_bytes: 256
/*
LANG:C++
PROB:

*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
#include <iostream>
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)


using namespace __gnu_pbds;
using namespace std;


typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update>
    ordered_set;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;
typedef unsigned long long ui64;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }


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

    // ifstream fin(".in");
    // ofstream fout(".in");

i64 k;
cin>>k;
vi64 v(k+1),pref(k+1);
forn(i,k)
cin>>v[i];
i64 ans=v[0];
for1(i,k-1)
{
if(v[i-1]<v[i])
ans+=v[i]-v[i-1];
}


cout<<ans;

    return 0;
  }


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
typedef long long ll;
ll q, dp[1010][1010];
string s, t;
int main(void){
    // Your code here!
    cin >> q;
    for (ll k = 0; k < q; k++) {
        cin >> s >> t;
        for (ll i = 1; i <= s.length(); i++) {
            for (ll j = 1; j <= t.length(); j++) {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                if (s[i - 1] == t[j - 1]) {
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
                }
            }
        }
        cout << dp[s.length()][t.length()] << endl;
    }
}



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

using namespace std;

int main(){
	string s;
	cin>>s;
	if(s.substr(0,4) == "2017"){
		s.insert(s.begin()+3,'8');
		s.erase(s.begin() + 4);
	}
	cout<<s<<endl;

	return 0;

}

Measured memory_bytes: 256
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using pii=pair<int,int>;
using vll=vector<ll>;
using vvll=vector<vll>;


int main(void)
{
	int a, b;
	while(scanf("%d%d", &a, &b)==2)
	{
		int ans=max(a-b*2, 0);

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


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

using namespace std;

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

#define ALL(obj)	(obj).begin(),(obj).end()

typedef unsigned int 			uint;
typedef unsigned long long int	ull;
typedef long long int 			ll;

typedef pair<int,int>			P;
typedef vector<int>				V;
typedef vector<V>				VV;

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define MAX 		100050

const ll LINF = (ll)1e18+7;		//
const int INF = 1e9+7;			//2,147,483,647 (Max int)
const int MOD = 1e9+7;
// テンプレ終了
//====================================================================//




//
int main(){
	int X,Y,Z,K;
	cin >> X>>Y>>Z>>K;
	vector<ll> A(X),B(Y),C(Z);
	REP(i,X)cin>>A[i];
	REP(i,Y)cin>>B[i];
	REP(i,Z)cin>>C[i];

	vector<ll> DP(X*Y,0);
	REP(i,X)REP(j,Y)DP[i*Y+j] = A[i]+B[j];

	sort(ALL(DP),[&](ll x,ll y){return x > y;});
	sort(ALL(C),[&](ll x,ll y){return x > y;});
	
	int xy = min(K,X*Y);
	int c = min(K,Z);
	vector<ll> E(xy*c);
	REP(i,xy)REP(j,c){
		E[i*c+j] = DP[i]+C[j];
		//printf("[%d,%d] : %lld\n",i,j,E[i*xy+j]);
	}
	sort(ALL(E),[&](ll x,ll y){return x > y;});

	REP(i,K)cout << E[i] << endl;

	return 0;
}




Measured memory_bytes: 31616
a1, b1 = [int(x) for x in input().split()]
a2, b2 = [int(x) for x in input().split()]
a3, b3 = [int(x) for x in input().split()]

l = [a1, b1, a2, b2, a3, b3]
col = [l.count(1), l.count(2), l.count(3), l.count(4)]
if col.count(1) == 2 & col.count(2) == 2:
    print('YES')
else:
    print('NO')

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define LLI long long int

LLI n,num[110],a,memo[1000][30],ans;

using namespace std;

LLI po(int low,int sum){
    LLI a=0,b=0;

    if(memo[low][sum]!=0)return memo[low][sum];

    if(low==n-2){
    if(sum==num[low+1])return 1;
    return 0;

    }else {
    if(sum+num[low+1]<=20)a=po(low+1,sum+num[low+1]);
    if(sum-num[low+1]>=0)b=po(low+1,sum-num[low+1]);
          }

          ans=a+b;

    memo[low][sum]=ans;
      return ans;

      }


int main(){

    cin >> n;

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

    }

    cout << po(0,num[0]) << endl;


return 0;
}

Measured memory_bytes: 1188
#include <stdio.h>

int main(){
    int w,h,x,y,r;
    scanf("%d%d%d%d%d",&w,&h,&x,&y,&r);
    
    if(x+r>w||x-r<0||y+r>h||y-r<0) printf("No\n");
    else printf("Yes\n");
}


Measured memory_bytes: 2124
#include <bits/stdc++.h>
#define ll long long
#define mem( f, x ) memset( f, x, sizeof( f ) )
#define INF 0x3f3f3f3f
#define pii pair<int, int>
#define mk( x, y ) make_pair(x, y)
#define pk push_back
#define fi first
#define se second
using namespace std;
const int M = 1e6+50;
const int N = 1e6+50;
const int MAXN = 1e6+50;
int n;
char s[N];
pii add[N], sub[N];

bool cmp1( pii p1, pii p2 ){
    if( p1.se == p2.se )
        return p1.fi > p2.fi;
    return p1.se < p2.se;
}

bool cmp2( pii p1, pii p2 ){
    if( p1.fi == p2.fi )
        return p1.se < p2.se;
    return p1.fi > p2.fi;
}

int main( ){
    while( scanf( "%d", &n ) != EOF ){
        int cnt_a = 0, cnt_s = 0, sum = 0;
        for( int i = 1; i <= n; i++ ){
            scanf( "%s", s );
            int len = strlen( s );
            int st = 0, ed = len-1;
            int L = 0, R = 0;
            while( s[st] == ')' && st < len )
                R++, st++, sum--;
            while( s[ed] == '(' && ed >= 0 )
                L++, ed--, sum++;
            int tmp = 0;
            for( int j = st; j <= ed; j++ ){
                if( s[j] == '(' ) tmp++, sum++;
                else tmp--, sum--;
            }
            if( tmp > 0 ) L += tmp;
            else R -= tmp;
            if( L >= R ) add[cnt_a++] = mk( L, R );
            else sub[cnt_s++] = mk( L, R );
        }
        if( sum ){
            printf( "No\n" );
            continue;
        }
        sort( add, add+cnt_a, cmp1 );
        sort( sub, sub+cnt_s, cmp2 );
        sum = 0;
        bool flag = 0;
        for( int i = 0; i < cnt_a; i++ ){
            sum -= add[i].se;
            if( sum < 0 ){
                flag = 1;
                printf( "No\n" );
                break;
            }
            sum += add[i].fi;
        }
        if( flag ) continue;
        for( int i = 0; i < cnt_s; i++ ){
            sum -= sub[i].se;
            if( sum < 0 ){
                flag = 1;
                printf( "No\n" );
                break;
            }
            sum += sub[i].fi;
        }
        if( flag ) continue;
        if( sum ) flag = 1;
        if( flag ) printf( "No\n" );
        else printf( "Yes\n" );
    }
    return 0;
}


Measured memory_bytes: 11484
N,M=map(int,input().split())
ab=list(list(map(int,input().split())) for _ in range(N))
cd=list(list(map(int,input().split())) for _ in range(M))

for i in range(N):
    k=0
    d=abs(ab[i][0]-cd[0][0])+abs(ab[i][1]-cd[0][1])
    for j in range(1,M):
        if abs(ab[i][0]-cd[j][0])+abs(ab[i][1]-cd[j][1])<d:
            k=j
            d=abs(ab[i][0]-cd[j][0])+abs(ab[i][1]-cd[j][1])
    print(k+1)


Measured memory_bytes: 9224
#include<bits/stdc++.h>
#include<string>
using namespace std;
int main()
{
    long long int t,n,a,b,c,d,i,j,k,l,m,cnt,flag,cnt1,flag1;
    int w,s;
    cin>>s>>w;
    if(w>=s)
    {
        cout<<"unsafe"<<endl;
    }
    else
    {
        cout<<"safe"<<endl;
    }
    return 0;
}



Measured memory_bytes: 3592
#include<bits/stdc++.h>
#define MAXN 1000005
#define INF int(16843009)
using namespace std;

int N,M;

struct edge{
	int u,v;
	edge(int u=0, int v=0):u(u), v(v){}
};

vector<edge> adjc[MAXN];
vector<int> adj1[MAXN];

void addE(int u, int v){
	cerr<<"addE: "<<u<<" "<<v<<endl;
	adj1[u].push_back(v);
	adj1[v].push_back(u);
}

int d[MAXN];
void bfs(){
	memset(d, 1, sizeof(d));
	d[1] = 0;
	queue<int> q;
	q.push(1);
	
	int u,v;
	while(!q.empty()){
		u = q.front(); q.pop();
		if(u==N) return;
		
		for(int k=0;k<adj1[u].size();k++){
			v = adj1[u][k];
			if(d[u] + 1 < d[v]){
				d[v] = d[u] + 1;
				q.push(v);
			}
		}
	}
}

int fa[MAXN];
int p[MAXN];
int findR(int x){
	if(p[x]==x) return x;
	else return p[x] = findR(p[x]);
}

int main(){
	
	scanf("%d%d", &N, &M);
	
	int u,v,c;
	for(int i=1;i<=M;i++){
		scanf("%d%d%d", &u, &v, &c);
		adjc[c].push_back(edge(u,v));
	}
	
	int top = N;
	for(int i=1;i<=1e6;i++){
		//cout<<i<<endl;
		if(adjc[i].size()==0) continue;
		//
		for(int k=0;k<adjc[i].size();k++){
			u = adjc[i][k].u; v = adjc[i][k].v;
			p[u] = u; p[v] = v;
			fa[u] = fa[v] = 0;
		}
		
		int ru,rv; 
		for(int k=0;k<adjc[i].size();k++){
			u = adjc[i][k].u; v = adjc[i][k].v;
			ru = findR(u); rv = findR(v);
			p[ru] = rv;
		}
		
		for(int k=0;k<adjc[i].size();k++){
			u = adjc[i][k].u; v = adjc[i][k].v;
			ru = findR(u); rv = findR(v);
			//
			if(fa[ru]) addE(u,fa[ru]);
			else{
				fa[ru] = ++top;
				addE(u,top);
			}
			
			//
			if(fa[rv]) addE(v,fa[rv]);
			else{
				fa[rv] = ++top;
				addE(v,top);
			}
		}
	}
	//cout<<"pass"<<endl;
	bfs();
	
	if(d[N]==INF) cout<<"-1"<<endl;
	else cout<<d[N]/2<<endl;
	
	return 0;
}


Measured memory_bytes: 73216
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;
const int N=605,P=1e9+7;
int n,K,ans,fac2[N],match[N],f[2][N];
int main(){
	fac2[0]=1;
	for(int i=1;i<N;++i)fac2[i]=1LL*fac2[i-1]*(2*i-1)%P;
	scanf("%d%d",&n,&K);
	for(int i=1;i<=K;++i){
		int k1,k2;
		scanf("%d%d",&k1,&k2);
		match[k1]=k2,match[k2]=k1;
	}
	rep(i,1,n*2){
		int cur=0;
		memset(f[cur],0,sizeof(f[cur]));
		f[cur][0]=1;
		int sz1=0,sz2=0;
		for(int j=i;j<=n*2;++j){
			if(match[j]){
				if(match[j]>j)++sz1;
				else if(match[j]<i)break;
				else --sz1;
			}else{
				++sz2;
				cur^=1;
				memset(f[cur],0,sizeof(f[cur]));
				rep(k,0,min(n,sz2)){
					if(f[cur^1][k]){
						if(k){
							(f[cur][k-1]+=1LL*f[cur^1][k]*k%P)%=P;
						}
						(f[cur][k+1]+=f[cur^1][k])%=P;
					}
				}
			}
			if(!sz1){
				(ans+=1LL*f[cur][0]*fac2[n-K-(sz2/2)]%P)%=P;
				f[cur][0]=0;
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 3624
n,k=list(map(int,input().split()))
l=list(map(int,input().split()))
dp=[0]*n
dp[0]=0
dp[1]=abs(l[1]-l[0])
for i in range(2,n):
	x=10**9
	for j in range(i-1,i-k-1,-1):
		if j>=0:x=min(dp[j]+abs(l[j]-l[i]),x)
	dp[i]=x
print(dp[-1])


Measured memory_bytes: 52448
function nxt(Q)
  x=shift!(Q)
  if x%10>0
    push!(Q,x*10+x%10-1)
  end
  push!(Q,x*10+x%10)
  if x%10<9
    push!(Q,x*10+x%10+1)
  end
  Q
end
function main()
  Q=[1,2,3,4,5,6,7,8,9]
  for _=2:parse(Int,readline())
    Q=nxt(Q)
  end
  println(Q[1])
end
main()


Measured memory_bytes: 114992
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <ctime>

#define Rep(i, n) for (int i = 1; i <= n; i ++)
#define Rep0(i, n) for (int i = 0; i <= n; i ++)
#define RepG(i, x) for (int i = head[x]; i; i = edge[i].next)
#define v edge[i].to
#define mp(a, b) make_pair(a, b)

using namespace std;

typedef long long LL;
const int N = 1010;
const int mod = 1e9 + 7;

struct matrix{ LL mat[3][3]; }b, ans;
matrix operator*(matrix a, matrix b)
{
    matrix tmp; memset(tmp.mat, 0, sizeof(tmp.mat));
    Rep0(i, 1) Rep0(j, 1) Rep0(k, 1) tmp.mat[i][j] = (tmp.mat[i][j] + a.mat[i][k] * b.mat[k][j] % mod + mod) % mod;
    return tmp;
}
void mat_qpow(matrix &a, LL k)
{
	k %= (mod - 1);
    matrix tmp; memset(tmp.mat, 0, sizeof(tmp.mat));
    Rep0(i, 1) tmp.mat[i][i] = 1;
    while (k){
        if (k & 1) tmp = tmp * a;
        a = a * a, k >>= 1;
    }
    a = tmp;
}

char s[N];
int g[N][N];

LL qpow(LL a, LL b)
{
	b %= (mod - 1);
	LL ret = 1, base = a;
	while (b) {
		if (b & 1) ret = ret * base % mod;
		base = base * base % mod, b >>= 1;
	}
	return ret;
}

int main()
{
	int h, w;
	LL k;
	scanf("%d%d%lld", &h, &w, &k);
	
	if (!k) { printf("1\n"); return 0;}
	
	Rep(i, h) {
		scanf("%s", s + 1);
		Rep(j, w) g[i][j] = (s[j] =='#');
	}
	int cnt0 = 0, cnt1 = 0, cnt = 0;
	Rep(i, h) Rep(j, w) cnt += g[i][j];
	Rep(i, w) if (g[1][i] == 1 && g[h][i] == 1) cnt0 ++;
	Rep(i, h) if (g[i][1] == 1 && g[i][w] == 1) cnt1 ++;

	if (!cnt0 && !cnt1) printf("%lld\n", qpow(cnt, k - 1));
	else if (cnt0 && cnt1) printf("1\n");
	else {
		int tt = 0;
		Rep(i, h) Rep(j, w) {
			if (cnt1 && g[i][j] && g[i][j - 1]) tt ++;
			else if (cnt0 && g[i][j] && g[i - 1][j]) tt ++;
		}
		b.mat[0][0] = cnt, b.mat[1][0] = -tt;
		b.mat[0][1] = 0, b.mat[1][1] = cnt0 + cnt1;
		mat_qpow(b, k - 1);
		
		ans.mat[0][0] = 1, ans.mat[0][1] = 1;
		ans = ans * b;

		printf("%lld\n", ans.mat[0][0]);
	}
	
	return 0;
}
/*
11 15 2
.....#.........
....###........
....####.......
...######......
...#######.....
..##.###.##....
..##########...
.###.....####..
.####...######.
###############
#.##..##..##..#
*/

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

int main() {
    int N = 0;
    cin >> N;
    int X = 0, Y = 0;
    vector<char> judge(N);
    bool Z = false;

    for (int i = 0; i < N; i++) {
        cin >> X >> Y;
        if (X == Y) {
            judge.at(i) = 'Y';
        } else {
            judge.at(i) = 'N';
        }
    }

    for (int i = 0; i < N - 2; i++) {
        if (judge.at(i) == 'Y' && judge.at(i+1) == 'Y' && judge.at(i+2) == 'Y') {
            Z = true;
            break;
        } else {}
    }

    if (Z == true) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 3620
s = input()
while len(s) != 0:
    if s[-5:] == 'dream' or s[-5:] == 'erase':
        s = s[:-5]
    elif s[-6:] == 'eraser':
        s = s[:-6]
    elif s[-7:] == 'dreamer':
        s = s[:-7]
    else:
        break
print('YES' if len(s) == 0 else 'NO')


Measured memory_bytes: 3188
t = str(input())
p = str(input())
tt = len(t)
pp = len(p)
y = 0

#print(t, p)

for i in range(tt - pp + 1):
    x = 0
    for j in range(pp):
        #print(i, j, t[i+j], p[j])

        if t[i+j] == p[j]:
            x = x + 1
        #print(x)
        
    if x == pp:
        y = y + 1
        #print('→',i)
        print(i)


Measured memory_bytes: 5568
#include <bits/stdc++.h>
//#include <ext/numeric>


using namespace std;
//using namespace __gnu_cxx;

const int MAXN = (int)1e5 + 5;
vector<int> adjList[MAXN];
int mx = 0;
map<pair<int, int>, int> mp;

int getColor(int u, int v) {
    if (u > v)
        swap(u, v);
    return mp[{u, v}];
}

void setColor(int u, int v, int color) {
    if (u > v)
        swap(u, v);
    mp[{u, v}] = color;
}

void dfs(int u, int par) {
    int c = 1;
    int come = getColor(u, par);
    for (int v : adjList[u]) {
        if (v == par)
            continue;
        if (c == come)
            ++c;
        setColor(u, v, c);
        ++c;
        dfs(v, u);
    }
    mx = max(mx, max(c - 1, come));
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0), cout.precision(10), cout << fixed;

    int n;
    cin >> n;
    vector<pair<int, int>> edges;
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        adjList[u].push_back(v);
        adjList[v].push_back(u);
        edges.push_back({u, v});
    }


    dfs(1, 0);

    cout << mx << '\n';
    for (auto e : edges) {
        cout << getColor(e.first, e.second) << '\n';
    }




    return 0;
}

Measured memory_bytes: 19524
#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;

int main() {
    ll n, m, x, y;
    cin >> n >> m >> x >> y;
    vector<ll> xn(n), yn(m);
    for(auto &i: xn) cin >> i;
    for(auto &i: yn) cin >> i;
    xn.push_back(x);
    yn.push_back(y);
    sort(xn.rbegin(), xn.rend());
    sort(yn.begin(), yn.end());
    if(xn[0] < yn[0]) cout << "No War" << endl;
    else cout << "War" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
  string s;
  cin >> s;
  vector<string> t(7);
  t[1] = "MON";
  t[2] = "TUE";
  t[3] = "WED";
  t[4] = "THU";
  t[5] = "FRI";
  t[6] = "SAT";
  t[0] = "SUN";
  int ans = 0;
  for(int i = 0;i < 7;i++){
    if(t[i] == s) ans = 7-i;
  }
  cout << ans <<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep_lr(i,l,r) for(int i=(l);i<(r);i++)
#define all(x) (x).begin(),(x).end()
#define V vector
typedef V<int> vi;
typedef V<vi> vvi;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<int, int, int> T;
constexpr int INF = INT_MAX >> 1;
constexpr ll LINF = 5000000000000000LL;
constexpr int MOD = 998244353;

int main() {
	
	int n;
	cin >> n;
	vi a(n);
	int x = 0;
	rep(i, n) {
		cin >> a[i];
		x ^= a[i];
	}
	rep(i, n) {
		int ans = x ^ a[i];
		cout << ans << endl;
	}
}

Measured memory_bytes: 3960
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
using ll = long long;
ll a[N], s[N];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
		cin >> a[i];
	sort(a + 1, a + 1 + n);
	for (int i = 1; i <= n; ++i)
		s[i] = s[i - 1] + a[i];
	ll l = 1, r = 1e10;
	for (; l < r; )
	{
		ll mid = (l + r) / 2 + 1, cnt = 0;
		for (int i = 1; i <= n; ++i)
			cnt += n - (lower_bound(a + 1, a + 1 + n, mid - a[i]) - a) + 1;
		if (cnt >= m)
			l = mid;
		else
			r = mid - 1;
	}
	ll ans = 0, cnt = 0;
	for (int i = 1; i <= n; ++i)
	{
		int pos = lower_bound(a + 1, a + 1 + n, l - a[i]) - a, tot = n - pos + 1;
		cnt += tot;
		ans += a[i] * tot + s[n] - s[pos - 1];
	}
	cout << ans - (cnt - m) * l;
}


Measured memory_bytes: 1792
program keyence
  implicit none
  character(len=100)::s
  character(len=7)::ke='keyence'
  integer :: i, k
  read(*,*) s
  s=trim(s)
  k=len_trim(s)

  do i = 1, 6
     if ( s(1:i)==ke(1:i) .and. s(k+i-6:k)==ke(i+1:7)) then
        write(*,*) 'YES'
        stop
     end if
  end do

  if ( s(1:7) == ke .or. s(k-6:k) == ke ) then
     write(*,*) 'YES'
     stop
  end if

  write(*,*) 'NO'
  
  stop
end program keyence
     


Measured memory_bytes: 256
#include<queue>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define N 100005
#define M 100005
#define ll long long
int n,m;
struct node{
	int a,b;
}job[N];
ll ans;
priority_queue<int>Q;
bool cmp(node p,node q)
{
	return p.a<q.a;
	//if(p.b==q.b) return p.a>q.a;
	//return p.b>q.b;
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
    	scanf("%d %d",&job[i].a,&job[i].b);
	sort(job+1,job+n+1,cmp);
	int i=1;
	for(int t=m;t>=0;t--)
	{
		while(m-job[i].a>=t&&i<=n)
		{
			//printf("%d\n",i);
			Q.push(job[i].b);
			i++;
		}
		if(Q.empty()) continue;
		int tmp=Q.top();Q.pop();
		ans+=tmp;
	}
	/*int i=1;
	for(int t=0;t<=m,i<=n;t++)
	{
		while(job[i].a+t>m)
			i++;
		ans+=job[i].b,i++;
	}*/
	printf("%lld\n",ans);
    return 0;
}

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

public class Main {
  static Scanner sc = new Scanner(System.in);

  public static void main(String[] args) {
    int N = sc.nextInt();
    int[] A = new int[N];
    int sum = 0;
    for (int i = 0; i < N; i++) {
      A[i] = sc.nextInt();
      sum += A[i];
    }
    if (N == 1) {
      System.out.println(sum);
      return;
    }
    long[] exist = new long[(sum + 63) / 64];
    exist[0] = 1L;
    long[] tmp = new long[exist.length];
    for (int i = 0; i < N; i++) {
      Arrays.fill(tmp, 0L);
      for (int j = 0; j < exist.length; j++) {
        if (A[i] % 64 == 0) {
          if (j + A[i] / 64 < tmp.length) tmp[j + A[i] / 64] |= exist[j];
        } else {
          if (j + A[i] / 64 < tmp.length) tmp[j + A[i] / 64] |= exist[j] << (A[i] % 64);
          if (j + A[i] / 64 + 1 < tmp.length) tmp[j + A[i] / 64 + 1] |= exist[j] >>> (64 - A[i] % 64);
        }
        exist[j] |= tmp[j];
      }
      exist[A[i] / 64] |= 1L << (A[i] % 64);
    }

    for (int i = (sum + 1) / 2; ; i++) {
      if ((exist[i / 64] & (1L << i % 64)) != 0) {
        System.out.println(i);
        return;
      }
    }
  }

}


Measured memory_bytes: 28144
using System;
using System.Linq;

class Program
{
  static void Main()
  {
    while(true)
    {
      string[] inputs = Console.ReadLine().Split(' ');
      int h = int.Parse(inputs[0]);
      int w = int.Parse(inputs[1]);
      if (h == 0 && w == 0) break;

      string s1 = string.Concat(Enumerable.Repeat("#.", w / 2));
      string s2 = string.Concat(Enumerable.Repeat(".#", w / 2));

       for (int i = 0; i < h; i ++)
        {
          if (i % 2 == 0)
          {
            if (w % 2 == 0)
            {
              Console.WriteLine(s1);
            }
            else Console.WriteLine(s1 + "#");
          }
          else
          {
            if (w % 2 == 0)
            {
              Console.WriteLine(s2);
            }
            else Console.WriteLine(s2 + ".");
          }
        }
      Console.WriteLine();
    }
  }
}



Measured memory_bytes: 16264
n,c,k = map(int,input().split())
t = [int(input()) for i in range(n)]
t.sort()

pas = 1
last_bus = t[0] + k
ans = 1

for i in t[1:]:
  if i <= last_bus and pas < c:
    pas +=1
  else:
    ans +=1
    pas =1
    last_bus = i + k
    
    
print(ans)

Measured memory_bytes: 7884
h,w = map(int,input().split())
s = h*w
if s%2 == 0 and h > 1 and w > 1:
  print(int(s/2))
elif s%2 == 1 and h > 1 and w > 1:
  print(s//2 + 1)
else:
  print(1)

Measured memory_bytes: 3060
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm> 
#include <cmath>
#include <map>

using namespace std;

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

map<pii, LL> mp;
int H, W, N;
LL ans[10];

bool inbounds(int a, int b) {
	return a >= 0 && b >= 0 && a < H && b < W;
}
void add(int a, int b) {
	if (!inbounds(a, b) || !inbounds(a + 2, b + 2)) {
		return;
	}
	mp[pii(a, b)]++;
}
int main() {
	scanf("%d%d%d", &H, &W, &N);
	for (int i = 0; i < N; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		a--; b--;

		for (int x = -2; x <= 0; x++) {
			for (int y = -2; y <= 0; y++) {
				add(a + x, b + y);
			}
		}
	}

	LL sum = 0;
	for (map<pii, LL>::iterator itr = mp.begin(); itr != mp.end(); itr++) {
		ans[itr->second]++;
	}
	for (int i = 0; i < 10; i++) {
		sum += ans[i];
	}

	LL zeros = ((LL)H - 2) * ((LL)W - 2) - sum;
	cout << zeros << '\n';
	for (int i = 1; i < 10; i++) {
		cout << ans[i] << '\n';
	}
}

Measured memory_bytes: 56448
#include <bits/stdc++.h>
#define ll long long int
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;

bool find(string a, string b){
    int va[26]={0}, vb[26]={0};
    for(auto i : a) va[i-'a']++;
    for(auto i : b) vb[i-'a']++;
    for(int i=0; i<26; i++){
        if(va[i] != vb[i]) return false;
    }
    return true;
}

int main() {
    fast
	ll n, ans=0, start=0;
	cin>>n;
	cin.ignore();
	vector<string> v(n);
	for(int i=0; i<n; i++){
	    getline(cin,v[i]);
	    sort(v[i].begin(),v[i].end());
	}
	sort(v.begin(),v.end());
	for(int i=1; i<n; i++){
	    if(v[i] != v[i-1]){
	        ans += (i-start) * (i-start-1) / 2;
	        start = i;
	    }
	}
	ans += (v.size()-start) * (v.size()-start-1) / 2;
	cout << ans << '\n';
}


Measured memory_bytes: 5760
import std.stdio, std.string, std.conv, std.algorithm, std.numeric;
import std.range, std.array, std.math, std.typecons, std.container, core.bitop;

void main() {
    int h, w;
    scan(h, w);

    auto c = new int[][](10, 10);
    auto d = new int[][](10, 10);

    foreach (i ; 0 .. 10) {
        c[i] = readln.split.to!(int[]);
        d[i] = c[i].dup();
    }

    foreach (k ; 0 .. 10) {
        foreach (i ; 0 .. 10) {
            foreach (j ; 0 .. 10) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }

    long ans;

    foreach (i ; 0 .. h) {
        auto ai = readln.split.to!(int[]);

        foreach (aij ; ai) {
            if (aij != -1) ans += d[aij][1];
        }
    }

    writeln(ans);
}



void scan(T...)(ref T args) {
    string[] line = readln.split;
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}



void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}



struct Queue(T) {
    private {
        int N, head, tail;
        T[] data;
    }

    this(int n) {
        N = n + 1;
        data = new T[](N);
    }

    bool empty() {
        return head == tail;
    }

    bool full() {
        return (tail + 1) % N == head;
    }

    T front() {
        return data[head];
    }

    void push(T x) {
        assert(!full);
        data[tail++] = x;
        tail %= N;
    }

    void pop() {
        assert(!empty);
        head = (head + 1) % N;
    }

    void clear() {
        head = tail = 0;
    }
}

Measured memory_bytes: 4092
#include <stdio.h>
#include <string.h>

int main(){
  int h,n;
  scanf("%d%d", &h, &n);
  int sum;
  for (int i = 0; i < n; i++){
    int x;
    scanf("%d", &x);
    sum += x;
  }
  if (sum >= h){
    printf("Yes\n");
  }else{
    printf("No\n");
  }
  return 0;
  
}

Measured memory_bytes: 128
using System;
using System.Collections.Generic;


namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            List<int> vs = new List<int>();
            var i =int.Parse(Console.ReadLine());
            var str = Console.ReadLine().Split();
            foreach(var s in str)
            {
                vs.Add(int.Parse(s));
            }
            vs.Sort();
            int sum = 0;
            for (int a = 0; a < i; a++)
            {
                sum += vs[2 * a];
            }
            
            Console.WriteLine(sum.ToString());
        }
    }
}


Measured memory_bytes: 11220
using System;
using System.Collections.Generic;
using System.Linq;
class ilds1_4_b{
  public static void Main(){
    int n = int.Parse(Console.ReadLine());
    int[] s = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
    int q = int.Parse(Console.ReadLine());
    int[] t = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
    int ans = 0;
    for(int i=0; i<q; i++){
      ans += bins(s,t[i],n);
    }
    Console.WriteLine(ans);
  }
  public static int bins(int[] num, int n, int size){
    int left = 0;
    int right = size;
    while(left < right){
      int mid = (right + left)/2;
      if(num[mid] == n){
        return 1;
      }
      if(num[mid] < n){
        left = mid + 1;
      }
      else{
        right = mid;
      }
    }
    return 0;
  }
}



Measured memory_bytes: 33360
# include <iostream>
# include <stdint.h>
# include <stdio.h>
# include <math.h>
using namespace std;


int main(){
	int n ,a,b,c ,d;
	cin >>n;
	for(int i =1; i <n+1;i++){
		int x[i];
		int a =i%3;
		int b =i %10;
        int c =i/10;
         x[i]= 0;
        while(c >2){
        	int d = c%10;
        	if (d ==3)
        	{
        		x[i]=3;/* code */
        	}
        	c =c/10;
        }
		if (a ==0 ||b ==3 ||x[i] ==3){
			cout <<" "<<i ;
		}
	}
	cout << endl;
return 0;
}



Measured memory_bytes: 3132
/*input
3 3
1 2 10
2 3 3
3 1 3
*/
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define F first
#define S second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define pb push_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#ifdef leowang
#define debug(...) do{\
	fprintf(stderr,"%s - %d : (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
	_DO(__VA_ARGS__);\
}while(0)
template<typename I> void _DO(I&&x){cerr<<x<<endl;}
template<typename I,typename...T> void _DO(I&&x,T&&...tail){cerr<<x<<", ";_DO(tail...);}
#else
#define debug(...)
#endif
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
	out<<'('<<P.F<<','<<P.S<<')';
	return out;
}
//}}}
const ll maxn=300005;
const ll maxlg=__lg(maxn)+2;
const ll INF64=8000000000000000000LL;
const int INF=0x3f3f3f3f;
const ll MOD=ll(1e9+7);
const double PI=acos(-1);
//const ll p=880301;
//const ll P=31;

ll mypow(ll a,ll b){
	ll res=1LL;
	while(b){
		if(b&1) res=res*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return res;
}

vector<pair<pll,ll>> edge;
vector<pll> child[maxn];
ll a[maxn];
ll tg[maxn];

bool vis[maxn];

void dfs(int u){
	vis[u]=1;
	for(auto i:child[u]) if(!vis[i.F]){
		a[i.F]=i.S-a[u];
		tg[i.F]=!tg[u];
		dfs(i.F);
	}
}

int main()
{
	//IOS;
	int n,m;
	cin>>n>>m;
	REP(i,m){
		ll u,v,d;
		cin>>u>>v>>d;
		u--;v--;
		edge.pb(MP(MP(u,v),d));
		child[u].pb(MP(v,d));
		child[v].pb(MP(u,d));
	}
	dfs(0);

	ll x;
	bool flag=0;

	for(auto i:edge){
		ll u=i.F.F,v=i.F.S,d=i.S;
		if(tg[u]==tg[v]){
			if(tg[u]){
				ll tmp=d-a[u]-a[v];
				if(tmp%2){
					cout<<"0\n";
					return 0;
				}
				if(flag){
					if(tmp/2!=x){
						cout<<"0\n";
						return 0;
					}
				}
				else{
					x=tmp/2;
					flag=1;
				}
			}
			else{
				ll tmp=a[u]+a[v]-d;
				if(tmp%2){
					cout<<"0\n";
					return 0;
				}
				if(flag){
					if(tmp/2!=x){
						cout<<"0\n";
						return 0;
					}
				}
				else{
					x=tmp/2;
					flag=1;
				}
			}
		}
		else{
			if(a[u]+a[v]!=d){
				cout<<"0\n";
				return 0;
			}
		}
	}
	if(flag){
		bool f=1;
		REP(i,n){
			if(tg[i]){
				if(x+a[i]<=0) f=0;
			}
			else{
				if(-x+a[i]<=0) f=0;
			} 
		}
		cout<<f<<'\n';
		return 0;
	}
	ll l=INF64,r=INF64;
	REP(i,n){
		if(tg[i]) l=min(l,a[i]);
		else r=min(r,a[i]);
	}
	l=1-l;
	r--;
	cout<<max(0LL,r-l+1)<<'\n';
	return 0;
}


Measured memory_bytes: 23984
import sys

stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return map(int, stdin.readline().split())
def nl(): return list(map(int, stdin.readline().split()))


def main():
    r, g, b, n = nm()
    ans = 0
    for i in range(n + 1):
        if n - i * r < 0:
            break
        for j in range(n + 1):
            num = n - r * i - g * j
            if num < 0:
                break
            if (num > 0 and num % b == 0) or num == 0:
                ans += 1
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9100
#include <iostream>
#include <map> 

#define REP(i, a, b) for ( int i = (a); i < (b); i++ )
#define REVREP(i, a, b) for ( int i = (a); i >= (b); i--)
#define DEBUG_INT(var) printf("the value of "#var" is %d\n", var)
#define PRINT_ARRAY(name, i) printf("the value of "#name"[%d] is %d\n", (i), name[(i)])
#define DEBUG_ARRAY(name, begin, end) REP(i, begin, end) PRINT_ARRAY(name, i)

using namespace std;

map<int, bool> M; 
int ans, s;

int func(int n) {
	if (n % 2 == 0) return n / 2;
	else return 3 * n + 1;
}

int solve() {
	int a = s;
    M[s] = true;

    int m = 1;

    while (1) {
    	a = func(a);
    	m++;

    	if (M[a]) return m;
    	else M[a] = true;
    }

}

int main(void) {
    scanf("%d", &s);
    
    printf("%d\n", solve());

	return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<cmath>
using namespace std;
int main(){
  unsigned long long n,k,count=0;
  
  cin >> n >> k;
  int  a[n];
  for(int i=0;i<=n-1;i++){
    cin >> a[i];
  }
  
  unsigned long long  s=0,t=0;
  for(int i=0;i<n-1;i++){
    for(int j=i+1;j<=n-1;j++){
      if(a[i]>a[j]){
        s++ ;
      }
      else if(a[i]<a[j]){
        t++ ;
      }
    }
  }

  
  count = k*(k-1)/2;
  count %= 1000000007LL;
  count *= (s+t) ;
  count %= 1000000007LL;
  count += (k*s);
  count %= 1000000007LL;
  
  cout << count;
}


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

#define fs first
#define sc second
#define pb emplace_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

signed main() {
  int h, w;
  cin >> h >> w;

  int d[10][10];
  for (int i = 0; i < 10; ++i) {
    for (int j = 0; j < 10; ++j) {
      cin >> d[i][j];
    }
  }

  for (int k = 0; k < 10; ++k) {
    for (int i = 0; i < 10; ++i) {
      for (int j = 0; j < 10; ++j) {
        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
      }
    }
  }

  long long ans = 0;
  for (int i = 0; i < h * w; ++i) {
    int n;
    cin >> n;
    if (~n) ans += d[n][1];
  }

  cout << ans << endl;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int main(int argc, char const *argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int A,B,C;
    cin >> A >> B >> C;

    if ((C - (A - B)) > 0) {
        cout << (C - (A - B)) << endl;
    }
    else {
        cout << 0 << endl;
    }
    
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include<ios>
#include <vector>
using namespace std;
using ll = long long;

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

int main(){
    ios::sync_with_stdio(false);
    int N, W;
    cin >> N >> W;
    vector<int> w(N), v(N);
    for(int i = 0; i < N; i++) {
        cin >> w[i];
        cin >> v[i];
    }
    vector<vector<ll>> dp(N+1, vector<ll>(W+1,0));
    for(int i = 0; i < N; i++) {
        for(int sum_w = 0; sum_w <= W; sum_w++) {
            if (sum_w >= w[i]) chmax(dp[i+1][sum_w], dp[i][sum_w-w[i]]+v[i]);
            chmax(dp[i+1][sum_w], dp[i][sum_w]);
        }
    }

    cout << dp[N][W] << endl;
}

Measured memory_bytes: 80256
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i <(n); ++i)
#define REP2(i,x,n) for (int i = x; i <(n); ++i)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using P = pair<int,int>;
static const double PI = acos(-1);
static const int INF = 1e9+7;
//debug 
#ifdef _DEBUG
#define debug(var)  do{cout << #var << " :";view(var);}while(0)
#else
#define debug(...)
#endif
template<typename T> void view(T e){cout << e << endl;}
template<typename T> void view(const vector<T>& v){for(const auto& e : v){ cout << e << " "; } cout << endl;}
template<typename T> void view(const vector<vector<T> >& vv){ for(const auto& v : vv){ view(v); } }


int main(){
  int n;
  cin >> n;
  string s;
  cin >> s;
  int cnt = 0;

  //左端がリーダの時，向きを変える必要がある人をcount
  REP(i,n){
    if(i == 0) continue;
    if(s[i] == 'E') cnt++;
  }
  int ans = cnt;

  //リーダを左から順にずれしていく
  REP(i,n){
    if(i == 0) continue;
    if(s[i-1] == 'W') cnt++;
    if(s[i] == 'E') cnt--;
    ans = min(ans,cnt);
  }

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

Measured memory_bytes: 3900
#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() {
    string s;
    cin >> s;
    ll ans = 0, cnt = 0;
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] == 'B') cnt++;
        else ans += cnt;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3688
n = int(input())
*arr, = map(int, input().split())
arr.sort()

cnt = 0
for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            if arr[i] != arr[j] != arr[k] and arr[i] + arr[j] > arr[k]:
                cnt += 1
print(cnt)




Measured memory_bytes: 9172