akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

#define INF 1e9
#define MAX 100005
#define xx first
#define yy second
#define pb push_back
#define mp make_pair
#define ull long long
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define nl '\n'
#define zai <<' '<<
#define all(a) a.begin(),a.end()
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;

int a[MAX];
int dp[MAX];
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n,k;
	cin >> n >> k;
	for(int i=0;i<n;i++){
		cin >> a[i];
	}
	for(int i=0;i<=100000;i++){
		dp[i]=INF;
	}
	dp[0]=0;
	dp[1]=abs(a[1]-a[0]);
	for(int i=2;i<n;i++){
		int tmp=k-1;
		for(int j=i-1;j>=0 && tmp>=0;j--){
			dp[i]=min(dp[i],dp[j]+abs(a[i]-a[j]));
			tmp--;
		}
	}
	cout << dp[n-1];
	return 0;
}

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return 
        if self.root[x] > self.root[y]:
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x 
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
    def Count(self, x): # xが属するグループのサイズを返す
        return -self.root[self.Find_Root(x)]
    def Members(self, x): # xが属するグループに属する要素をリストで返す
        return [i for i in range(self.n) if self.Find_Root(i)==self.Find_Root(x)]
    def Roots(self): # 全ての根の要素をリストで返す
        return [i for i, x in enumerate(self.root) if x < 0]
    def Group_Count(self): # グループの数を返す
        return len(self.Roots())

uf = UnionFind(n)
ps = list(map(lambda x:int(x)-1, input().split()))
for _ in range(m):
    x, y = map(lambda x:int(x)-1, input().split())
    uf.Unite(x, y)

ans = 0
for i in range(n):
    p = ps[i]
    if uf.isSameGroup(p, i):
        ans += 1

print(ans)

Measured memory_bytes: 15476
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <unordered_map>
#include <set>
#include <map>
#define INCANT cin.tie(0), cout.tie(0), ios::sync_with_stdio(0), cout << fixed << setprecision(20);
#define rep(i,n) for (int i=0; i<n;++i)
#define ALL(a)  (a).begin(),(a).end()
#define PI 3.14159265358979
typedef long long ll;
using namespace std;
const ll MOD = 1e9+7LL;
const int INF = 2e9;
int N;
map<ll, int> M;

int main() {
  INCANT;
  cin >> N;
  ll a;
  rep(i, N) {
    cin >> a;
    M[a]++;
  }
  ll b=0ll,c=0ll;

  for (auto p : M) {
    if (p.second>=2) { 
      b=c;
      c=p.first;
    }
    if (p.second>=4) b = p.first;
  } 
  cout << b*c << "\n";
  return 0;
}

Measured memory_bytes: 6528
import sys
sys.setrecursionlimit(10**6)

def dfs(v: int, p: int = -1, s: int = 0):
    dist[v] = s
    for i, j in t[v]:
        if i == p:
            continue
        dfs(i, v, s + j)

n = int(input())
t = [[] for _ in range(n)]
for _ in range(n-1):
    a, b, c = map(int, input().split())
    a -= 1; b -= 1;
    t[a].append((b, c))
    t[b].append((a, c))

q, k = map(int, input().split())
k -= 1

dist = [0]*n

dfs(k)

for _ in range(q):
    x, y = map(int, input().split())
    print(dist[x-1]+dist[y-1])



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

using namespace std;

#define all(x) x.begin(), x.end()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define reps(i, m, n) for (int i = m; i <= n; ++i)

using i64 = long long;
using pii = pair<i64, i64>;

template<class A, class B>inline bool chmax(A &a, const B &b){return b > a ? a = b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, const B &b){return b < a ? a = b,1 : 0;}

constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int MOD = int(1e9) + 7;

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

  int n;
  string s, t;
  cin >> n >> s >> t;

  int len = 2 * n;
  for (int i = 0; i < n; ++i) {
    if (s.substr(i, n-i) == t.substr(0, n-i)) {
      cout << len - (n-i) << "\n";
      return 0;
    }
  }

  cout << len << "\n";

  return 0;
}

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

using namespace std;

bool can_sum_storage[2001];

bool can_sum(const vector<int> &A, int M, int sum, int i) {
	if (can_sum_storage[M]) return true;
	if (i >= A.size()) return false;

	sum += A[i];
	if (sum <= 2000) {
		can_sum_storage[sum] = true;
	}

	return can_sum(A, M, sum, i+1) || can_sum(A, M, sum - A[i], i+1);
}

int main() {
	int n;
	cin >> n;
	vector<int> A(n);
	for (auto &Ai: A) {
		cin >> Ai;
	}

	int q;
	cin >> q;
	while (q--) {
		int M;
		cin >> M;
		if (can_sum(A, M, 0, 0)) {
			cout << "yes";
		} else {
			cout << "no";
		}
		cout << '\n';
	}
}


Measured memory_bytes: 3088
#include <bits/stdc++.h>
#define REP(i,s,e) for(int i=(s); i<(e);i++)
#define rep(i,n) REP(i,0,n)
#define rep1(i,n) REP(i,1,n)
#define repe(i,n) for(auto &&i:n)
#define all(v) (v).begin(),(v).end()
#define decimal fixed<<setprecision(20)
#define fastcin() cin.tie(0);ios::sync_with_stdio(false)
using namespace std;
using LL = long long;
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 int INF = 1e9;
const LL LLINF = 1e16;

int main(){
    fastcin();
    int n;
    cin >> n;
    vector<int>x(n), l(n);
    rep(i, n) cin >> x[i] >> l[i];
    vector<pair<int, int>> p;
    rep(i, n){
        p.emplace_back(x[i]+l[i], x[i]-l[i]);
    }
    sort(all(p));

    int ans = 0, t=-INF-10;
    rep(i, n){
        if(t <= p[i].second){
            ans++;
            t = p[i].first;
        }
    }
    cout << ans<< endl;
}

Measured memory_bytes: 2168
#include <bits/stdc++.h>
using namespace std;
#define fol(i,n) for(int i=0;i<n;i++)
#define pb push_back
typedef long long ll;
typedef pair<int,int> P;
typedef vector<P> vip;

int main(){
    int n;cin>>n;
    int C[n],S[n],F[n];
    fol(i,n-1){
        cin>>C[i]>>S[i]>>F[i];
    }
    int t=0;
    fol(i,n-1){
        t=0;
        t+=C[i]+S[i];
        for(int j=i+1;j<n-1;j++){
            if(t<=S[j]) t = C[j]+S[j];
            else{
                if ((t-S[j])%F[j]){
                    t += C[j]+F[j]-(t-S[j])%F[j];
                }else{
                    t += C[j];
                }
            }
        }
        cout << t << endl;
    }
    cout << 0 << endl;
    return 0;
}


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

int main(void){
    int N,x;
    cin>>N>>x;
    int a[100];
    int ans=0;
    for(int i=0;i<N;i++){
        cin>>a[i];
    }

    sort(a,a+N);

    for(int i=0;i<N;i++){
        if(x<0)break;
        x-=a[i];
        if(x>=0){
            ans++;
            if(i+1==N){
                if(x!=0)ans--;
            }
        }
    }
    

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

Measured memory_bytes: 256
n,m,c=map(int,input().split())
bb=list(map(int,input().split()))
x = 0
for _ in range(n):
    aa=map(int,input().split())
    s = sum(map(lambda a: a[0]*a[1], zip(aa, bb)))
    if s + c > 0:
        x += 1
print(x)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define All(V) V.begin(), V.end()
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD = 1e9+7, INF = 1e9;

int main()
{
	int a, b, c, d, k; cin >> a >> b >> c >> d >> k;
    cout << 60*(c-a)+(d-b)-k << endl;
	
    system("pause");
}


Measured memory_bytes: 3688
#include <algorithm>
#include <iostream>
#include <string>
#include <utility>
#include <vector>

int calc_gdc(int a, int b)
{
  if (a < b) std::swap(a, b);
  for (int m = a % b; m != 0; m = a % b) {
    a = b;
    b = m;
  }
  return b;
}

int solve(const std::vector<int>& array)
{
  const auto n = static_cast<int>(array.size());
  std::vector<int> vv;
  if (array[0] >= 2) vv.push_back(array[0]);
  if (array[1] >= 2) vv.push_back(array[1]);

  int current = calc_gdc(array[0], array[1]);
  for (int i = 2; i < n; ++i) {
    for (auto it = vv.begin(); it != vv.end();) {
      const auto gdc = calc_gdc(*it, array[i]);
      if (gdc == 1) {
        it = vv.erase(it);
      } else {
        *it = gdc;
        ++it;
      }
    }
    if (current >= 2) {
      if (std::find(vv.begin(), vv.end(), current) == vv.end()) {
        vv.push_back(current);
      }
      current = calc_gdc(current, array[i]);
    }
  }
  return vv.empty() ? 1 : *std::max_element(vv.begin(), vv.end());
}

int main()
{
  int n;
  std::cin >> n;

  std::vector<int> ints(n);
  for (auto& a : ints) {
    std::cin >> a;
  }

  std::cout << solve(ints) << std::endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const int iinf = 1 << 28;
const long long llinf = 1ll << 60;
const double PI = 3.14159265;

void work() {
    string s; int q; cin>>s>>q;
    vector<char> s1, s2;
    bool rev = false;
    while (q--) {
        int t; cin>>t;
        if (t == 1) {
            rev = !rev;
            continue;
        }
        int f; char c; cin>>f>>c;
        if (f == 1) {
            if (!rev) {
                s1.push_back(c);
            } else {
                s2.push_back(c);
            }
        } else {
            if (!rev) {
                s2.push_back(c);
            } else {
                s1.push_back(c);
            }
        }
    }

    if (!rev) {
        if (s1.size()) {
            for (int i = s1.size() - 1; i >= 0; --i) cout << s1[i];
        }
        cout << s;
        for (auto c : s2) cout << c;
    } else {
        if (s2.size()) {
            for (int i = s2.size() - 1; i >= 0; --i) cout << s2[i];
        }
        reverse(s.begin(), s.end());
        cout << s;
        for (auto c : s1) cout << c;
    }
    cout << endl;
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    work();
    return 0;
}


Measured memory_bytes: 976
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using vpii = vector<pair<int, int>>;
using vpll = vector<pair<ll, ll>>;

int		main(void)
{
	int A, B, C;

	cin >> A >> B >> C;
	cout << max(0, C - (A - B)) << endl;
}



Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
#include<iomanip>
#include<list>
#include<deque>
using namespace std;
//#define MODE 1
#ifdef MODE
#define DEB(X) cout<< #X <<": "<<X<<" ";
#define DEB2(X) cout<<X<<" ";
#define END cout<<endl;
#else
#define DEB(X) {}
#define DEB2(X) {}
#define END {}
#endif
typedef long long ll;
#define int ll
#define uset unordered_set
#define umap unordered_map
//typedef std::pair<int,int> P;
struct edge{int to,cost;};
const int INF=100000000000000000;
const int INF2=9223372036854775807;
const int MOD=1000000007;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define min(X,Y) (((int)(X)<(int)(Y))?(X):(Y))
#define max(X,Y) (((int)(X)>(int)(Y))?(X):(Y))
#define NP(X,Y) next_permutation(X,Y)
#define setdouble(X,Y) cout<<fixed<<setprecision(X)<<Y
int ceil2(int a,int b){if(a%b==0){return a/b;}else{return a/b+1;}}
int pow2(int a,int b){int r=1;for(int i=1;i<=b;i++){r*=a;}return r;}
int Log2(int a){int t=0;while(1){if(a==0||a==1){break;}a/=2;t++;}return t;}

int N;
string S;
set<string> U;

signed main(){
	cin>>N;
	REP(i,N){
		cin>>S;
		U.insert(S);
	}
	cout<<U.size()<<endl;
	return 0;
}


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

int main(){
  string a;
  cin>>a;
  int ans=0;
  
  for (int i=0;i<3;++i){
    if (a[i]=='1')ans+=1;
  }
  //if (a[1]=='1')ans+=1;
  //if (a[2]=='1')ans+=1;
  
  cout<<ans<<endl;
}

Measured memory_bytes: 256
sa=input()
sb=input()
sc=input()

t='a'
while True:
  if t=='a':
    if sa=='':
      print('A')
      exit()
    t=sa[0]
    sa=sa[1:]
  if t=='b':
    if sb=='':
      print('B')
      exit()
    t=sb[0]
    sb=sb[1:]
  if t=='c':
    if sc=='':
      print('C')
      exit()
    t=sc[0]
    sc=sc[1:]

Measured memory_bytes: 3064
/*

 *
 *  Created on: 2017/05/27
 *      Author: aihara
 */

#define MYDEBUG
#include <bits/stdc++.h>

#ifdef MYDEBUG
#define dbp(x) cout << "#x" << ": " << x << endl;
#else
#define dbp(x)
#endif
#define ll long long
using namespace std;

const int MAX_N = 60;
int per[MAX_N];
int main() {
	int n, p, winner, box;
	while (cin >> n >> p, n || p) {
		box = p;
		for (int i = 0; i < MAX_N; ++i) {
			per[i] = 0;
		}

		while (true) {
			bool finish = false;
			for (int i = 0; i < n; ++i) {
				if (per[i] != 0 && box == 0) {
					box = per[i];
					per[i] = 0;
				} else if (per[i] == 0 && box != 0) {
					per[i]++;
					box--;
				} else if (per[i] == 0 && box == 0) {
					continue;
				} else {
					per[i]++;
					box--;
				}
				if (per[i] == p) {
					winner = i;
					finish = true;
					break;
				}
			}
			if (finish) {
				cout << winner << endl;
				break;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 2988
#include <bits/stdc++.h>
using namespace std;
using ll=double;
//a2=b2+c2−2bccosA
int main(){
  const double PI = acos(-1);
  ll A,B,H,M; cin>>A>>B>>H>>M;
  //分そく
  ll Hs=0.5;
  ll Ms=6.0;
  ll m=H*60+M;
  ll a=Hs*m;//じのいち
  ll b=Ms*M;//ふんのいち
  ll theta=abs((a-b)/180)*PI;
  ll ans=0;
  ans=A*A+B*B-2*A*B*cos(theta);
  ans=sqrt(ans);
  cout<<fixed<<setprecision(10)<<ans<<endl;
}

Measured memory_bytes: 4224
#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <cctype>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>
#include <stdlib.h>
#include <tuple>
#include <iomanip>
#include <iterator>
#include <stdio.h>
#include <fstream>
#include <time.h>
using namespace std;
const double PI = 3.14159265358979323846;
const long long int MOD = 1000000000 + 7;

struct UnionFind {
    vector<int> parent;

    UnionFind(int N) : parent(N) {
        for (int i = 0; i < N; i++) {
            parent[i] = -1;
        }
    }

    int root(int i) {
        if (parent[i] < 0) {
            return i;
        }
        return (parent[i] = root(parent[i]));
    }

    bool unite(int from, int to) {
        int rx = root(from);
        int ry = root(to);
        if (rx != ry) {
            parent[ry] += parent[rx];
            parent[rx] = ry;

            return true;
        }
        else {
            return false;
        }
    }

    bool same(int x, int y) {
        return root(x) == root(y);
    }

    int treeSize(int x) {
        

        return -parent[root(x)];
    }
};

long long int modpow(long long int base, long long int pow, long long int mod) {
    if (pow == 1) {
        return base;
    }
    else if (pow == 0) {
        return 1;
    }

    if (pow % 2 == 0) {
        auto temp = modpow(base, pow / 2, mod);
        return (temp * temp) % mod;
    }
    else {
        return base * modpow(base, pow - 1, mod) % mod;
    }
}

long long int moddiv(long long int X, long long int Y, long long int mod) {
    auto fermatDiv = modpow(Y, mod - 2, mod);

    return (X * fermatDiv) % mod;
}

long long modCombination(long long left, long long right, long long int mod) {
    long long answer = 1;
    for (long long i = 0; i < right; i++) {
        answer = (answer * (left - i)) % mod;
        answer = moddiv(answer, (i + 1), mod);
    }

    return answer;
}

bool IsPrime(long long N) {
    if (N == 1) {
        return false;
    }
    for (long long i = 2; i * i <= N; i++) {
        if (N % i == 0) {
            return false;
        }
    }

    return true;
}



vector<pair<long long, long long> > prime_factorize(long long N) {
    vector<pair<long long, long long> > res;
    for (long long a = 2; a * a <= N; ++a) {
        if (N % a != 0) continue;
        long long ex = 0; // 指数

        // 割れる限り割り続ける
        while (N % a == 0) {
            ++ex;
            N /= a;
        }

        // その結果を push
        res.push_back({ a, ex });
    }

    // 最後に残った数について
    if (N != 1) res.push_back({ N, 1 });
    return res;
}

long long euclid(long long a, long long b) {
    if (a > b) {
        long long temp = b;
        b = a;
        a = temp;
    }
    if (b % a == 0) {
        return a;
    }
    else {
        return euclid(a, b - a);
    }
}

int main() {
    string s;
    cin >> s;
    cout << s[0] << s[1] << s[2] << endl;
    return 0;
}

Measured memory_bytes: 3600
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;


int main() {
  
  int N, M;
  
  while(cin >> N >> M && (N|M)) {
    vector<vector<double> > p(N, vector<double>(N, 0));
      
    for(int i=0; i<N; i++) for(int j=0; j<N; j++) cin >> p[i][j];
      
    vector<vector<double> > dp(M, vector<double>(N, 0));
    for(int i=0; i<N; i++) dp[0][i] = 1.0;
	
    for(int k=1; k<M; k++)
      for(int i=0; i<N; i++)
	for(int j=0; j<N; j++)
	  dp[k][i] = max(dp[k][i], dp[k-1][j]*p[j][i]);
    
    double res = 0.0;
    for(int i=0; i<N; i++) res = max(res, dp[M-1][i]);
    
    printf("%.2f\n", res);
  }  
  
  return 0;
}

Measured memory_bytes: 1356
MOD = 10**9+7
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]

DP = [1] * (N+1)

for i in A:
    DP[i] = 0

for i in range(2, N+1):
    if DP[i]:
        DP[i] = DP[i-1] + DP[i-2]
        DP[i] %= MOD

print(DP[N])


Measured memory_bytes: 7848
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
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;}


struct UnionFind{
  Int n;
  vector<Int> r,v,p;
  using P = pair<Int, Int>;
  using T = tuple<Int, Int, Int>;
  map<P, T> st;
  UnionFind(){}
  UnionFind(Int sz,vector<Int> x):n(sz),r(sz,1),v(x),p(sz,0){
    iota(p.begin(),p.end(),0);
  }
  Int find(Int x){
    return (x==p[x]?x:find(p[x]));
  }
  bool same(Int x,Int y){
    return find(x)==find(y);
  }
  void unite(Int x,Int y){
    Int a=x,b=y;
    x=find(x);y=find(y);    
    if(x==y){
      st[P(a,b)]=T(x,y,-1);
      return;
    }
    if(r[x]<r[y]) swap(x,y);
    r[x]+=r[y];
    v[x]+=v[y];
    p[y]=x;
    st[P(a,b)]=T(x,y,v[y]);
  }
  void rollback(Int a,Int b){
    assert(!st.empty());
    Int x,y,z;
    tie(x,y,z)=st[P(a,b)];
    if(z<0) return;
    r[x]-=r[y];
    v[x]-=v[y];
    p[y]=y;
  }
};

//INSERT ABOVE HERE
signed main(){
  Int n,m;
  cin>>n>>m;
  vector<Int> x(n);
  for(Int i=0;i<n;i++) cin>>x[i];

  struct edge{
    Int a,b,y;
    edge(){}
    edge(Int a,Int b,Int y):a(a),b(b),y(y){}
    bool operator<(const edge &e)const{return y<e.y;}
  };

  vector<edge> es;
  for(Int i=0;i<m;i++){
    Int a,b,y;
    cin>>a>>b>>y;
    a--;b--;
    es.emplace_back(a,b,y);
  }

  sort(es.begin(),es.end());
  UnionFind uf(n,x);
  for(auto e:es) uf.unite(e.a,e.b);

  reverse(es.begin(),es.end());
  Int ans=0;
  for(auto e:es){
    Int a=e.a,b=e.b,y=e.y;
    Int r=uf.find(a);
    if(y<=uf.v[r]) continue;
    uf.rollback(a,b);
    ans++;
  }  
  
  cout<<ans<<endl;
  return 0;
}


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

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define MOD 1000000007LL

#define rep(i, n) for(ll (i) = 0LL;(i) < (ll)(n);(i)++)
#define rep2(i, s, e) for(ll (i) = (ll)(s);(i) < (ll)(e);(i)++)
#define repi(i, n) for(ll (i) = 0LL;(i) <= (ll)(n);(i)++)
#define repi2(i, s, e) for(ll (i) = (ll)(s);(i) <= (ll)(e);(i)++)
#define per(i, n) for(ll (i) = (ll)(n) - 1LL;(i) >= 0LL;(i)--)
#define per2(i, s, e) for(ll (i) = (ll)(s) - 1LL;(i) >= (ll)(e);(i)--)
#define peri(i, n) for(ll (i) = (ll)(n);(i) >= 0LL;(i)--)
#define peri2(i, s, e) for(ll (i) = (ll)(s);(i) >= (ll)(e);(i)--)
#define iter(i, it) for(auto &(i): (it))

template<typename T, typename U> ostream& operator<<(ostream &s, const pair<T, U> m) {
    cout << "(" << m.first << ", " << m.second << ")";
    return s;
}
template<typename T, typename U> ostream& operator<<(ostream &s, const map<T, U> m) {
    ll c = 0;
    cout << "{ ";
    iter(i, m) cout << i << (c++ == m.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const vector<T> &v) {
    cout << "{ ";
    rep(i, v.size()) cout << v[i] << (i == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const list<T> &v) {
    ll c = 0;
    cout << "{ ";
    iter(i, v) cout << i << (c++ == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}

int main(void) {
    ll r, g, b;
    cin >> r >> g >> b;
    if((g * 10 + b) % 4 == 0) cout << "YES";
    else cout << "NO";
    cout << endl;
    return 0;
}


Measured memory_bytes: 3616
let () = Scanf.scanf "%d" @@ fun n ->
  let sum = ref 1 in
  let dp = Array.make (n + 1) 1 in
  let is_prime = Array.make (n + 1) true in
  for p = 2 to n do
    if is_prime.(p) then begin
      let rec outer i pp =
        if pp <= n then begin
          let rec inner j =
            if j <= n then begin
              is_prime.(j) <- false;
              dp.(j) <- dp.(j) * (1 + i) / i;
              inner (j + pp)
            end in
          inner pp; outer (i + 1) (pp * p)
        end in
      outer 1 p;
    end;
    sum := p * dp.(p) + !sum
  done;
  Printf.printf "%d\n" !sum


Measured memory_bytes: 164232
#include <bits/stdc++.h>
using namespace std;
int main() {
    string S;
    cin >> S;

    bool ans = false;
    if (S[0] != S[1] || S[1] != S[2] || S[2] != S[0]) {
        ans = true;
    }
    if (ans) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
const input=require('fs').readFileSync('/dev/stdin','utf8').split(/[\s]/);let input_i=-1;const tn=():number=>{input_i++;return Number(input[input_i])};const tnn=(n:number):number[]=>{const a=[];for(let i=0;i<n;i++){a.push(tn())}return a};const ts=():string=>{input_i++;return String(input[input_i])};const tss=(n:number):string[]=>{const a=[];for(let i=0;i<n;i++){a.push(ts())}return a};const to=(...arg)=>{console.log(...arg)};const abs=(a)=>{return Math.abs(a)};const min=(...a)=>{return Math.min(...a)};const max=(...a)=>{return Math.max(...a)};const floor=(a)=>{return Math.floor(a)};const asc=(ar:number[])=>{const t=[...ar];return ar.sort((a,b)=>{return a-b})};const desc=(ar:number[])=>{const t=[...ar];return t.sort((a,b)=>{return b-a})};const sw=(a,arr:any[],op:'=='|'>='|'>'|'<='|'<'='==')=>{for(let i=0;i<arr.length-1;i+=2){if(eval(a+op+arr[i])){return arr[i+1]}}return arr[arr.length-1]};const near=(n:number,arr:number[]):number=>{let ne=arr[0],ni=0;for(let i=1;i<arr.length;i++){if(Math.abs(n-ne)>Math.abs(n-arr[i])){ne=arr[i];ni=i}}return ni};const deduplicate=(a:any[]):any[]=>{return Array.from(new Set(a))};
const main=()=>{
  let [l,r]=tnn(2),n=2019
  if(r-l>=2019){
    to(0)
    return
  }
  l=l%n
  r=r%n
  if(r<=l){
    to(0)
    return
  }
  let m=n
  for(let i=l;i<=r;i++){
    for(let j=i+1;j<=r;j++){
      m=min(m,i*j%n)
      if(m==0)break
    }
    if(m==0)break
  }
  to(m)
}
main()


Measured memory_bytes: 10176
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

S = sys.stdin.buffer.readline().decode().rstrip()
N = len(S)

# ピッタリ払う
dp0 = [INF] * (N + 1)
# 1 多く払う
dp1 = [INF] * (N + 1)

dp0[0] = 0
dp1[0] = 1
for i, c in enumerate(S):
    dp0[i + 1] = min(dp0[i] + int(c), dp1[i] + 10 - int(c))
    dp1[i + 1] = min(dp0[i] + int(c) + 1, dp1[i] + 10 - int(c) - 1)
# print(dp0)
# print(dp1)
print(dp0[-1])


Measured memory_bytes: 128568
n = int(input())
subords = dict()

ords = [int(x) for x in input().split()]

for boss in ords:
    if boss not in subords:
        subords[boss] = 0
    subords[boss] += 1


for boss in range(1, n + 1):
    if boss in subords:
        print(subords[boss])
    else:
        print('0')


Measured memory_bytes: 33352
#include <bits/stdc++.h>
using namespace std;
int main(){
  int A,B;
  cin >> A >> B;
  int out = 1;
  int num = 0;
  while (out < B){
    out--;
    out += A;
    num++;
  }
  cout << num << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;

int main(){
int N,M;
cin>>N>>M;

vector<int>oks(N+1,true);
 for(int i=0;i<M;++i){
 int a;cin>>a;
 oks[a]=false;
 }

 vector<long long int>dp(N+1);
 dp[0]=1;
 for(int now=0;now<N;++now){
 for(int next=now+1;next<=min(N,now+2);++next){
 if(oks[next]){
 dp[next]+=dp[now];
 dp[next]%=mod;
 }
 }
 }

 cout<<dp[N]<<endl;
 return 0;
 }

Measured memory_bytes: 1408
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN = 100 + 4;
int M[MAXN][MAXN];
int main()
{
    int n, k, u, m;
    memset ( M, 0, sizeof(M) );
    cin>>n;
    for ( int i = 0; i < n; i++ ) {
        cin>>u>>k;
        for ( int j = 0; j < k; j++ ){
            cin>>m;
            M[u][m] = 1;
        }
    }

    for ( int i = 1; i <= n; i++ ) {
        for ( int j = 1; j <= n; j++ ) {
            if ( j == 1 ) cout<<M[i][j];
            else cout<<' '<<M[i][j];
        }
        cout<<endl;
    }
    return 0;
}



Measured memory_bytes: 3132
from copy import copy
N = int(input())
A = list(map(int,(input().split())))

A.insert(0,-10000000)
B = copy(A)
ans = []
bns = []

for i in range(1,N):
    if A[i] > A[i+1]:
        if A[i] >= 0 and A[i+1] >= 0:
            A[i+1] += A[i]
            ans.append([i,i+1])
        elif A[i] <= 0 and A[i+1] <= 0:
            A[i] += A[i+1]
            ans.append([i+1,i])
        else:
            if abs(A[i]) <= abs(A[i+1]):
                A[i] += A[i+1]
                ans.append([i+1,i])
                A[i] += A[i+1]
                ans.append([i+1,i])
            else:
                A[i+1] += A[i]
                ans.append([i,i+1])
                A[i+1] += A[i]
                ans.append([i,i+1])
for i in range(1,N)[::-1]:
    if A[i] > A[i+1]:
        if A[i] >= 0 and A[i+1] >= 0:
            A[i+1] += A[i]
            ans.append([i,i+1])
        elif A[i] <= 0 and A[i+1] <= 0:
            A[i] += A[i+1]
            ans.append([i+1,i])
        else:
            if abs(A[i]) <= abs(A[i+1]):
                A[i] += A[i+1]
                ans.append([i+1,i])
                A[i] += A[i+1]
                ans.append([i+1,i])
            else:
                A[i+1] += A[i]
                ans.append([i,i+1])
                A[i+1] += A[i]
                ans.append([i,i+1])

A = B
for i in range(1,N)[::-1]:
    if A[i] > A[i+1]:
        if A[i] >= 0 and A[i+1] >= 0:
            A[i+1] += A[i]
            bns.append([i,i+1])
        elif A[i] <= 0 and A[i+1] <= 0:
            A[i] += A[i+1]
            bns.append([i+1,i])
        else:
            if abs(A[i]) <= abs(A[i+1]):
                A[i] += A[i+1]
                bns.append([i+1,i])
                A[i] += A[i+1]
                bns.append([i+1,i])
            else:
                A[i+1] += A[i]
                bns.append([i,i+1])
                A[i+1] += A[i]
                bns.append([i,i+1])
for i in range(1,N):
    if A[i] > A[i+1]:
        if A[i] >= 0 and A[i+1] >= 0:
            A[i+1] += A[i]
            bns.append([i,i+1])
        elif A[i] <= 0 and A[i+1] <= 0:
            A[i] += A[i+1]
            bns.append([i+1,i])
        else:
            if abs(A[i]) <= abs(A[i+1]):
                A[i] += A[i+1]
                bns.append([i+1,i])
                A[i] += A[i+1]
                bns.append([i+1,i])
            else:
                A[i+1] += A[i]
                bns.append([i,i+1])
                A[i+1] += A[i]
                bns.append([i,i+1])

M = len(ans)
L = len(bns)
if M <= L:
    print(M)
    for i in range(M):
        print(*ans[i])
else:
    print(L)
    for i in range(L):
        print(*bns[i])

Measured memory_bytes: 38384
#![allow(non_snake_case)]
#![allow(unused_variables)]

fn iceil(x: i64, y: i64) -> i64 {
    (x + y - 1) / y
}

fn f(b: i64, n: i64) -> i64 {
    if n < b {
        n
    } else {
        f(b, n / b) + n % b
    }
}

fn bis<P>(ok: i64, ng: i64, p: P) -> i64
    where P : Fn(i64) -> bool {
    let mid = (ok + ng) / 2;
    if (ok - ng).abs() == 1 {
        ok
    } else if p(mid) {
        bis(mid, ng, p)
    } else {
        bis(ok, mid, p)
    }
}

fn main() {
    let n: i64 = {
        let mut line: String = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        line.trim().parse().unwrap()
    };
    let s: i64 = {
        let mut line: String = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        line.trim().parse().unwrap()
    };

    // 2以上sqrt(n)以下で該当するbがあればそれが解
    // そうでなければnをb進表記すると2桁なので、上位桁について全探索すればよい
    let ans = if s > n || (iceil(n, 2) < s && s < n) {
        -1
    } else if s == n {
        n + 1
    } else {
        let sqn = bis(1_000_000_000, 0, |x| x * x > n);
        let b = (2..sqn).find(|&i| f(i, n) == s);
        match b {
            Some(c) => c,
            None => {
                let j = (1..sqn).rev().find(|&i| (f((n - s + i) / i, n) == s)).unwrap();
                (n - s + j) / j
            }
        }
    };

    println!("{}", ans);
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
const int N = 109;
int n, m, q, cnt, A[N], B[N];
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++)
		scanf("%d", &A[i]), cnt += (A[i] & 1);
	if (cnt > 2)
		return !printf("Impossible\n");
	if (n == 1)
		return !printf("%d\n1\n1\n", A[1]);
	if (m == 1)
		return !printf("%d\n2\n%d %d\n", A[1], A[1] - 1, 1);
	for (int i = 1; i <= m; i++)
		if (A[i] & 1)
			swap(A[i], A[1]);
	for (int i = 2; i <= m; i++)
		if (A[i] & 1)
			swap(A[i], A[m]);
	for (int i = 1; i <= m; i++)
		printf("%d ", A[i]);
	printf("\n");
	if (A[1] > 1)
		B[++ q] = A[1] - 1;
	for (int i = 2; i < m; i++)
		B[++ q] = A[i];
	B[++ q] = A[m] + 1;
	printf("%d\n", q);
	for (int i = 1; i <= q; i++)
		printf("%d ", B[i]);
	printf("\n");
	return 0;
}

Measured memory_bytes: 764
import math

n,a,b = [int(x) for x in input().split(' ')]

if a == 0:
    print(0)

elif a >= n:
    print(n)

else:
    num_a = (n // (a+b)) * a
    left_repeated = (n % (a+b))
    print(num_a + min(left_repeated, a))


Measured memory_bytes: 3060
#include <iostream>

using namespace std;

int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    if (i % 3 == 0) cout << " " << i;
    else {
      int x = i;
      while (x) {
        if (x%10 == 3) {
          cout << " " << i;
          break;
        }
        x /= 10;
      }
    }
  }
  cout << endl;
  return 0;
}

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

char p[62][62];
bool done[62][62];
bool done2[62][62];
double mi,mx;
double xsum = 0;
int c = 0;
char color;
int parent[62];

void dfs2(int x,int y,int color){
	if( p[y][x] != color ) return;
	if( done2[y][x] ) return;
	done2[y][x] = true;
	xsum += x;
	c++;
	dfs2(x+1,y,color);
	dfs2(x-1,y,color);
	dfs2(x,y+1,color);
	if( p[y-1][x] != '.' )
		dfs2(x,y-1,p[y-1][x]);
}
void dfs(int x,int y){
	if( p[y][x] != color ) return;
	if( done[y][x] ) return;
	done[y][x] = true;
	if( p[y+1][x] != color && p[y+1][x] != '.' ){
		mi = min(mi,x-0.5);
		mx = max(mx,x+0.5);
	}
	dfs(x+1,y);
	dfs(x-1,y);
	dfs(x,y+1);
	dfs(x,y-1);
}
int main(){
	int w,h;
	while(	cin >> w >> h && w){
		memset(done,0,sizeof(done));
		for(int i = 0 ; i < 62 ; i++)
			for(int j = 0 ; j < 62 ; j++)
				p[i][j] = '.';
		for(int i = 0 ; i < 62 ; i++)
			p[h+1][i] = '#';
		for(int i = 1 ; i <= h ; i++){
			for(int j = 1 ; j <= w ; j++){
				cin >> p[i][j];
			}
		}
		int flag = 0;
		for(int i = 1 ; i <= h ; i++){
			for(int j = 1 ; j <= w ; j++){
				if( p[i][j] != '.' && !done[i][j] ){
					mi = 1e9;
					mx = -1e9;
					c = 0;
					xsum = 0;
					color = p[i][j];
					dfs(j,i);
					memset(done2,0,sizeof(done2));
					dfs2(j,i,color);
					//cout << xsum / c << "(" << mi << " " << mx << ")" << endl;
					if( mi + 1e-9 < xsum / c && xsum / c < mx - 1e-9 ){
						
					}else{
						flag++;
					}
				}
			}
		}
		if(flag) cout << "UNSTABLE" << endl;
		else cout << "STABLE" << endl;
		
	}
}

Measured memory_bytes: 1164
n = int(input())
a, b = map(int, input().split())
p = list(map(int, input().split()))

x = 0
y = 0
z = 0
for i in range(n):
    if p[i] <= a: 
        x += 1
    if a + 1 <= p[i] <= b:
        y += 1
    if b + 1 <= p[i]:
        z += 1

print(min((x, y, z)))

Measured memory_bytes: 38356
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <numeric>

using namespace std;


int main()
{
    int n;
    string s, t;
    cin >> n;
    cin >> s >> t;

    for(int i = 0;i < n;i++)
    {
        cout << s[i] << t[i];
    }
    cout << endl;

    return 0;
}


Measured memory_bytes: 256
/*
  AtCoder Beginner Contest 104
  B - AcCepted
*/

#include<iostream>
using namespace std;

string S;

int main() {
  cin >> S;

  int cnt = -1;
  bool check = true;

  if (S[0] == 'A') {
    cnt = 0;
    for (int i = 2; i < S.length() - 1; ++i) {
      if (S[i] == 'C') cnt += 1;
    }
  }

  for (int i = 1; i < S.length(); ++i) {
    if (!('a' <= S[i] && S[i] <= 'z')) {
      if (!(S[i] == 'C' && 2 <= i && i <= S.length() - 2)) check = false;
    }
  }
 
  if (check && cnt == 1) printf("AC\n");
  else printf("WA\n");
  return 0;
}


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

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<vector<ll>>> vvvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<vector<vector<bool>>> vvvb;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
typedef vector<double> vd;
typedef vector<vd> vdd;

#define FOR(i,x,y) for(ll i=(ll)x; i<(ll)y; ++i)
#define REP(i,y) FOR(i, 0, y)
#define RFOR(i,x,y) for(ll i=(ll)x; i>=(ll)y; --i)
#define RREP(i,x) RFOR(i, x, 0)
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define debug_print(x...) cerr << "line " << __LINE__ << " : "; debug_print_in(x);

template <typename First>
void debug_print_in(First first){
  cerr << first << endl;
  return;
}

template <typename First, typename... Rest>
void debug_print_in(First first, Rest... rest){
  cerr << first << " ";
  debug_print_in(rest...);
  return;
}

void IN(void){
  return;
}

template <typename First, typename... Rest>
void IN(First& first, Rest&... rest){
  cin >> first;
  IN(rest...);
  return;
}

template <typename First>
void OUT(First first){
  cout << first << endl;
  return;
}

template <typename First, typename... Rest>
void OUT(First first, Rest... rest){
  cout << first << " ";
  OUT(rest...);
  return;
}

template<class t, class u> void chmax(t&a,u b){if(a<b)a=b;};
template<class t, class u> void chmin(t&a,u b){if(a>b)a=b;};
int popcount(int t){return __builtin_popcount(t);} //GCC
int popcount(ll t){return __builtin_popcountll(t);} //GCC

template <typename T>
void vec_print(vector<T> VEC){
  REP(i, VEC.size()){
    cerr << VEC[i] << " ";
  }
  cerr << endl;
};

template <typename T>
void mat_print(vector<vector<T> > MAT){
  REP(i,MAT.size()){
    REP(j,MAT[i].size()){
      cerr << MAT[i][j] << " ";
    }
    cerr << endl;
  }
};

constexpr int INF = (1<<30);
constexpr ll INFLL = 1LL<<62;
constexpr long double EPS = 1e-12;
constexpr ll MOD = (ll)((1E+9)+7);

string S;
ll N;
vll dp;

int main(){
  cin.tie(0); // cut the cin and cout (default, std::flush is performed after std::cin)
  ios::sync_with_stdio(false); // cut the iostream and stdio (DON'T endl; BUT "\n";)

  IN(S);
  N = S.size();
  dp.resize(2019, 0);

  reverse(ALL(S));
  ll shift = 1;
  dp[0] = 1;
  ll ans = 0;
  ll tmp = 0;
  REP(i,N){
    ll val = S[i]-'0';
    val *= shift;
    val %= 2019;
    val += tmp;
    val %= 2019;
    ans += dp[val];
    dp[val]++;
    //debug_print(val, (2019-val)%2019, ans);
    shift *= 10;
    shift %= 2019;
    tmp = val;
  }

  OUT(ans);

  return 0;
}


Measured memory_bytes: 3732
N,K = map(int, input().split())
mod = 10**9+7
ans = (((2*K-1)*(K-1)%mod*K%mod - (2*N+3)*(N+2)%mod*(N+1)%mod \
     + 3*(N+1)*(N+1)%mod*(N+2)%mod - 3*(N+1)*K%mod*(K-1)%mod)*pow(6,mod-2,mod) \
     + (N-K+2))%mod
# ans = (((2*K-1)*(K-1)%mod*K%mod - (2*N+3)*(N+2)%mod*(N+1)%mod \
#      + 3*(N+1)*(N+1)%mod*(N+2)%mod - 3*(N+1)*K%mod*(K-1)%mod)/6 \
#      + (N-K+2))%mod

print(int(ans))

Measured memory_bytes: 9196
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc=new Scanner(System.in);
		
		int s=sc.nextInt();		//羊の数
		int w=sc.nextInt();		//狼の数
		
		if(s<=w) {
			System.out.println("unsafe");
		} else {
			System.out.println("safe");
		}

		sc.close();

	}

}


Measured memory_bytes: 27076
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <climits>
#include <iomanip>
using namespace std;
typedef long long ll;
int main(){
  ll n;
  cin >> n;
  vector<ll> a(n);
  vector<ll> b(n);
  for(int i = 0;i < n;i++)cin >> a[i];
  for(int i = 0;i < n;i++)cin >> b[i];
  ll res = 0;
  vector<int> add;
  ll tarinai = 0;
  for(int i = 0;i < n;i++){
    if(a[i] > b[i])add.push_back(a[i] - b[i]);
    else if(a[i] < b[i])res++,tarinai += b[i] - a[i];
  }
  sort(add.begin(),add.end());
  for(int i = add.size() - 1;i >= 0;i--){
    if(tarinai > 0)tarinai -= add[i],res++;
    else break;
  }
  if(tarinai > 0)res = -1;
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 2176
import math

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

motoa = a/0.08

motob = b/0.1
a += 1
b += 1
xmotoa = a/0.08
xmotob = b/0.1

if motoa < motob <xmotoa:
    print(math.ceil(motob))
elif motoa < xmotob <xmotoa:
    print(math.ceil(motoa))
else:
    print('-1')

Measured memory_bytes: 3060
package main

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

var sc = bufio.NewScanner(os.Stdin)
func scanInt() int {
	sc.Scan()
	a,_ := strconv.Atoi(sc.Text())
	return a
}

func scanText() string {
	sc.Scan()
	return sc.Text()
}

func min(a,b int) int {
	if a<b {
		return a
	}
	return b
}

func main() {
	sc.Split(bufio.ScanWords)
	
	n := scanInt()
	b := make([]int, n-1)

	for i := 0; i < n-1; i++ {
		b[i] = scanInt()
	}
	
	ans := 0
	pre := b[0]

	for i := 1; i < n; i++ {
		ans += min(pre,b[i-1])
		pre = b[i-1]
	}
	
	fmt.Println(ans+pre)
}


Measured memory_bytes: 640
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")


def main():
    S = input()[:-1]
    tmp = "hi"
    for _ in range(len(S)):
        if S == tmp:
            print("Yes")
            return
        tmp += "hi"
        if len(tmp) > len(S):
            break
    print("No")


if __name__ == '__main__':
    main()

Measured memory_bytes: 66156
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr long double EPS = 1e-15;
const long double PI = acos(-1);
constexpr int inf = 1e9;
constexpr ll INF = 2e18;
constexpr ll MOD = 1e9+7;
constexpr ll MOD1 = 998244353;
typedef pair<ll,ll> P;
//#define all(v) (v).begin(), (v).end()
#define rep(i,a,b) for (int i = (a); i < (b); i++)
#define REP(i,n) rep(i,0,n)
#define sz(s) (s).size()
#define pb push_back
#define fi first
#define se second
//#define mp make_pair

ll n,m,p;
ll from[6000],to[6000],cost[6000];
vector<ll> G[3000],R[3000];

void input() {
    cin >> n >> m >> p;
    REP(i,m) {
        cin >> from[i] >> to[i] >> cost[i];
        from[i]--;
        to[i]--;
        cost[i] -= p;
        G[from[i]].pb(to[i]);
        R[to[i]].pb(from[i]);
    }
}

bool from0[3000], fromn[3000];

void dfs0(int k) {
    if (from0[k]) return;
    from0[k] = 1;
    for (int i = 0; i < G[k].size(); i++) {
        dfs0(G[k][i]);
    }
}

void dfsn(int k) {
    if (fromn[k]) return;
    fromn[k] = 1;
    for (int i = 0; i < R[k].size(); i++) {
        dfsn(R[k][i]);
    }
}

ll d[3000];

void solve() {
    // from0[0] = 1;
    // fromn[n - 1] = 1;
    // for (int i = 0; i < n; i++) {
    //     for (int j = 0; j < m; j++) {
    //         if (from0[from[j]]) from0[to[j]] = 1;
    //         if (fromn[to[j]]) fromn[from[j]] = 1;
    //     }
    // }
    dfs0(0);
    dfsn(n-1);

    REP(i,n) d[i] = -INF;
    d[0] = 0;
    ll ma = -INF;
    for (int i = 0; i <= 2 * n; i++) {
        ll pre[3000];
        for (int j = 0; j < n; j++) {
            pre[j] = d[j];
        }
        for (int j = 0; j < m; j++) {
            d[to[j]] = max(d[to[j]], d[from[j]] + cost[j]);
        }
        bool f = 0;
        for (int j = 0; j < n; j++) {
            if (pre[j] != d[j] && from0[j] && fromn[j]) f = 1;
        }
        if (!f) break;
        if (i == 2 * n) {
            cout << -1 << endl;
            return;
        }
        ma = max(ma, d[n - 1]);
    }
    cout << max(ma,0LL) << endl;
}

int main(int argc, char *argv[]){
    input();
    solve();
    return 0;
}


Measured memory_bytes: 768
from collections import*
class UnionFind():
    def __init__(self,size):
        self.table=[-1]*size
    def root(self,x):
        while self.table[x]>=0:
            x=self.table[x]
        return x
    def unite(self,x,y):
        s1=self.root(x)
        s2=self.root(y)
        if s1!=s2:
            if self.table[s1]>self.table[s2]:
                s1,s2=s2,s1
            self.table[s1]+=self.table[s2]
            self.table[s2]=s1
        return
    def same(self,x,y):
        return self.root(x)==self.root(y)
    def size(self,x):
        return -self.table[self.root(x)]
input=open(0).readline
n,k,l=map(int,input().split())
u=UnionFind(n)
v=UnionFind(n)
for _ in range(k):
    p,q=map(int,input().split())
    u.unite(p-1,q-1)
for _ in range(l):
    r,s=map(int,input().split())
    v.unite(r-1,s-1)
d=defaultdict(int)
a=[]
for i in range(n):
    t=(u.root(i),v.root(i))
    d[t]+=1
    a.append(t)
print(*[d[i]for i in a])

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

int main(){
  string s,t;
  bool count = true;
  cin >> s >> t;
  for(int i = 0;i < s.size();i++){
    if(s[i] != t[i]){
      count = false;
      break;
    }
  }
  if(s.size() + 1 != t.size())
    count = false;
  if(count == true)
    cout << "Yes\n";
  else
    cout << "No\n";
  return 0;
}


Measured memory_bytes: 3640
# import sys
# import math
# import decimal
# import queue
# import bisect
# import heapq # priolity-queue
# import time
# import itertools
# import collections # queue
# from operator import itemgetter
# from fractions import Fraction

mod = int(1e9+7)
INF = 1<<29
lINF = 1<<35

def main():
    n,k = map(int,input().split())
    a = []
    for i in range(n):
        a.append(list(map(int,input().split())))
    a.sort()
    cnt = 0
    for i in range(n):
        cnt += a[i][1]
        if cnt>=k:
            print(a[i][0])
            break
    return

if __name__=='__main__':
    main()


Measured memory_bytes: 27872
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll=long long;
using vi = vector<int>;
using vl = vector<ll>;
using Graph = vector<vi>;
using P = pair<int,int>;
const int MOD=(int)1e9+7;
const int INF=(int)1e9;
const ll LINF=(ll)1e18;
template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}

int main(){
    int k,s;
    cin >> k >> s;
    int cnt = 0;
    for(int x=0;x<=s && x <= k;x++){
        for(int y=0;y<=s && y<=k;y++){
            int z = s - x - y;
            if(z>=0 && z<=k) cnt++;
        }
    }
    cout << cnt << endl;
}

Measured memory_bytes: 256
/*
Author:Fuad Ashraful Mehmet
University of Asia Pacific
Date:23 Feb 2020
*/
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N=1e5+5;
int n;

int main()
{
 ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    
    bool flag=false;
    string s;cin>>s;
    for(int i=0;i<2;++i)
    {
        if(s[i]!=s[i+1])flag=true;
    }

    flag==true?cout<<"Yes"<<endl:cout<<"No"<<endl;
 return 0;
}

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

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

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

  int n, d; cin >> n >> d;
  int tmp = 2*d+1;

  cout << (n+tmp-1)/tmp << '\n';
  return 0;
}


Measured memory_bytes: 256
import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception {

		int a = 0;
		int b = 0;
		int c = 0;

		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
			String line;
			while ((line = br.readLine()) != null) {
				String[] tokens = line.split(" ");
				a = Integer.parseInt(tokens[0]);
				b = Integer.parseInt(tokens[1]);
				c = Integer.parseInt(tokens[2]);
			}
		}

		List<Integer> aList = new ArrayList();
		List<Integer> bList = new ArrayList();
		List<Integer> cList = new ArrayList();

		aList.add(a);
		bList.add(b);
		cList.add(c);

		int count = 0;
		while(true) {

			if (a % 2 == 1 || b % 2 == 1 || c % 2 == 1) {
				break;
			}

			int a2 = (b / 2) + (c / 2);
			int b2 = (a / 2) + (c / 2);
			int c2 = (a / 2) + (b / 2);

			a = a2;
			b = b2;
			c = c2;

			int l = aList.size();
			for (int i = 0; i < l; i++) {
				if (aList.get(i) != a) {
					continue;
				}
				if (bList.get(i) != b) {
					continue;
				}
				if (cList.get(i) != c) {
					continue;
				}

				count = -1;
			}

			if (count != -1) {
				count++;
			} else {
				break;
			}

			aList.add(a);
			bList.add(b);
			cList.add(c);
		}

		System.out.println(count);
	}
}

Measured memory_bytes: 20436
using System;
using static System.Console;
using System.Linq;

namespace AC
{
   public class shiokara
   {
      static void Main(string[] args)
      {
         string alpha = ReadLine();
         for(char i = 'a'; i <= 'z'; i++){
             if(alpha[0] == i){
                 WriteLine("a");
                 return;
             }
         }
         WriteLine("A");
      }
   }
}

Measured memory_bytes: 25880
#include<iostream>
#include<vector>
using namespace std;
int choco(vector<int> a,int i,int d){
	int ret=0;
	do{
		ret++;
	} while (ret*a.at(i)+1<=d);
	return ret;

}
int main() {
	int n, d,x, sum = 0;
	cin >> n>>d>>x;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a.at(i);
	}
	for (int i = 0; i < n; i++) {
		sum += choco(a,i,d);
	}
	cout << sum+x;
}

Measured memory_bytes: 3572
#include<iostream>
#define END "\n"
#define REP(i, a, b) for (int i = a; i < b; ++i)

using namespace std;  

int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    if (n >= 30) cout << "Yes";
    else cout << "No";
    return 0;
}


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

int main() {
	int n; cin >> n;
	int a[n], even = 0;
	for(int i = 0; i < n; i++) {
		cin >> a[i];
		if(a[i] % 2 == 0) even++;
	}

	long long fodd = pow(2, even);
	cout << pow(3, n) - fodd << endl;
	return 0;
}


Measured memory_bytes: 256
import sys

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr

def main():
    A, B = map(int, input().split())

    pf_A = factorization(A)
    pf_B = factorization(B)

    if pf_A[0][0] == 1 or pf_B[0][0] == 1:
        pfs = []
    else:
        pfs = set([i for i,num in pf_A]) & set([i for i,num in pf_B])

    print(len(pfs)+1)
main()

Measured memory_bytes: 63356
import numpy as np
import sys

n = int(input())
arr = np.array(list(map(int, input().split())))

arr.sort()
arr_cs = arr.cumsum()

ans = 0
for i in range(n - 1):
    if arr_cs[i] * 2 < arr[i + 1]:
        ans = i + 1
else:
    print(n - ans)

Measured memory_bytes: 23116