akhauriyash/Code-Regression huggingface dataset:
def main():
    import sys
    input = sys.stdin.readline
    
    N = int(input())
    A = []
    tmp = (0,)*(N+1)
    A.append(tmp)
    for i in range(N):
        tmp = (0,) + tuple(map(int, input().split()))
        A.append(tmp)
    B = [1]*(N+1)
    C = [[0]*N for i in range(N+1)]
    count = 0
    flag = 0
    
    #1試合目
    Q = []
    nextQ = []
    for i in range(1,N+1):
        j = A[i][B[i]]
        if A[j][B[j]] == i:
            ii = min(i,j)
            jj = max(i,j)
            if not (ii,jj) in nextQ:
                nextQ.append((ii,jj))
    
    day = 0    
    while count < N*(N-1)//2 and len(nextQ) >= 1:
        day += 1
        Q = nextQ
        nextQ = []
        for T in Q:
            i = T[0]
            j = T[1]
            k = max(C[i][B[i]-1], C[j][B[j]-1]) + 1
            C[i][B[i]] = k
            C[j][B[j]] = k
            B[i] += 1
            B[j] += 1
            count += 1
            if B[i] < N:
                I = A[i][B[i]]
                if A[I][B[I]] == i:
                    ii = min(i,I)
                    jj = max(i,I)
                    if not (ii,jj) in nextQ:
                        nextQ.append((ii,jj))
            if B[j] < N:
                J = A[j][B[j]]
                if A[J][B[J]] == j:
                    ii = min(j,J)
                    jj = max(j,J)
                    if not (ii,jj) in nextQ:
                        nextQ.append((ii,jj))
            
                    
    #print(C)
    if count < N*(N-1)//2:
        print(-1)
    else:
        print(day)
    
    
    
if __name__ == '__main__':
    main()

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

int main()
{
    string S, T;
    cin >> S;
    cin >> T;
    int count = 0;
    for(int i = 0; i < 3; i++) {
        if(S[i] == T[i]) {
            count += 1;
        }
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 3600
#include <stdio.h>

int main(void)
{
	int day, a, b, c, d;
	int j, m;
	
	scanf("%d %d %d %d %d", &day, &a, &b, &c, &d);
	
	j = a / c;
	if (a % c != 0){
		j++;
	}
	
	m = b / d;
	if (b % d != 0){
		m++;
	}
	
	if (j > m){
		printf("%d\n", day - j);
	}
	else {
		printf("%d\n", day - m);
	}
	return (0);
}

Measured memory_bytes: 596
#include <iostream>
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <cctype>
#include <string>
#include <map>
#include <set>
#include <math.h>
#include <cmath>
#define ll long long
#define lli long long int

using namespace std;
using P = pair<int,int>;

int main(){

  int N, b;
  cin >> N;
  int ans = 0;
  vector<int> vecA(N);
  vector<int> vecB(N-1);

  for (int i = 0; i < N-1; i++){
    cin >> b;
    vecB.at(i) = b;
  }

  for (int i = 0; i < N-1; i++){
    if(i == 0){
      vecA.at(i) = vecB.at(i);
      vecA.at(i+1) = vecB.at(i);
      continue;
    }

    if(vecA.at(i) > vecB.at(i)) vecA.at(i) = vecB.at(i);
    vecA.at(i+1) = vecB.at(i);
  }

  ans = accumulate(vecA.begin(), vecA.end(), 0);

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3568
#include <iostream>
using namespace std;
typedef long long ll;
int main() {
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    ll result = a*c;
    if (result < a*d) {
        result = a*d;
    } 
    if (result < b*c) {
        result = b*c;
    }
    if (result < b*d) {
        result = b*d;
    }
    cout << result << endl;
}

Measured memory_bytes: 3636
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

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

#define DEBUG

#ifdef DEBUG
#define var_dump(...) fprintf(stdout, __VA_ARGS__)
#define dump(a) cout << a << "\n";
#else
#define var_dump(...) 42
#define dump(a) 42
#endif

typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

int dy4[]={0, 0, 1, -1};
int dx4[]={1, -1, 0, 0};
int dx8[]={0, 0, 1, -1, 1, 1, -1, -1};
int dy8[]={1, -1, 0, 0, 1, -1, -1, 1};

// https://beta.atcoder.jp/contests/abc086/tasks/abc086_b

int main() {

    string a, b; cin >> a >> b;
    ll ab = stoi(a+b);

    REP(i, 10005) {
        if (ab == i*i) {
            cout << "Yes" << "\n";
            return 0;
        }
    }

    cout << "No" << "\n";

    return 0;
}


Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0;i < (n);i++)
#define all(v) v.begin(),v.end()
#define dec(n) cout << fixed << setprecision(n);
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;

ll gcd(ll a,ll b){
  if(b == 0) return a;
  return gcd(b , a % b);
}

ll mod(ll a){
  return (a % 1000000007);
}

ll lcm(ll a,ll b){
  return (a*b)/gcd(a,b);
}


int main(){
  ll h,w,a,b; cin >> h >> w >> a >> b;
  
  vvl table(h,vl(w));
  
  rep(i,h){
    rep(j,w){
      if((i < b and j < a) or (i >= b and j >= a)){
        table[i][j] = 1;
      }
      else table[i][j] = 0;
    }
  }
  
  for(auto array : table){
    for(ll x : array){
      cout << x ;
    }
    cout << endl;
  }
  
  
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF 1e16
#define mod 1000000007

ll n;
ll a[1001];
vector<P> b[2];
ll res[2];
vector<ll> idxs[2];
vector<ll> c;
vector<ll> ans;

int main(){
  cin>>n;
  rep(i,n)cin>>a[i];
  rep(i,n){
    if(i%2==0){
      b[0].push_back(P(a[i],i));
    }else{
      b[1].push_back(P(a[i],i));
    }
  }

  if(b[0].size()>0){
    sort(all(b[0]));
    reverse(all(b[0]));
    res[0]=b[0][0].fi;
    idxs[0].push_back(b[0][0].se);
    repl(i,1,b[0].size()){
      if(b[0][i].fi>0){
        res[0]+=b[0][i].fi;
        idxs[0].push_back(b[0][i].se);
      }
    }
  }
  if(b[1].size()>0){
    sort(all(b[1]));
    reverse(all(b[1]));
    res[1]=b[1][0].fi;
    idxs[1].push_back(b[1][0].se);
    repl(i,1,b[1].size()){
      if(b[1][i].fi>0){
        res[1]+=b[1][i].fi;
        idxs[1].push_back(b[1][i].se);
      }
    }
  }

  rep(i,n)c.push_back(i);

  if(res[0]>res[1]){
    sort(all(idxs[0]));
    while(*c.begin()!=*idxs[0].begin()){
      ans.push_back(0);
      c.erase(c.begin()+0);
    }
    while(*c.rbegin()!=*idxs[0].rbegin()){
      ans.push_back(c.size()-1);
      c.erase(c.begin()+c.size()-1);
    }
    rep(i,idxs[0].size()-1){
      ll nxt=idxs[0][i+1];
      while(c[2]!=nxt){
        ans.push_back(2);
        c.erase(c.begin()+3); c.erase(c.begin()+1);
      }
      ans.push_back(1);
      c.erase(c.begin()+2); c.erase(c.begin()+0);
    }
    cout<<res[0]<<endl;
  }else{
    sort(all(idxs[1]));
    while(*c.begin()!=*idxs[1].begin()){
      ans.push_back(0);
      c.erase(c.begin()+0);
    }
    while(*c.rbegin()!=*idxs[1].rbegin()){
      ans.push_back(c.size()-1);
      c.erase(c.begin()+c.size()-1);
    }
    rep(i,idxs[1].size()-1){
      ll nxt=idxs[1][i+1];
      while(c[2]!=nxt){
        ans.push_back(2);
        c.erase(c.begin()+3); c.erase(c.begin()+1);
      }
      ans.push_back(1);
      c.erase(c.begin()+2); c.erase(c.begin()+0);
    }
    cout<<res[1]<<endl;
  }
  cout<<ans.size()<<endl;
  rep(i,ans.size())cout<<ans[i]+1<<endl;
  return 0;
}


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

const int N = 300000;

const long double PI = acos(-1.0);
struct Complex{
    long double x, y;
    void operator+=(const Complex &b){ x += b.x; y += b.y; }
    Complex operator-(const Complex &b) const{ return {x - b.x, y - b.y}; }
    Complex operator*(const Complex &b) const
    { return {x * b.x - y * b.y, x * b.y + y * b.x}; }
};

template<int N> struct Fast_Fourier_Transform{
    Complex W[N*4+5];
    void init(int n){
        Complex Wn = {cos(2*PI/n), sin(2*PI/n)}; W[0] = {1.0, 0.0};
        for (int i = 1; i < n>>1; ++i) W[i] = W[i-1] * Wn;
        for (int i = 0, j = n>>1; j < n; ++i, ++j) W[j] = {W[i].x, -W[i].y};
    }
    void init2(int n){
        for (int i = 0; i < n>>1; ++i) W[i] = {cos(i*2*PI/n), sin(i*2*PI/n)};
        for (int i = 0, j = n>>1; j < n; ++i, ++j) W[j] = {W[i].x, -W[i].y};
    }
    void go(Complex A[], int n, int opt){
        int _n = n>>1, kbg = (~opt ? 0 : _n), ked = kbg + _n;
        for (int i = 0, j = 0; i < n; ++i){
            if (i < j) swap(A[i], A[j]);
            for (int k = _n; (j^=k) < k; k >>= 1);
        }
        for (int len = 1, dk = _n; len <= _n; len <<= 1, dk >>= 1)
            for (int i = 0, j = len; i < n; i += len, j += len)
                for (int k = kbg; k < ked; ++i, ++j, k += dk){
                    Complex X = W[k] * A[j]; A[j] = A[i] - X; A[i] += X;
                }
        if (opt == -1) for (int i = 0; i < n; ++i) A[i].x /= n;
    }
};

Fast_Fourier_Transform<N> fft;

template<typename FFT, FFT &fft> struct Poly_Mul{
    Complex za[N*4+5], zb[N*4+5];
    template <typename T>
    void poly_mul(T a[], int an, T b[], int bn, T res[], int &rn){
        for (rn = 1; rn < an+bn-1; rn <<= 1); fft.init(rn);
        for (int i = 0; i < an; ++i) za[i] = {a[i], 0.0};
        for (int i = an; i < rn; ++i) za[i] = {0.0, 0.0};
        for (int i = 0; i < bn; ++i) zb[i] = {b[i], 0.0};
        for (int i = bn; i < rn; ++i) zb[i] = {0.0, 0.0};
        fft.go(za, rn, 1); fft.go(zb, rn, 1);
        for (int i = 0; i < rn; ++i) za[i] = za[i] * zb[i];
        fft.go(za, rn, -1);
        for (int i = 0; i < an+bn-1; ++i) res[i] = za[i].x + 0.5;
    }
};

Poly_Mul<decltype(fft), fft> poly_mul;

int h[N+5], w[N+5], cntH[N+5], cntW[N+5];

long long a[N*4+5], b[N*4+5], c[N*4+5];

int main(){
    int H, W, M;
    scanf("%d %d %d", &H, &W, &M);
    for (int i = 1; i <= M; ++i){
        scanf("%d %d", h+i, w+i);
        ++cntH[h[i]];
        ++cntW[w[i]];
    }
    for (int i = 1; i <= N; ++i){
        ++a[cntH[i]];
    }
    for (int i = 1; i <= N; ++i){
        ++b[cntW[i]];
    }
    int tot;
    poly_mul.poly_mul(a, N + 1, b, N + 1, c, tot);
    for (int i = 1; i <= M; ++i){
        int sum = cntH[h[i]] + cntW[w[i]];
        --c[sum]; ++c[sum - 1];
    }
    for (int i = tot; i >= 0; --i){
        if (c[i]){
            printf("%d\n", i);
            break;
        }
    }
    return 0;
}


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

int main() {
  int a1,a2,a3,a4,b1,b2,b3,b4,atot,btot;
  cin >> a1 >> a2 >> a3 >> a4 >> b1 >> b2 >> b3 >> b4;
  atot = a1 + a2 + a3 + a4;
  btot = b1 + b2 + b3 + b4;
  if( atot > btot)
    cout << atot << endl;
  else
    cout << btot << endl;
}

Measured memory_bytes: 0
def main():  
  #Union Find

  #xの根を求める
  def find(x):
      if par[x] < 0:
          return x
      else:
          par[x] = find(par[x])
          return par[x]
  #xとyの属する集合の併合
  def unite(x,y):
      x = find(x)
      y = find(y)

      if x == y:
          return False
      else:
          #sizeの大きいほうがx
          if par[x] > par[y]:
              x,y = y,x
          par[x] += par[y]
          par[y] = x
          return True

  def find2(x):
    if pa[x] < 0:
        return x
    else:
        pa[x] = find2(pa[x])
        return pa[x]

  import sys
  input = sys.stdin.readline

  n,k,l = [int(i) for i in input().split()]
  par = [-1]*n
  pa = [-1]*n
  ans = [0]*n

  for i in range(k):
    p,q = [int(i) for i in input().split()]
    unite(p-1,q-1)

  def unite2(x,y):
      x = find2(x)
      y = find2(y)
      if x == y:
          return False
      else:
          if pa[x] > pa[y]:
              x,y = y,x
          pa[x] += pa[y]
          pa[y] = x
          return True

  for i in range(l):
    r,s = [int(i) for i in input().split()]
    unite2(r-1,s-1)

  dic = {}
  chk = []
  for i in range(n):
      p1 = find(i)
      p2 = find2(i)
      chk.append((p1,p2))
      if (p1,p2) in dic:
          dic[(p1,p2)] += 1
      else: 
          dic[(p1,p2)] = 1
  print(' '.join([str(dic[chk[i]]) for i in range(n)]))
  
if __name__ == '__main__':
    main()


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

using namespace std;

int main() {

	int x, n;
	cin >> x >> n;
	vector<int> p(n);
	for (int i = 0; i < n; i++) {

		cin >> p[i];

	}
	
	if (find(p.begin(), p.end(), x) == p.end()) {
		cout << x;
		return 0;
	}
	int i = 1;
	while (1) {
		
		 
		if (find(p.begin(), p.end(), x-i) == p.end()) {
			cout << x-i;
			return 0;
		}
		
		if (find(p.begin(), p.end(), x+i) == p.end()) {
			cout << x + i;
			return 0;
		}

		i++;
		

	}

}

Measured memory_bytes: 3632
#define T 444
D[T][T],i,j,x,y,a,b,c,r=9999;main(k){for(i=-1;++i<T;)for(j=-1;++j<T;)D[i][j]=r;scanf("%*d%d%d",&x,&y);for(D[0][0]=0;~scanf("%d%d%d",&a,&b,&c);)for(i=T;i-->a;)for(j=T;j-->b;)k=D[i-a][j-b]+c,D[i][j]>k?D[i][j]=k:0;for(i=x,j=y;i<T&&j<T;i+=x,j+=y)D[i][j]<r?r=D[i][j]:0;printf(r>=9999?"-1\n":"%u\n",r);}

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

template<class T> ll llpow(T x,T n){ll ans=1;if(x==0)ans=0;while(n){if(n&1)ans*=x;x*=x;n>>=1;}return ans;}
template<class T> inline T gcd(T x,T y){if(y==0)return x; else {return gcd(y,x%y);}}
template<class T> inline T lcm(T x,T y){return x/gcd(x,y)*y;}

#define rep(i,n) for(ll i=0;i<(ll)n;i++)
#define rep2(i, begin_i, end_i) for (ll i = (ll)begin_i; i < (ll)end_i; i++)

long long INF = 1LL<<60;
int main(){
    string s;
    cin>>s;
    int i=0;
    int before=s.size();
    while(s.size()>=2&&i<=(s.size()-1)-1){
        if(s.at(i)!=s.at(i+1)){
            s=s.erase(i,2);
            if(i!=0)i--;
        }
        else{
            i++;
            }
        }
   int after=s.size();
   cout<<before-after<<endl;
    return 0;
}




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

using pii = pair<int,int>;
using ll = long long;
#define rep(i, j) for(int i=0; i < (int)(j); i++)
#define repeat(i, j, k) for(int i = (j); i < (int)(k); i++)
#define all(v) v.begin(),v.end()
#define debug(x) cerr << #x << " : " << x << endl

template<class T> bool set_min(T &a, const T &b) { return a > b  ? a = b, true : false; }
template<class T> bool set_max(T &a, const T &b) { return a < b  ? a = b, true : false; }
// vector
template<class T> istream& operator >> (istream &is , vector<T> &v) { for(T &a : v) is >> a; return is; }
template<class T> ostream& operator << (ostream &os , const vector<T> &v) { for(const T &t : v) os << "\t" << t; return os << endl; }
// pair
template<class T, class U> ostream& operator << (ostream &os , const pair<T, U> &v) { return os << "<" << v.first << ", " << v.second << ">"; }

const int INF = 1 << 30;
const ll INFL = 1LL << 60;


class Solver {
  public:
    bool solve() {
        int r; cin >> r;
        cout << r * r << endl;
        return 0;
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    Solver s;
    s.solve();
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
# define mod 1000000007
# define INF (1 << 29)
/* ちゃんと考えて実装して問題なくACできた時嬉しいよ！！ */

int main(void){
    double t,x;
    cin >> t >> x;
    cout << t/x;
    return 0;
}

Measured memory_bytes: 764
import core.bitop, std.algorithm, std.ascii, std.bigint, std.conv, std.math,
    std.functional, std.numeric, std.range, std.stdio, std.string, std.random,
    std.typecons, std.container, std.format;
static import std.ascii;

// dfmt off
T lread(T = long)(){return readln.chomp.to!T();}
T[] aryread(T = long)(){return readln.split.to!(T[])();}
void scan(TList...)(ref TList Args){auto line = readln.split();
foreach (i, T; TList){T val = line[i].to!(T);Args[i] = val;}}
alias sread = () => readln.chomp();enum MOD = 10 ^^ 9 + 7;
alias PQueue(T, alias less = "a<b") = BinaryHeap!(Array!T, less);
// dfmt on

void main()
{
    long H, W;
    scan(H, W);
    auto S = new string[](H);
    foreach (i; 0 .. H)
        scan(S[i]);
    auto G = new long[][](H * W, H * W);
    long id(long h, long w)
    {
        return h * W + w;
    }

    foreach (ref row; G)
        row[] = 1234567;
    foreach (i; 0 .. H)
        foreach (j; 0 .. W)
            if (S[i][j] != '#')
                G[id(i, j)][id(i, j)] = 0;

    foreach (h; 0 .. H)
        foreach (w; 0 .. W)
        {
            if (S[h][w] == '#')
                continue;
            if (0 < h && S[h - 1][w] != '#')
                G[id(h, w)][id(h - 1, w)] = 1;

            if (0 < w && S[h][w - 1] != '#')
                G[id(h, w)][id(h, w - 1)] = 1;

            if (h < H - 1 && S[h + 1][w] != '#')
                G[id(h, w)][id(h + 1, w)] = 1;

            if (w < W - 1 && S[h][w + 1] != '#')
                G[id(h, w)][id(h, w + 1)] = 1;
        }

    // foreach (ref row; G)
    //     writeln(row);
    // writeln();

    foreach (k; 0 .. (H * W))
        foreach (i; 0 .. (H * W))
            foreach (j; 0 .. (H * W))
                if (G[i][j] > G[i][k] + G[k][j])
                    G[i][j] = G[i][k] + G[k][j];

    long ans = -1;
    foreach (row; G)
    {
        // writeln(row);
        foreach (x; row)
            if (x < 1234567)
                ans = max(ans, x);
    }
    writeln(ans);
}


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

using namespace std;
typedef long long ll;

#define REP(i,n) for(int i=0;i<n;i++)
#define REPD(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)

#define INF 1'000'000'000'000 //10^12
#define MOD 1'000'000'007


int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  int n;
  cin >> n;
  int d[n];
  
  REP(i,n)cin >> d[i];
  ll sum = 0LL;
  
  REP(i,n)FOR(j,i+1,n)sum += d[i]*d[j];
  
  cout << sum;
  cout << '\n';
  return 0;
}

Measured memory_bytes: 3588
#include <iostream>

using namespace std;

int main()
{
int x, y;
cin >> x>> y;
 if ((x==1 ||x==3||x==5||x==7||x==8||x==10||x==12)&&(y==1  ||y==3||y==5||y==7||y==8||y==10||y==12))
     cout << "Yes";
        else
        if( (x==4||x==6 ||x==9||x==11)&& (y==4||y==6 ||y==9||y==11))
        cout << "Yes";
        else
        if(x==2 &&y==2)
        cout << "Yes";

 else
    cout << "No";

    return 0;
}


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

int main(){
  int n,s,c[101],t[101],mn=100000;
  cin>>n>>s;
  
  for(int i=0;i<n;i++){
    cin>>c[i]>>t[i];
  }
  for(int i=0;i<n;i++){
    if(t[i]<=s){
      mn=min(mn,c[i]);
    }
  }
  if(mn==100000){
    cout<<"TLE"<<endl;
  }
  else{
    cout<<mn<<endl;
  }
}
  

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

int main()
{
    int a, b, k, i;
    cin >> k;
    cin >> a >> b;

    for(i=a; i<=b; i++)
    {
        if(i%k==0)
        {
            cout << "OK" << endl;
            return 0;
        }
    }

    cout << "NG" << endl;

    return 0;
}


Measured memory_bytes: 3620
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 2019


def resolve():
    s = input()
    n = len(s)
    s = s[::-1]

    ruiseki = [0]
    for i in range(n):
        ruiseki.append((ruiseki[-1] + int(s[i]) * pow(10, i, mod)) % mod)

    D = Counter(ruiseki)

    res = 0
    for v in D.values():
        res += v * (v - 1) // 2

    print(res)


if __name__ == '__main__':
    resolve()


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

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

#define p_ary(ary,a,b,i) do { cout << "["; for (int (i) = (a);(i) < (b);++(i)) cout << ary[(i)] << ((b)-1 == (i) ? "" : ", "); cout << "]\n"; } while(0)
#define p_map(map,it) do {cout << "{";for (auto (it) = map.begin();;++(it)) {if ((it) == map.end()) {cout << "}\n";break;}else cout << "" << (it)->first << "=>" << (it)->second << ", ";}}while(0)

const ll mod = 1000000007;
//const ll mod = 998244353;

const int MAX_N = 2010;
ll combi[MAX_N][MAX_N];

void pascal() {
    for (int i = 0;i < MAX_N;++i) for (int j = 0;j < MAX_N;++j) combi[i][j] = 0;
    combi[0][0] = 1;
    for (int i = 0;i < MAX_N-1;++i) for (int j = 0;j < i+1;++j) {
        combi[i+1][j+1] += combi[i][j];
        (combi[i+1][j] += combi[i][j]) %= mod;
    }
}

int main() {
    int n,k;
    cin >> n >> k;
    pascal();
    for (int i = 0;i < k;++i) {
        cout << combi[k-1][i]*combi[n-k+1][i+1]%mod << "\n";
    }
}

Measured memory_bytes: 31872
#include<bits/stdc++.h>
#define rep(i,a,...) for(int i = (a)*(strlen(#__VA_ARGS__)!=0);i<(int)(strlen(#__VA_ARGS__)?__VA_ARGS__:(a));++i)
#define per(i,a,...) for(int i = (strlen(#__VA_ARGS__)?__VA_ARGS__:(a))-1;i>=(int)(strlen(#__VA_ARGS__)?(a):0);--i)
#define foreach(i, n) for(auto &i:(n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define all(x) (x).begin(), (x).end()
#define bit(x) (1ll << (x))
#define lambda(RES_TYPE, ...) (function<RES_TYPE(__VA_ARGS__)>)[&](__VA_ARGS__) -> RES_TYPE
#define method(FUNC_NAME, RES_TYPE, ...) function<RES_TYPE(__VA_ARGS__)> FUNC_NAME = lambda(RES_TYPE, __VA_ARGS__)
using ll = long long;
//const ll MOD = (ll)1e9+7;
const ll MOD = 998244353;
const int INF = (ll)1e9+7;
const ll INFLL = (ll)1e18;
using namespace std;
template<class t>
using vvector = vector<vector<t>>;
template<class t>
using vvvector = vector<vector<vector<t>>>;
template<class t>
using priority_queuer = priority_queue<t, vector<t>, greater<t>>;
template<class t, class u> bool chmax(t &a, u b){if(a<b){a=b;return true;}return false;}
template<class t, class u> bool chmin(t &a, u b){if(a>b){a=b;return true;}return false;}
#ifdef DEBUG
#define debug(x) cout<<"LINE "<<__LINE__<<": "<<#x<<" = "<<x<<endl;
#else
#define debug(x) (void)0
#endif

namespace templates{
  ll modpow(ll x, ll b){
    ll res = 1;
    while(b){
      if(b&1)res = res * x % MOD;
      x = x * x % MOD;
      b>>=1;
    }
    return res;
  }

  ll modinv(ll x){
    return modpow(x, MOD-2);
  }

  bool was_output = false;
  template<class t>
  void output(t a){
    if(was_output)cout << " ";
    cout << a;
    was_output = true;
  }
  void outendl(){
    was_output = false;
    cout << endl;
  }
  ll in(){
    ll res;
    scanf("%lld", &res);
    return res;
  }

  template<class t>
  istream& operator>>(istream&is, vector<t>&x){
    for(auto &i:x)is >> i;
    return is;
  }

  template<class t, class u>
  istream& operator>>(istream&is, pair<t, u>&x){
    is >> x.first >> x.second;
    return is;
  }

  template<class t>
  void in(t&x){
    cin >> x;
  }

  template<class t>
  t in(){
    t res; cin >> res; return res;
  }

  template<class t>
  void out(t x){
    cout << x;
  }

  template<class t>
  vector<t> sorted(vector<t> line,function<bool(t,t)> comp=[](t a,t b){return a<b;}){
    sort(line.begin(),line.end(),comp);
    return line;
  }

  template<class t>
  vector<t> reversed(vector<t> line){
    reverse(line.begin(),line.end());
    return line;
  }
}

using namespace templates;

vector<int> input_vector(){
  int n = in();
  vector<int> res(n);
  foreach(i,res)i=in();
  return res;
}

int main(){
  auto a = input_vector();
  auto b = input_vector();
  cout << (a<b) << endl;
}



Measured memory_bytes: 3264
#include "bits/stdc++.h"
using namespace std;
#define repi(i,a,b) for(int i=(a), i##_len=(b); i<i##_len; ++i)
#define rep(i,n) repi(i,0,n)
#define all(x) (x).begin(),(x).end()
#define vsort(v) sort((v).begin(), (v).end())
#define gsort(v) tsort(v); reverse((v).begin(), (v).end())
#define vrev(v) reverse((v).begin(), (v).end())
#define siz(v) ((int)(v).size())
#define ers(v, n) (v).erase((v).begin() + n)
#define cnt(v, n) count(all(v), n)
#define vmin(v) *min_element(v.begin(), v.end())
#define vmax(v) *max_element(v.begin(), v.end())
#define el "\n"
#define co(x) cout<<(x)<<el
#define coc(c, a, b) if(c)co((a));else co((b))
#define cosp(x) cout<<(x)<<' '
#define YES(c) coc(c,"YES", "NO")
#define Yes(c) coc(c,"Yes", "No")
#define yes(c) coc(c,"yes", "no")
#ifdef tqktmp_2
#define gc() getchar(); getchar()
#else
#define gc() 1
#endif
typedef long long lint;

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

template<class T>inline bool maxi(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>inline bool mini(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);
	
	lint n, in, free=0; cin >> n;
	bool c[8] = { 0 };
	rep(i, n) {
		cin >> in;
		if (in >= 3200)free++;
		else c[in / 400] = 1;
	}
	lint ans = 0;
	rep(i, 8)ans += c[i];
	bool k = ans == 0;
	cout << ans+k << ' ' << ans + free << el;
	gc();
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define MIN_INT -2147483648
#define MAX_INT 2147483647
#define MIN_LONG -9223372036854775808L
#define MAX_LONG 9223372036854775807L
 
#define long long long int
 
using namespace std;
 
// @author: pashka
 
int main() {
    ios::sync_with_stdio(false);
 
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    int s = 0;
    for (int i = 0; i < n; i++) s += a[i];
    vector<int> d;
    for (int i = 1; i * i <= s; i++) {
        if (s % i == 0) {
            d.push_back(i);
            d.push_back(s / i);
        }
    }
    int res = 1;
    for (int x : d) {
        vector<int> b(n);
        for (int i = 0; i < n; i++) {
            b[i] = a[i] % x;
        }
        sort(b.begin(), b.end());
        int i = 0;
        int j = n - 1;
        long c = 0;
        while (i < j) {
            if (b[i] == 0) i++;
            else if (b[j] == x) j--;
            else {
                int q = min(b[i], x - b[j]);
                b[i] -= q;
                b[j] += q;
                c += q;
            }
        }
//        cout << x << " " << c << "\n";
        if (c <= k) {
            res = max(res, x);
        }
    }
    cout << res << "\n";
 
    return 0;
}

Measured memory_bytes: 384
def factorial_mod(n, mod):
    a = 1
    for i in range(1, n + 1):
        a *= i
        a %= mod
    return a


def cmb(n, k, mod):
    if k > n or k < 0:
        return 0
    fact_n = factorial_mod(n, mod)
    fact_k = factorial_mod(k, mod)
    fact_n_k = factorial_mod(n - k, mod)
    return (fact_n * pow(fact_k, mod - 2, mod) * pow(fact_n_k, mod - 2, mod)) % mod


n, k = map(int, input().split())
MOD = 10**9 + 7

for i in range(k):
    print(int(cmb(n - k + 1, i + 1, MOD) * cmb(k - 1, i, MOD) % MOD))

Measured memory_bytes: 9120
#include<iostream>

using namespace std;

long long N,M;
int i,j;
long long a[105];
long long b[105];

void solver(long long n){
	if(n==1){
		i++;
		b[i]=M--;
		return ;
	}
	if(n&1) {
		i++;
		b[i]=M--;
//		cout<<i<<"*";
		solver(n>>=1);
		
	}
	else{
		j++;
		a[j]=M--;
		solver(n-1);
	}
}

int main()
{
	long long N;
	cin>>N;
	M=100;
	solver(N);
	cout<<2*(i+j)<<endl;
	for(int m=1;m<=j;m++){
		cout<<a[m]<<" ";
	}
	for(int m=i;m>=1;m--){
		cout<<b[m]<<" ";
	}
	
//	cout<<" ! "<<i<<" ! "<<j<<"!";
	for(int m=101-i-j;m<=100;m++){
		cout<<m<<" ";
	}
	return 0;
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=int(a);i<int(b);i++)
typedef long long ll;


int main(){
    
    ll N,A,B;
    cin>>N>>A>>B;
    if(N==1 && A!=B)cout<<0<<endl;
    else if(N==1 && A==B)cout<<1<<endl;
    else if(A>B)cout<<0<<endl;
    else if(N!=1 && A==B)cout<<1<<endl;
    else cout<<(N-2)*(B-A)+1<<endl;
}




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

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

#define MAX 100

int t[MAX+2], v[MAX+2], s[MAX+2];

double f(int i, double t){
	if(i>0 && t<=s[i-1]) return v[i]+(s[i-1]-t);
	else if(t<=s[i]) return v[i];
	else return v[i]+(t-s[i]);
}

int main(){
	int n;
	cin >> n;
	t[0]=0, v[0]=0;
	t[n+1]=0, v[n+1]=0;
	for(int i=1; i<=n; i++) cin >> t[i];
	for(int i=1; i<=n; i++) cin >> v[i];

	s[0]=t[0];
	for(int i=1; i<=n+1; i++) s[i]=s[i-1]+t[i];

	double ans=0.0;
	for(int i=0; i<2*s[n+1]; i++){
		double f1=100.0, f2=100.0;
		for(int j=0; j<=n+1; j++) f1=min(f1, f(j, i/2.0));
		for(int j=0; j<=n+1; j++) f2=min(f2, f(j, (i+1)/2.0));
		ans+=(f1+f2)/4.0;
	}
	printf("%.9f\n", ans);
	return 0;
}

Measured memory_bytes: 256
<?php
fscanf(STDIN, "%d %d %d %d", $a, $b, $c, $d);

$loop = 0;
while(true) {
  if($loop%2 == 0) {
    $c -= $b;
  } else {
    $a -= $d;
  }

  if($a <= 0 || $c <= 0) {
    break;
  }
  $loop++;
}

echo ($a >= $c) ? 'Yes' : 'No';

Measured memory_bytes: 16168
#include <iostream>
#include <sstream>
#include <cstdlib>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstdio>
#include <numeric>
#include <bitset>
#include <stack>
#include <ctime>
using namespace std;

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

class State
{
public:
  int x, y, m, d;
  State(int xx, int yy, int mm, int dd)
    :x(xx), y(yy), m(mm), d(dd) {}
};

int main()
{
  int R, C;
  while (cin >> R >> C) {
    vector<string> c(R);
    for (int i = 0; i < R; ++i)
      cin >> c[i];

    bool yes = false;
    static bool visited[20][20][16][4];
    for (int i = 0; i < 20; ++i) {
      for (int j = 0; j < 20; ++j) {
	for (int k = 0; k < 16; ++k) {
	  for (int l = 0; l < 4; ++l)
	    visited[i][j][k][l] = false;
	}
      }
    }

    queue<State> que;
    que.push(State(0, 0, 0, 1));
    while (!que.empty()) {
      State st = que.front();
      que.pop();

      if (visited[st.y][st.x][st.m][st.d])
	continue;

      char op = c[st.y][st.x];
      visited[st.y][st.x][st.m][st.d] = true;
      switch (op) {

      case '<':
	st.d = 0;
	break;

      case '>':
	st.d = 1;
	break;

      case '^':
	st.d = 2;
	break;

      case 'v':
	st.d = 3;
	break;

      case '_':
	if (st.m == 0)
	  st.d = 1;
	else
	  st.d = 0;
	break;

      case '|':
	if (st.m == 0)
	  st.d = 3;
	else
	  st.d = 2;
	break;

      case '?':
	st.d = 4;
	break;

      case '@':
	yes = true;
	break;

      case '0':
      case '1':
      case '2':
      case '3':
      case '4':
      case '5':
      case '6':
      case '7':
      case '8':
      case '9':
	st.m = (op - '0');
	break;

      case '+':
	if (st.m == 15)
	  st.m = 0;
	else
	  ++st.m;
	break;

      case '-':
	if (st.m == 0)
	  st.m = 15;
	else
	  --st.m;
	break;
      }

      if (yes)
	break;

      if (st.d < 4) {
	st.x += dx[st.d];
	if (st.x < 0)
	  st.x = C-1;
	else if (st.x >= C)
	  st.x = 0;

	st.y += dy[st.d];
	if (st.y < 0)
	  st.y = R-1;
	else if (st.y >= R)
	  st.y = 0;

	que.push(st);
      } else {
	int x = st.x, y = st.y;
	for (int i = 0; i < 4; ++i) {
	  st.x = x + dx[i];
	  if (st.x < 0)
	    st.x = C-1;
	  else if (st.x >= C)
	    st.x = 0;

	  st.y = y + dy[i];
	  if (st.y < 0)
	    st.y = R-1;
	  else if (st.y >= R)
	    st.y = 0;

	  st.d = i;
	  que.push(st);
	}
      }
    }

    if (yes)
      cout << "YES" << endl;
    else
      cout << "NO" << endl;
  }

  return 0;
}

Measured memory_bytes: 0
#include<iostream>
using namespace std;
 
int dp[1000001] = {0};
int main() {
        int a=1,n,m;
        for(int i = 0 ; a <= 1000000 ; i++){
                int b = 1;
                for(int j = 0 ; a*b <= 1000000 ; j++){
                        int c = 1;
                        for(int k = 0 ; a*b*c <= 1000000 ; k++){
                                dp[a*b*c] = true;
                                c *= 5;
                        }
                        b *= 3;
                }
                a *= 2;
        }
        for(int i = 1 ; i <= 1000000 ; i++){
                dp[i] += dp[i-1];
        }
        while(cin >> m&&m){
                cin >> n;
                cout << dp[n] - dp[m-1] << endl;
        }
        return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
int dp[201][201][2];
int main() {
  string s;
  cin >> s;
  int n=s.size();
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++)dp[i][j][0]=1<<29,dp[i][j][1]=-(1<<29);
    if(isdigit(s[i]))dp[i][i][0]=dp[i][i][1]=s[i]-'0';
  }
  for(int i=0; i<n; i++){
    for(int j=0;j<n-i;j++){
      if(s[j]=='(')dp[j][j+i][0]=min(dp[j][j+i][0],dp[j+1][j+i][0]),dp[j][j+i][1]=max(dp[j][j+i][1],dp[j+1][j+i][1]);
      if(s[j+i]==')')dp[j][j+i][0]=min(dp[j][j+i][0],dp[j][j+i-1][0]),dp[j][j+i][1]=max(dp[j][j+i][1],dp[j][j+i-1][1]);
    }
    for(int j=0;j<n-i;j++){
      if(s[j]=='+'||s[j]=='-'||s[j+i]=='+'||s[j+i]=='-')continue;
      for(int k=j+1;k<=j+i-1;k++){
        if((j+2<=k&&s[k-2]=='(')||(k<=j+i-2&&s[k+2]==')'))continue;
        if(s[k]=='+'||s[k]=='-'){
          for(int x=0;x<2;x++)for(int y=0;y<2;y++){
              if(abs(dp[j][k-1][x])>=(1<<29)||abs(dp[k+1][j+i][y])>=(1<<29))continue;
              dp[j][j+i][0]=min(dp[j][j+i][0],dp[j][k-1][x]+dp[k+1][j+i][y]*(s[k]=='+'?1:-1));
              dp[j][j+i][1]=max(dp[j][j+i][1],dp[j][k-1][x]+dp[k+1][j+i][y]*(s[k]=='+'?1:-1));
            }
        }
      }
    }
  }
  cout<<dp[0][n-1][1]<<endl;
  return 0;
}


Measured memory_bytes: 3484
# https://atcoder.jp/contests/abc095/tasks/arc096_a



A, B, C, X, Y = gets.split.map(&:to_i)

if C * 2 > A + B
  puts A * X + B * Y
  exit
end

if C <= [A, B].min / 2
  puts C * [X, Y].max * 2
  exit
end

# C を"高い"ピザの必要な枚数を満たすように買う場合
c = A > B ? 2 * X : 2 * Y
cheaper_pizza_count = A > B ? Y : X
ans1 = C * c + [A, B].min * [cheaper_pizza_count - (c / 2), 0].max

# C を"安い"ピザの必要な枚数を満たすように買う場合
c = A > B ? 2 * Y : 2 * X
richer_pizza_count = A > B ? X : Y
ans2 = C * c + [A, B].max * [richer_pizza_count - (c / 2), 0].max

puts [ans1, ans2].min


Measured memory_bytes: 1788
#include<bits/stdc++.h>
using namespace std;
int main(){
	int H,N;
  	cin>>H>>N;
  int sum=0;
  while(N--){
  	int a;
    cin>>a;
    sum+=a;
    if(sum>=H){
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
  return 0;



}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define loop2(i, s, n, a) for (int i = int(s); i < int(n); i += a)
#define loop(i, s, n) loop2(i, s, n, 1)
#define rep(i, n) loop(i, 0, n)

#define pb push_back
#define all(in) in.begin(),in.end()

using ll = long long;
using ull = unsigned long long;
using namespace std;

int main(){
    ll n, m, k; cin >> n >> m >> k;
    vector<ll> a(n),b(m);
    rep(i,n) cin >> a[i];
    rep(i,m) cin >> b[i];
    rep(i,n-1) a[i+1] += a[i];
    rep(i,m-1) b[i+1] += b[i];

    ll ans = 0;
    rep(i,n){
        if(a[i]<=k){
        ll count = i+1;
        ll kk = upper_bound(all(b),k-a[i])-b.begin();
        count += kk;
        if(ans < count) ans = count;
        }
    }
    ll count = 0;
    ll kk = upper_bound(all(b),k)-b.begin();
    count += kk;
    if(ans < count) ans = count;

    cout << ans << endl;
}

Measured memory_bytes: 6368
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    if (n == 0){
        cout << "0" << endl;
        return 0;
    }
    int ans[64] = {}, p = 0;
    while (n){
        if (n < 0){
            n = -n;
            if (n % 2 == 1){
                ans[++p] = 1;
                n = n / 2 + 1;
            }
            else{
                ans[++p] = 0;
                n = n / 2;
            }
        }else{
            if (n % 2 == 1) ans[++p] = 1;
            else ans[++p] = 0;
            n = - (n / 2);
        }
    }
    for (int i = p; i > 0; --i) cout << ans[i];
    cout << endl;
    return 0;
}


Measured memory_bytes: 256
N = int(input())
S = input()
S += S[0:2]

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


Measured memory_bytes: 3444
#define f(X) for(c=0;c<X;c+=v[p++]);if(c-X)goto L;
n,v[50],s,p,c,a[9];
main(){for(;n=atoi(gets(a));){for(s=0;s<n;v[++s]=strlen(gets(a)));s=0;L:p=++s;f(5)f(7)f(5)f(7)f(7)printf("%d\n",s);}}

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

using namespace std;

#define endl     "\n"
#define mod      1000000007
#define fi       first
#define se       second
#define pb       push_back
#define mp		 make_pair
#define bs       binary_search
#define lbnd     lower_bound
#define ubnd	 upper_bound
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) ((a)*(b))/__gcd((a),(b))
#define sz		 size

typedef long long ll;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	int a,b;
	cin>>a>>b;
	if(a+b==15)
		cout<<"+"<<endl;
	else if(a*b==15)
		cout<<"*"<<endl;
	else
		cout<<"x"<<endl;
	return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) {

		 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		 try{

			 int S = Integer.parseInt(br.readLine());

			 System.out.printf("%d:%d:%d\n",S/3600,(S%3600)/60,S%60);

		 }catch(IOException e){
			 e.printStackTrace();
		 }
	}
}


Measured memory_bytes: 24608
#include<stdio.h>
#include<string.h>
main()
{
    char a[3];
    int i;
    while(scanf("%s",a)==1){
        if(strlen(a)==2){
            printf("%s\n",a);
        }
        else{
            for(i=2;i>=0;i--)
                printf("%c",a[i]);
            printf("\n");
        }
    }
}


Measured memory_bytes: 128
#include <iostream>

using namespace std;

int main() {
    string s;
    cin >> s;
    for (int i = 0; i < 3; ++i) if (s.at(i) == s.at(i + 1)) {
        cout << "Bad\n";
        return 0;
    }
    cout << "Good\n";
    return 0;
}


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

#define rep(i, x, n) for (int i = x; i < n; i++)
typedef long long ll;

const int INF = 1e9 + 7;

using namespace std;

void dfs(int p, int id, const vector<vector<pair<int, int>>>& graph, int c, vector<int>& res) {
  res[id] = c;
  for (auto tmp : graph[id]) {
    if (tmp.first == p)
      continue;

    if (tmp.second & 1)
      dfs(id, tmp.first, graph, 1 - c, res);
    else
      dfs(id, tmp.first, graph, c, res);
  }
}

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

  int n;
  cin >> n;

  vector<vector<pair<int, int>>> graph(n);
  rep (i, 0, n - 1) {
    int u, v, w;
    cin >> u >> v >> w;

    u -= 1;
    v -= 1;
    graph[u].push_back(make_pair(v, w));
    graph[v].push_back(make_pair(u, w));
  }

  vector<int> res(n);
  dfs(-1, 0, graph, 0, res);

  rep (i, 0, n)
    cout << res[i] << endl;

	return 0;
}


Measured memory_bytes: 9728
#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>

using namespace std;

#define int long long
#define endl "\n"

const long long INF = (long long)1e18;
const long long MOD = 1'000'000'007; 

int hoge = 1'000;

string yn(bool f){return f?"Yes":"No";}
string YN(bool f){return f?"YES":"NO";}



signed main(){
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout<<fixed<<setprecision(10);
        
        int N, C;
        int ans = 0;
        vector<int> x, sum1, sum2, v;
        
        cin>>N>>C;
        
        x.resize(N);
        v.resize(N);
        sum1.resize(N+1);
        sum2.resize(N+1);
        
        for(int i = 0; i < N; i++){
                cin>>x[i]>>v[i];
        }
        
        for(int i = 0, sum = 0; i < N; i++){
                sum += v[i];
                
                sum1[i+1] = max(sum1[i],sum - x[i] * 2);
                //cout<<"i = "<<i+1<<" sum1 "<<sum1[i+1]<<endl;
        }
        
        for(int i = 0, sum = 0; i < N; i++){
                sum += v[N-i-1];
                
                sum2[i+1] = max(sum2[i],sum - (C - x[N-i-1]) * 2);
        }
        
        for(int i = 0, sum = 0; i < N; i++){
                int j = N - i - 1;
                sum += v[j];
                //cout<<"i = "<<i<<" sum = "<<sum<<" v = "<<v[j]<<endl;
                //cout<<"sum1 "<<sum1[j]<<" - "<<(C - x[j])<<" = "<<sum + sum1[j] - (C - x[j])<<endl;
                ans = max(sum + sum1[j] - (C - x[j]), ans);
        }
        
        
        for(int i = 0, sum = 0; i < N; i++){
                int j = N - i - 1;
                sum += v[i];
                
                ans = max(sum + sum2[j] - x[i], ans);
        }
        
        cout<<ans<<endl;
        
        return 0;
}

Measured memory_bytes: 3456
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b;
  cin >> a >> b;
  int x = (a + b) / 2;
  if ((a + b) % 2 == 0){
    cout << x << endl;
  }
  else{
    cout << x + 1 << endl;
  }
}

Measured memory_bytes: 3600
// https://atcoder.jp/contests/agc016/tasks/agc016_a
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <set>
#include <unordered_set>
#include <bitset>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define REP(i, n) for(size_t i = 0; i < (n); ++i)

int main()
{
    string s;
    cin >> s;
    set<char> cs;
    for (const char& c : s) cs.insert(c);
    if (cs.size() == 1)
    {
        printf("0\n");
        return 0;
    }
    int ans = s.size() / 2;
    for (const char& c : cs)
    {
        string chunk = s;
        int count = 1;
        bool isRetry = true;
        while (isRetry)
        {
            string str;
            isRetry = false;
            for (int i = 0; i < chunk.size() - 1; ++i)
            {
                if (c == chunk[i] || c == chunk[i + 1])
                {
                    str.push_back(c);
                }
                else
                {
                    // 異なる文字が入っている場合
                    str.push_back(chunk[i]);
                    isRetry = true;
                }
            }

            if (isRetry)
            {
                chunk = str;
                ++count;
            }
        }

        ans = min(ans, count);
    }

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


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

int main() {
    int N;
    cin>>N;
    vector<int> a(3*N);
    for(int i=0; i<3*N; i++) cin>>a[i];
    sort(a.begin(), a.end(), greater<int>());
    long ans=0;
    for(int i=1; i<2*N; i+=2) ans+=a[i];
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 1408
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
 
using namespace std;
 
#define PB push_back
#define MP make_pairA
#define REP(i,n) for(int i=0;i<(n);i++)
int main()
{
    string s;
    cin>>s;
    if(s.size()==2)cout<<s<<endl;
    else{
        REP(i,s.size())cout<<s[s.size()-1-i];
        cout<<endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
using namespace std;
#define int long long
#define double long double
 
int gcd(int x,int y){
    if(y==0)return x;
    x=x%y;
    gcd(y,x);
}
main()
{
    int n,m;
    cin>>n>>m;
    vector<int>a(n);
    vector<int>b(n);
    map<int,int> mp;
    rep(i,n){
        cin>>a[i]>>b[i];
        mp[a[i]]+=b[i];
    }
    int cnt=0,ans=0;
    auto it=mp.begin();
    while(cnt<m){
        int temp=min(m-cnt,it->second);
        ans+=it->first*temp;
        cnt+=temp;
        it++;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 8064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())
#define len(x) ((ll)(x).length())

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // std::ifstream in("input.txt");
    // std::cin.rdbuf(in.rdbuf());
    ll n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    ll streak = 0;
    rep(i, n + 1) {
        if (s[i] == '1') streak++;
        else streak = 0;
        if (streak >= m) {
            cout << -1 << endl;
            return 0;
        }
    }
    ll pos = n;
    vector<ll> ans;
    while(pos > 0) {
        rreps(i, 1, m + 1) {
            if ((pos - i) < 0) continue;
            if (s[pos - i] == '0') {
                pos -= i;
                ans.push_back(i);
                break;
            }
        }
    }
    reverse(all(ans));
    rep(i, sz(ans)) {
        printf("%lld%s", ans[i], (i == (sz(ans) - 1)) ? "\n" : " ");
    }
    return 0;
}


Measured memory_bytes: 1480
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
const long long MOD = 1000000007;
using namespace std;
typedef long long ll;
map<ll, int> mp;
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int d, g, p[11], c[11];
	cin >> d >> g;
	for (int i = 0; i < d; i++) {
		cin >> p[i] >> c[i];
	}
	int ans = 1e9;
	for (int i = 0; i < (1 << d); i++) {
		int s = 0, num = 0, rest_max = -1;
		for (int j = 0; j < d; j++) {
			if (i >> j & 1) {
				s += 100 * (j + 1) * p[j] + c[j];
				num += p[j];
			}
			else {
				rest_max = j;
			}
		}
		if (s < g) {
			int s1 = 100 * (rest_max + 1);
			int need = (g - s + s1 - 1) / s1;
			if (need >= p[rest_max]) {
				continue;
			}
			num += need;
		}
		ans = min(ans, num);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

using ll = long long;
void max_self(int &a, int b){
	a = max(a,b);
	}
int main(){
	int n;
	scanf("%d",&n);
	vector<int> dp(3);
	for(int i = 0 ; i < n; ++i){
		vector<int> activity(3);
		for(int &x : activity){
			scanf("%d",&x);
			}
		vector<int> new_dp(3);
		for(int j = 0; j < 3; j++){
			for(int k = 0; k < 3; k++){
				if( j != k){
					max_self(new_dp[k], dp[j] + activity[k]);
					}
				}
			}
		dp = new_dp;
		}
		int answer = 0;
		for(int i = 0 ; i < 3; ++i)
			max_self(answer, dp[i]);
			
		printf("%d",answer);
	
}

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

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

int main()
{
    int h, w, cnt;
    cin >> h >> w;
    string s[h];
    for (int i = 0; i < h; i++)
    {
        cin >> s[i];
    }

    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            if (s[i][j] == '#')
                continue;
            cnt = 0;
            for (int v = 0; v < 8; v++)
            {
                const int ny = i + dy[v];
                const int nx = j + dx[v];

                if (nx < 0 || w <= nx)
                    continue;
                if (ny < 0 || h <= ny)
                    continue;
                if (s[ny][nx] == '#')
                    cnt++;
            }
            s[i][j] = char(cnt + '0');
        }
    }

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

Measured memory_bytes: 256