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

using namespace std;

typedef long long ll;
const ll INF = 1LL<<60;

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

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

ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}

int dist[810][810] = {0};

int calc_dist(int i, int j, int H, int W){

  return min(min(i, H-1-i), min(j, W-1-j));

}

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

  int H, W, K;
  cin >> H >> W >> K;
  vector<vector<bool>> is_ok(H);
  string s;

  int si, sj;
  for(int i = 0; i < H; i++){
    cin >> s;
    for(int j = 0; j < W; j++){
      if(s[j] == '#'){
        is_ok[i].push_back(false);
      }else if(s[j] == '.'){
        is_ok[i].push_back(true);
      }else{
        is_ok[i].push_back(true);
        si = i;
        sj = j;
      }
    }
  }

  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      dist[i][j] = -1;    
    }
  }
  
  dist[si][sj] = 0;
  int min_dist = calc_dist(si, sj, H, W);
  queue<pair<int, int>> q;
  q.push(make_pair(si, sj));

  while(!q.empty()){

    pair<int, int> next = q.front();
    int ci = next.first;
    int cj = next.second;
    q.pop();
    
    if(ci-1 >= 0  && is_ok[ci-1][cj]){
      if(dist[ci-1][cj] < 0){
      dist[ci-1][cj] = dist[ci][cj] + 1;
      if(dist[ci-1][cj] <= K){
        chmin(min_dist, calc_dist(ci-1, cj, H, W));
      }
      q.push(make_pair(ci-1, cj));
      }
    }

    if(ci+1 < H && is_ok[ci+1][cj]){
      if(dist[ci+1][cj] < 0){
      dist[ci+1][cj] = dist[ci][cj] + 1;
      if(dist[ci+1][cj] <= K){
        chmin(min_dist, calc_dist(ci+1, cj, H, W));
      }
      q.push(make_pair(ci+1, cj));
      }
    }

    if(cj-1 >= 0  && is_ok[ci][cj-1]){
      if(dist[ci][cj-1] < 0){
      dist[ci][cj-1] = dist[ci][cj] + 1;
      if(dist[ci][cj-1] <= K){
        chmin(min_dist, calc_dist(ci, cj-1, H, W));
      }
      q.push(make_pair(ci, cj-1));
      }
    }

    if(cj+1 < W && is_ok[ci][cj+1]){
      if(dist[ci][cj+1] < 0){
        dist[ci][cj+1] = dist[ci][cj] + 1;
        if(dist[ci][cj+1] <= K){
          chmin(min_dist, calc_dist(ci, cj+1, H, W));
        };
        q.push(make_pair(ci, cj+1));
      }
    }
  }

  cout << 1 + (min_dist + K - 1) / K << endl; 

  return 0;
}


Measured memory_bytes: 2944
while True :
    x=int(input())
    if x==0:
        break
    else:
        a=(1000-x)//500
        b=(1000-x-500*a)//100
        c=(1000-x-500*a-100*b)//50
        d=(1000-x-500*a-100*b-50*c)//10
        e=(1000-x-500*a-100*b-50*c-10*d)//5
        f=1000-x-500*a-100*b-50*c-10*d-5*e
        print(a+b+c+d+e+f)


Measured memory_bytes: 5584
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (true) {
			int n = sc.nextInt();
			if (n == 0)
				break;
			int result = 0;
			for (int i = 1; i < n / 2 + 1; i++) {
				int sum = i;
				for (int j = i + 1; j < n; j++) {
					sum += j;
					if (sum == n) {
						result++;
						break;
					} else if (sum > n)
						break;
				}
			}
			System.out.println(result);
		}
		sc.close();
	}
}

Measured memory_bytes: 19964
#include <bits/stdc++.h>
using namespace std;
long long a,b,c;
int main(){
	cin>>b>>a>>c;
	b=b-c,c=0;
	if (b<0) c-=b,b=0;
	a=a-c;
	if (a<0) a=0;
	cout<<b<<" "<<a;
}

Measured memory_bytes: 256
n = int(input())
d = []
for d_i in range(n):
  d.append(int(input()))
  
count = 0
pre_max = -1
max = -1

for i in range(n): 
  for j in d:
    if j > max:
      max = j
      
  d[d.index(max)] = 0
      
  if pre_max == -1:
    count += 1
    
  elif max < pre_max:
    count += 1
    
  pre_max = max
  max = -1
  
print(count)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#include<cstdio>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm;
inline char getcha() {
	if (ci - cn == cm) { fread(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	char C = getcha();
	int A = C - '0';
	while ((C = getcha()) >= '0') A = A * 10 + C - '0';
	return A;
}

const ll q = ((ll)1000000000 << 30);

int P[100001];
int D[100001];
ll Find(int A) {
	if (P[A] < 0) return q + A;

	ll k = Find(P[A]);
	int d = (k >> 30) - 1000000000;
	int p = k & ((1 << 30) - 1);
	D[A] += d;
	P[A] = p;

	return ((ll)(D[A] + 1000000000) << 30) + p;
}

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


	int N = getint();
	int M = getint();
	rep1(i, N) P[i] = -1;

	int OK = 1;
	rep(i, M) {
		int L = getint();
		int R = getint();
		int d = getint();

		ll k = Find(L);
		int dl = (k >> 30) - 1000000000;
		int l = k & ((1 << 30) - 1);
		k = Find(R);
		int dr = (k >> 30) - 1000000000;
		int r = k & ((1 << 30) - 1);

		if (l != r) {
			if (P[l] <= P[r]) {
				P[l] += P[r];
				P[r] = l;
				D[r] = dl - dr + d;
			}
			else {
				P[r] += P[l];
				P[l] = r;
				D[l] = dr - dl - d;
			}
		}
		else {
			if (dl + d != dr) {
				OK = 0;
				break;
			}
		}
	}
	if (OK) printf("Yes");
	else printf("No");

	Would you please return 0;
}

Measured memory_bytes: 1152
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=100;

char maz[N+5][N+5];
int dp[N+3][N+3];
int r,c;

int main(){
	scanf("%d%d",&r,&c);
	for(int i=1;i<=r;i++) scanf("%s",maz[i]+1);
	memset(dp,0x3f,sizeof dp);
	dp[1][1]=maz[1][1]=='#';
	for(int i=1;i<=r;i++)
		for(int j=i==1? 2:1;j<=c;j++){
			if(i>1){
				if(maz[i][j]=='#'){
					if(maz[i-1][j]=='#') dp[i][j]=min(dp[i][j],dp[i-1][j]);
					else dp[i][j]=min(dp[i][j],dp[i-1][j]+1);
				}
				else dp[i][j]=min(dp[i][j],dp[i-1][j]);
			}
			if(j>1){
				if(maz[i][j]=='#'){
					if(maz[i][j-1]=='#') dp[i][j]=min(dp[i][j],dp[i][j-1]);
					else dp[i][j]=min(dp[i][j],dp[i][j-1]+1);
				}
				else dp[i][j]=min(dp[i][j],dp[i][j-1]);
			}
		}
	printf("%d\n",dp[r][c]);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(c) (c).begin(),(c).end()
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define MINF(a) memset(a,0x3f,sizeof(a))
#define POW(n) (1LL<<(n))
#define IN(i,a,b) (a <= i && i <= b)
using namespace std;
template <typename T> inline bool CHMIN(T& a,T b) { if(a>b) { a=b; return 1; } return 0; }
template <typename T> inline bool CHMAX(T& a,T b) { if(a<b) { a=b; return 1; } return 0; }
template <typename T> inline void SORT(T& a) { sort(ALL(a)); }
template <typename T> inline void REV(T& a) { reverse(ALL(a)); }
template <typename T> inline void UNI(T& a) { sort(ALL(a)); a.erase(unique(ALL(a)),a.end()); }
template <typename T> inline T LB(vector<T>& v, T& a) { return *lower_bound(ALL(v),a); }
template <typename T> inline int LBP(vector<T>& v, T& a) { return lower_bound(ALL(v),a) - v.begin(); }
template <typename T> inline T UB(vector<T>& v, T& a) { return *upper_bound(ALL(v),a); }
template <typename T> inline int UBP(vector<T>& v, T& a) { return upper_bound(ALL(v),a) - v.begin(); }
template <typename T1, typename T2> ostream& operator<< (ostream& os, const pair<T1,T2>& p) { os << p.first << " " << p.second; return os; }
template <typename T1, typename T2> istream& operator>> (istream& is, pair<T1,T2>& p) { is >> p.first >> p.second; return is; }
template <typename T> ostream& operator<< (ostream& os, const vector<T>& v) { REP(i,v.size()) { if (i) os << " "; os << v[i]; } return os; }
template <typename T> istream& operator>> (istream& is, vector<T>& v) { for(T& in : v) is >> in; return is; }
template <typename T = int> vector<T> make_v(size_t a) { return vector<T>(a); }
template <typename T, typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...)); }
template< typename T, typename V > typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) { t = v; }
template< typename T, typename V > typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) { for(auto &e : t) fill_v(e, v); }
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-10;

signed main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  int N;
  cin >> N;
  vector<int> A(N),v;
  cin >> A;
  v.push_back(-A[0]);
  FOR(i,1,N) {
    int pos = upper_bound(ALL(v),-A[i])-v.begin();
    if (pos == v.size()) v.push_back(-A[i]);
    else v[pos] = -A[i];
  }
  cout << v.size() << endl;

  return 0;
}

Measured memory_bytes: 2168
N=int(input())
ans=0
p=2
 
while N>1 and p*p<=N:
  if N%p==0:
    c=0
    while N%p==0:
      N=N/p
      c=c+1
    Y=1
    U=2
    while c>=Y:
      ans=ans+1
      Y=Y+U
      U=U+1
  p=p+1
 
if N>1:
  ans=ans+1
 
print(ans)

Measured memory_bytes: 9292
#include<stdio.h>
#define ll long long

ll n;
char c[2123456];

int main(){
  scanf("%lld",&n);
  scanf("%s",c);
  ll ans=0;
  int l=0,r=n-1;
  while(r>l){
    while(l<n && c[l]=='R'){
      l++;}
    while(r>=0 && c[r]=='W'){
      r--;}
    if(r<0 || l>=n || r<l) break;
    c[l]='R';
    c[r]='W';
    ans++;}

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


Measured memory_bytes: 1920
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,k,i,j,tt=0;
	cin>>n>>k;//6 3
	int yen[n];
	for(i=0;i<n;i++)
		cin>>yen[i];//1 2 4 3 7 6
	sort(yen,yen+n);//1 2 3 4 6 7
	for(i=0;i<k;i++)
		tt+=yen[i];
	cout<<tt;
	return 0;
}

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

const int N = 200010;

typedef pair<int, int> P;

int A[N], n;

inline bool check(int mid) {
	set<P> s;
	for (int i = 2; i <= n; i++) if (A[i] <= A[i - 1]) {
		while (s.size() && s.rbegin() -> first > A[i]) s.erase(*s.rbegin());
		for (int j = A[i]; ; j--) {
			if (!j) return false;
			if (s.size() && j == s.rbegin() -> first) {
				if (s.rbegin() -> second < mid - 1) {
					auto t = *s.rbegin(); s.erase(t), t.second++;
					s.insert(t); break;	
				} else s.erase(*s.rbegin());
			} else {
				if (mid == 1) return false;
				s.insert(P(j, 1)); break;
			}
		} 
	}
	return true;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &A[i]);
	int l = 1, r = n, mid, ans = -1;
	while (l <= r) {
		mid = (l + r) >> 1;
		if (check(mid)) r = mid - 1, ans = mid;
		else l = mid + 1;
	}
	printf("%d\n", ans);
}

Measured memory_bytes: 1024
#include <iostream>

using namespace std;

int main(){
  int p[8],a,s,t;
  long x,y;
  int c[8]={1,2,1,2,1,4,1,4};
  while(cin>>p[0]){
    t=1000000;x=50000000;
    for(int i=1;i<8;++i) cin>>p[i];
    for(int j=0;j<8;++j){
      s=((p[0]-c[j]>0)?p[0]-c[j]:0);
      for(int i=1;i<8;++i){
	s+=((p[i]-c[(i+j)%8]>0)?p[i]-c[(i+j)%8]:0);
      }
      if(t>=s){
	y=0;
	for(int i=0;i<7;++i) y=(y+c[(j+i)%8])*10;
	y+=c[(j+7)%8];
	if(t!=s||x>y){
	  x=y;t=s;a=j;
	}
      }
    }
    int k;
    for(k=a;(k-a)%8!=7;++k) cout<<c[k%8]<<" ";
    cout<<c[k%8]<<endl;
  }
  return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
#define ll int64_t

//ライブラリ始まり

//定数

//円周率
const double PI = 3.1415926535897932384;

//天井
const int INF = 1000000000; // = 10^9
const ll LINF = 1000000000000000; // = 10^15

//ABC文字列
const string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZABC";
const string abc = "abcdefghijklmnopqrstuvwxyzabc";

//よくあるmodくん
const ll MOD = 1000000007; // = 10^9 + 7

//関数

//ctoi
int ctoi(char c){
  if (c == '0') {
    return 0;
  }
  if (c == '1') {
    return 1;
  } 
  if (c == '2') {
    return 2;
  } 
  if (c == '3') {
    return 3;
  }
  if (c == '4') {
    return 4;
  } 
  if (c == '5') {
    return 5;
  } 
  if (c == '6') {
    return 6;
  }
  if (c == '7') {
    return 7;
  } 
  if (c == '8') {
    return 8;
  } 
  if (c == '9') {
    return 9;
  }
  return -1;  
}

//素数判定
bool PN(int x) {
  if (x <= 1) {
    return false;
  }
  if (x == 2) {
    return true;
  }
  for (int i = 2; i < sqrt(x) + 1; i++) {
    if (x % i == 0) {
      return false;
    }
  }
  return true;
}

//ライブラリ終わり

int main() {
  int N;
  cin >> N;
  int M = N;
  int S = 0;
  for (int i = 9; i >= 0; i--) {
    int K = pow(10, i);
    S += (M / K);
    M %= K;
  }
  if (N % S == 0) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 3908
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args)
	{
		Scanner s=new Scanner(System.in);
		
		long n=s.nextLong();
		long k=s.nextLong();
		
		System.out.println(Math.min(n%k,k-(n%k)));
		
	}
	
}

Measured memory_bytes: 21972
import sys

def main():
    N, K = map(int, input().split())
    a = list(map(int, input().split()))

    if N == K:
        mask = [1] * N

        print(calc(N, a, mask))
        return

    ans = sys.maxsize
    for i in range(1 << N):
        mask = [i >> j & 1 for j in range(N)]
        if sum(mask) < K: continue
        mask.reverse()

        ans = min(ans, calc(N, a, mask))

    print(ans)
    return

def calc(N, a, mask):
    ans = 0
    m = a[0]
    for i in range(1, N):
        m = max(m, a[i - 1])
        if mask[i] == 0:continue
        if m < a[i]:
            continue
        else:
            v = m - a[i] + 1
            ans += v
            m = a[i] + v

    return ans

if __name__ == '__main__':
    main()

Measured memory_bytes: 9076
#include <bits/stdc++.h>
using namespace std;
#define INF 20000
struct Point
{
	int x;
	int y;
};

Point p0;

int orientation(Point a, Point b, Point c)
{
	int val = (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
	if(val>0) return 1;
	else if(val<0) return -1;
	else return 0;
}

bool onLine(Point a, Point b, Point c)
{
	if(b.x<=max(a.x,c.x) && b.x>=min(a.x,c.x) && b.y<=max(a.y,c.y) && b.y>=min(a.y,c.y)) return true;
	return false;
}

bool intersect(Point a, Point b, Point c, Point d)
{
	int o1 = orientation(a,b,c);
	int o2 = orientation(a,b,d);
	int o3 = orientation(c,d,a);
	int o4 = orientation(c,d,b);

	if(o1!=o2 && o3!=o4) return true;
	if(o1==0 && onLine(a,c,b)) return true;
	if(o2==0 && onLine(a,d,b)) return true;
	if(o3==0 && onLine(c,a,d)) return true;
	if(o4==0 && onLine(c,b,d)) return true;
	return false;
}

int comp(const void *a, const void *b)
{
	Point *p1 = (Point*)a;
	Point *p2 = (Point*)b;	
	return 0;
}

void inside(Point shape[], int size, Point t)
{
	int intersection=0;
	Point end = {INF,t.y};
	for(int i=0;i<size;i++)
	{
		if(intersect(shape[i],shape[(i+1)%size],t,end)) 
		{
			intersection++;
			int o1 = orientation(t,shape[i],shape[(i+1)%size]);
			if(o1==0)
			{
					if(onLine(shape[i],t,shape[(i+1)%size])) 
					{
						cout<<"1"<<endl;
						return;
					}
					else intersection--; 
			}
			
			if(onLine(t,shape[(i+1)%size],end))
			{
				if(shape[i].y>=t.y) intersection--;	
			}
			if(onLine(t,shape[i],end))
			{
				if(shape[(i+1)%size].y>=t.y) intersection--;	
			}

		}
	}
	if(intersection%2==0) cout<<"0"<<endl;
	else cout<<"2"<<endl;
}

int main()
{
	int t,q;
	cin>>q;
	Point shape[q];
	int x,y;
	for(int i=0;i<q;i++)
	{
		cin>>x>>y;
		shape[i]={x,y};
	}
	p0 = {shape[0].x,shape[0].y};
	for(int i=0;i<q;i++)
	{
	
	}	
	cin>>t;
	for(int i=0;i<t;i++)
	{
		cin>>x>>y;
		Point in = {x,y};
		inside(shape,q,in);	
	}	
	return 0;
}



Measured memory_bytes: 3124
#include<bits/stdc++.h>
using namespace std;
const int N=205;
struct Edge{
	int to,nex,cap;
}e[N*N];
int n,s,t,head[N],a[N],b[N],c[N],d[N],dist[N],tot=1,inf=1e8;
void ade(int u,int v,int c){
	e[++tot]=(Edge){v,head[u],c};head[u]=tot;
	e[++tot]=(Edge){u,head[v],0};head[v]=tot;
	//cout<<"ade "<<u<<' '<<v<<' '<<c<<endl;
}
bool bfs()
{
	queue<int> q; q.push(s);
	memset(dist,7,sizeof(dist)); dist[s]=0;
	while(!q.empty()){
		int u=q.front(); q.pop();
		for(int i=head[u];i;i=e[i].nex){
			int v=e[i].to,cap=e[i].cap;
			if(dist[v]>inf&&cap){
				dist[v]=dist[u]+1;
				q.push(v);
			}
		}
	}
	return dist[t]<inf;
}
int dfs(int u,int maxf)
{
	if(u==t||!maxf) return maxf;
	int ret=0;
	for(int i=head[u];i;i=e[i].nex){
		int v=e[i].to,cap=e[i].cap;
		if(dist[v]==dist[u]+1&&cap){
			int now=dfs(v,min(cap,maxf-ret));
			e[i].cap-=now; e[i^1].cap+=now; ret+=now;
			if(ret==maxf) break;
		}
	}
	if(!ret) dist[u]=-1;
	return ret;
}
int dinic()
{
	int ret=0,flow=0;
	while(bfs()){
		//for(int i=s;i<=t;i++) cout<<dist[i]<<' '; cout<<endl;
		while(flow=dfs(s,inf))
		  ret+=flow;//cout<<flow<<endl;
		//cout<<"gg"<<endl;
	}
	return ret;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);
	//cout<<"pp"<<endl;
	for(int i=1;i<=n;i++) scanf("%d%d",&c[i],&d[i]);
	//cout<<"22"<<endl;
	s=0; t=2*n+1; tot=1;
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=n;j++)
		if(a[i]<c[j]&&b[i]<d[j])
		  ade(i,j+n,1);
	for(int i=1;i<=n;i++) ade(s,i,1),ade(i+n,t,1);
	printf("%d\n",dinic());
	return 0;
}


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

using namespace std;

int main() {
	string input;
	cin >> input;

	if (input == "Sunny") {
		cout << "Cloudy" << endl;
	} else if (input == "Cloudy") {
		cout << "Rainy" << endl;
	}
	else {
		cout << "Sunny" << endl;
	}
	


	return 0;
}


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

int main()
{
  long int i,j,n,k,m=0,x,y,z;
  cin>>n;
  vector<long int>a(n);
  vector<long int>b(n);
  vector<long int>c(n);
  for(i=0;i<n;i++)
   {
    cin>>a[i];
    cin>>b[i];
    cin>>c[i];
   }
  vector<vector<long int>>v(n,vector<long int>(3));
  v[0][0]=a[0];
  v[0][1]=b[0];
  v[0][2]=c[0];
  for(i=1;i<n;i++)
  {
    v[i][0]=max(v[i-1][1],v[i-1][2])+a[i];
    v[i][1]=max(v[i-1][0],v[i-1][2])+b[i];
    v[i][2]=max(v[i-1][0],v[i-1][1])+c[i];
  }
  cout<<max(v[n-1][0],max(v[n-1][1],v[n-1][2]))<<"\n";
 return 0;
}



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

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}
void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}


#define incID(i, l, r) for(int i = (l); i < (r); i++)
#define inc(i, n) incID(i, 0, n)
template<typename T> bool setmin(T &a, T b) { if(a <= b) { return false; } else { a = b; return true; } }
template<typename T> bool setmax(T &a, T b) { if(b <= a) { return false; } else { a = b; return true; } }


// ---- ----

int n, k;
forward_list<int> vec[100000];
bool has[100000];
int mi[100000];
int ma[100000];

void prod(int x, int y) {
	if(has[y]) {
		bool flag = true;
		if(has[x] && (mi[x] - mi[y]) % 2 == 0) { flag = false; }
		setmax(mi[x], mi[y] - 1);
		setmin(ma[x], ma[y] + 1);
		has[x] = true;
		if(mi[x] > ma[x]) { flag = false; }
		if(! flag) {
			puts("No");
			exit(0);
		}
	}
}

bool dfs(int node, int pre) {
	if(pre != -1) { prod(node, pre); }
	for(auto && e : vec[node]) {
		if(e != pre) {
			dfs(e, node);
			prod(node, e);
		}
	}
}

int main() {
	reader(&n);
	inc(i, n - 1) {
		int a, b;
		reader(&a, &b);
		a--; b--;
		vec[a].push_front(b);
		vec[b].push_front(a);
	}
	fill(mi, mi + n, -1000000);
	fill(ma, ma + n,  2000000);
	reader(&k);
	inc(j, k) {
		int v, p;
		reader(&v, &p);
		v--;
		mi[v] = p;
		ma[v] = p;
		has[v] = true;
	}
	
	dfs(0, -1);
	dfs(0, -1);
	
	puts("Yes");
	inc(i, n) { writerLn(mi[i]); }
	
	return 0;
}


Measured memory_bytes: 11904
from collections import deque
N = int(input())
S = list(input())
T = deque(S[:])
ins = []
pointer = 0
a = 0
for i in range(N):
  if S[i] == ')':
    if pointer >= 1:
      pointer -= 1
    else:
      T.appendleft('(')
  else:
    pointer += 1
  
a = 0
b = 0
for t in T:
  if t == ')':
    b += 1
  else:
    a += 1

for i in range(max(a-b, 0)):
  T.append(')')
print(''.join(T))


Measured memory_bytes: 38256
#pragma region RegionDefs
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "boost/multi_array.hpp"
#define rep(i,n) for(int i=0,i##_len=(n);i<i##_len;++i)
#define reps(i,j,n) for(int i=(j),i##_len=(n);i<i##_len;++i)
#define repr(i,n) for(int i=(n);i>=0;--i)
#define all(x) begin(x),end(x)
using namespace std;
template<class T=int> using P  = pair<T, T>;
template<class T=int> using V  = vector<T>;
template<class T=int> using PQ = priority_queue<T>;
template<class T=int> using PQG = priority_queue<T, V<T>, greater<T>>;
typedef long long ll;
const int INF = 1e9;
const ll MOD = 1000000007LL;
void in() {}
template<class Head, class... Tail>
void in(Head&& head, Tail&&... tail)
{
    cin >> head;
    in(move(tail)...);
}
#define IN(...) int __VA_ARGS__; in(__VA_ARGS__)
//オーバーフロー対策
#define INL(...) ll __VA_ARGS__; in(__VA_ARGS__)
#define INS(T, ...) T __VA_ARGS__; in(__VA_ARGS__)
#define VIN(T, v, n) V<T> v(n); for(auto& _elem:v)cin>>_elem
template<class T>bool chmax(T &a, const T &b) {if (a<b) {a=b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if (a>b) {a=b; return 1;} return 0;}
#define y0 y__0
#define y1 y__1
#define j0 j__0
#define j1 j__1
#pragma endregion RegionDefs

int point(int s)
{
    if (s == 1) return 300000;
    if (s == 2) return 200000;
    if (s == 3) return 100000;
    return 0;
}

void solve()
{
    IN(x, y);
    int p = 0;
    if (x == 1 && y == 1) p = 400000;
    p += point(x) + point(y);
    cout << p << endl;
}

int main()
{
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(numeric_limits<double>::max_digits10);

    solve();

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
#include<functional>
#include<stack>
#include<utility>
#include<map>

using namespace std;

int main() {
	int n, a[100],al=0,bo=0;
	cin >> n;
	for (int i = 0; i < n; i++)cin >> a[i];
	sort(a, a + n);
	for (int i = 0; i < n; i++) {
		if (i % 2 == 0)al += a[i];
		else bo += a[i];
	}
	cout << abs(al - bo) << endl;
	return 0;
}

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

vector<pair<long long,long long> >arr;

int main()
{
    long long temp[5],i,value,yen=0;
    double liter[5],bottle;
    for(i=3;i>=0;i--)
    {
        cin>>temp[i];
        temp[i]=temp[i]<<i;
        //cerr<<temp[i]<<endl;
        arr.push_back(make_pair(temp[i],i));
    }
    liter[3]=0.25;
    for(i=2;i>=0;i--)
    {
        liter[i]=liter[i+1]*2;
        //cerr<<i<<" "<<liter[i]<<endl;
    }
    sort(arr.begin(),arr.end());
    cin>>bottle;
    for(i=0;i<4 and bottle>0;i++)
    {
        //cerr<<arr[i].first<<" "<<arr[i].second<<" "<<(arr[i].first>>arr[i].second)<<endl;
        arr[i].first=(arr[i].first>>arr[i].second);
        value=bottle/liter[arr[i].second];
        bottle-=value*liter[arr[i].second];
        yen+=value*arr[i].first;
        //cerr<<yen<<" "<<bottle<<" "<<value<<" "<<liter[arr[i].second]<<endl;
    }
    cout<<yen<<endl;
    return 0;
}


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

using namespace std;

#define REP(i,m) for(int i=0; i<m; i++)
#define FOR(i,n,m) for(int i=n; i<m; i++)
#define INF 1000000007
#define INFL (1LL << 60)
#define MOD 998244353
#define ALL(v) v.begin(),v.end()
#define pb push_back
#define ll long long int
#define P pair<ll, ll>

bool c(pair<string, int> p1, pair<string, int> p2){
	if(p1.first != p2.first) return p1.first < p2.first;
	return p1.second > p2.second;
}

int main(){
	int n;
	cin >> n;
	pair<string, int> l[n], m[n];
	REP(i, n){
		string s;
		int p;
		cin >> s >> p;
		l[i] = {s, p};
	}
	REP(i, n) m[i] = l[i];
	sort(l, l+n, c);
	int ans[n];
	REP(i, n){
		REP(j, n){
			if(m[i] == l[j]) ans[j] = i+1;
		}
	}
	REP(i, n) cout << ans[i] << endl;
	return 0;
} 


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define ll long long
#define endl "\n"
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define hell 1000000007
#define ff first
#define ss second
#define pii pair<ll,ll>
#define upd upper_bound
#define lbd lower_bound
#define vi vector<ll>
#define vii vector<pii>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pi acos(-1.0)

using namespace std;
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define N 200005

ll i=0,j=0;

ll powr(ll a,ll b)
{
    ll i=0;
    ll ans=1;
    for(i=1;i<=b;i++)
    {
        ans*=a;
    }
    return ans;
}

int main()
{
    IOS;
    ll n;
    cin>>n;
    ll arr[n+1];
    ll brr[n+1];
    ll crr[n+1];
    for(i=1;i<=n;i++)
    {
        cin>>arr[i]>>brr[i]>>crr[i];
    }
    ll dp[n+1][4];
    dp[1][1]=arr[1];
    dp[1][2]=brr[1];
    dp[1][3]=crr[1];
    for(i=2;i<=n;i++)
    {
        for(j=1;j<=3;j++)
        {
            if(j==1)
            {
                dp[i][j]=max(dp[i-1][2]+arr[i],dp[i-1][3]+arr[i]);
            }
            else if(j==2)
            {
                dp[i][j]=max(dp[i-1][1]+brr[i],dp[i-1][3]+brr[i]);
            }
            else
            {
                dp[i][j]=max(dp[i-1][2]+crr[i],dp[i-1][1]+crr[i]);
            }
        }
    }
    cout<<max({dp[n][1],dp[n][2],dp[n][3]})<<endl;
}



Measured memory_bytes: 5760
import math

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True
  
N = int(input())

while is_prime(N) == False:
  N = N+1
print(int(N))

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <cassert>
using namespace std;

#define GET_ARG(a,b,c,F,...) F
#define REP3(i,s,e) for (i = s; i <= e; i++)
#define REP2(i,n) REP3 (i,0,(int)(n)-1)
#define REP(...) GET_ARG (__VA_ARGS__,REP3,REP2) (__VA_ARGS__)
#define RREP3(i,s,e) for (i = s; i >= e; i--)
#define RREP2(i,n) RREP3 (i,(int)(n)-1,0)
#define RREP(...) GET_ARG (__VA_ARGS__,RREP3,RREP2) (__VA_ARGS__)
#define DEBUG(x) cerr << #x ": " << x << endl

int main(void) {
    int i, k, t;
    cin >> k >> t;
    int mx = 0;
    REP (i,t) {
        int a;
        cin >> a;
        mx = max(mx,a);
    }
    if (mx <= (k + 1) / 2)
        cout << 0 << endl;
    else
        cout << (mx - (k + 1) / 2) * 2 - (1 - k % 2) << endl;
    return 0;
}


Measured memory_bytes: 256
import Data.List

main :: IO ()
main = sameIntegersDo

sameIntegers abcs
    | bRem == 0 && aRem == 0    = bN + aN
    | bRem == 1 && aRem == 1    = bN + aN + 1
    | otherwise                 = bN + aN + 2
    where
        [a,b,c] = sort abcs
        (bN, bRem) = (c - b) `divMod` 2
        (aN, aRem) = (c - a) `divMod` 2

sameIntegersDo = do
    abcs <- map read . words <$> getLine
    print $ sameIntegers abcs

Measured memory_bytes: 508
#include <vector>
#include <iostream>
#include <cmath>

using namespace std;

bool IsPrime(int x) {
    if (x < 2) {
        return false;
    }

    int sq = sqrt(x);

    for (int i = 2; i <= sq; ++i) {
        if (x % i == 0) {
            return false;
        }
    }

    return true;
}

int main() {
    int n;
    int ans = 0;
    cin >> n;

    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        if (IsPrime(x)) {
            ans++;
        }
    }

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


Measured memory_bytes: 3076
n = gets.to_i
h = gets.split.map(&:to_i)

dp = Array.new(n)
dp[0] = 0
dp[1] = (h[0] - h[1]).abs
2.upto(n - 1) { |i| dp[i] = [dp[i - 2] + (h[i - 2] - h[i]).abs, dp[i - 1] + (h[i - 1] - h[i]).abs].min }

puts dp[n - 1]

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

using namespace std;
using ll = long long;

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

  int n;
  cin >> n;
  vector<ll> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  ll allxor = 0;
  for (auto x : a)
    allxor ^= x;

  for (auto x : a) {
    cout << (allxor ^ x) << " ";
  }
  cout << endl;

  return 0;
}


Measured memory_bytes: 4736
'''
ITP-1_6-D
 ??????????????¨????????????
n??mn??m  ????????? AA ??¨???m??1m??1 ??????????????????bb ??????????????????AA ??¨ bb ?????????????????????????????°????????????????????????????????????

?¬????????????? mm ????????°??????????????????????????? m??1m??1????????????????????¨???????????????

b=??????????????????b1b2:bm??????????????????
b=(b1b2:bm)
?¬????????????? nn ????????°??????????????????????????? mm ????¨?????????????????????? n??mn??m ???????????¨???????????????

A=??????????????????a11a21:an1a12a22:an2......:...a1ma2m:anm??????????????????
A=(a11a12...a1ma21a22...a2m::::an1an2...anm)
??????????????????????????????????????????????????°????????¨???????´???¨?????????m??1m??1 ?????????????????? bb ???????????? ii ?????????????´???? bi(i=1,2,...,m)bi(i=1,2,...,m)???n??mn??m ????????? AA ?????? n??mn??m ??????????´????????????????ii ??? jj ?????????????´???? aij(i=1,2,...,n,j=1,2,...,m)aij(i=1,2,...,n,j=1,2,...,m)??§??????????????????

n??mn??m????????? AA ??¨m??1m??1?????????????????? bb ????????????n??1n??1?????????????????? cc ??¨?????????cc ??? ii ?????????????´? cici ????¬?????????§??????????????????

ci=???j=1maijbj=ai1b1+ai2b2+...+aimbm
???Input
???????????? nn ??¨ mm ????????????????????§??????????????????????¶???? nn ???????????? AA ???????´? aijaij ???
?????????????????§??????????????????????¶???? mm ?????????????????? bb ???????´? bibi ?????????????????????????????????????????????
???Output
????????? nn ???????????????????????????????????? cc ???????´? cici ???????????????????????????????????????????????????
'''
n, m = [int(cnt0) for cnt0 in input().split()]
matrixData = []
for i in range(n):
    # append | result = result + [a]
    matrixData.append([int(cnt1) for cnt1 in input().split()])
    
vector = []
for cnt2 in range(m):
    vector.append(int(input()))
    
for cnt3 in range(n):
    outputValue = 0
    for cnt4 in range(m):
        outputValue += ((matrixData[cnt3][cnt4]) * (vector[cnt4]))
    print(outputValue)

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

int A; int B[3];
void input()
{
    cin >> A;
    B[0] = (A % 1000) / 100;
    B[1] = (A % 100) / 10;
    B[2] = A % 10;
    A /= 1000;
}

void solve()
{
    for (int i = 0; i < (1<<3); ++i){
        int sum = A;
        char op[3];
        for (int j = 0; j < 3; ++j){
            if (i & (1<<j)){
                op[j] = '+';
                sum += B[j];
            }
            else {
                op[j] = '-';
                sum -= B[j];
            }
        }
        if (sum == 7){
            cout << A << op[0] << B[0] << op[1] << B[1] << op[2] << B[2] << "=7" << endl;
            break;
        }
    }
}

int main()
{
    cin.tie();
    ios::sync_with_stdio(false);
    // int ti = clock();
    input();
    solve();
    // printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
    return 0;
}

Measured memory_bytes: 3628
#include<iostream>
#include<vector>
using namespace std;
int main() {
	int n;
	int ans = 0;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int ic = i;
		int count = 0;
		while (ic >= 10) {
			ic /= 10;
			count++;
		}
		if (count % 2 == 0)ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
    std::deque<int> deq;
    int n,a,tmp,hoge;
    hoge=32;
    tmp=0;
    while (cin>>n) {
        if (n==0) {
            break;
        } else {
            for (int i=0;i<n;i++) {
                cin>>a;
                deq.emplace_back(a);
            }
            while (n>1) {
                hoge=hoge-((hoge-1)%5);
                cout<<hoge<<endl;
                hoge=hoge-deq[tmp];
                if (hoge<=0) {
                    cout<<0<<endl;
                    break;
                } else {
                    cout<<hoge<<endl;
                    if (tmp!=n-1) {
                        tmp++;
                    } else {
                        tmp=0;
                    }
                }
            }
        }
        hoge=32;
        tmp=0;
        deq.clear();
    }
}



Measured memory_bytes: 3076
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <climits>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define ALL(A)		(A).begin(),(A).end()
#define DUMP(A)    cout<<#A<<"="<<(A)<< endl
#define SIZE(A)    (int)((A).size())
using namespace std;
typedef long long ll;

int main(){
    int n,m,s,g1,g2;
    for(;;){
        int war[100][100];
        scanf("%d%d%d%d%d",&n,&m,&s,&g1,&g2);
        if(n==0&&m==0&&s==0&&g1==0&&g2==0) break;
        s--;g1--;g2--;
        int fr,to,co;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(i==j) war[i][j]=0;
                else war[i][j]=1000000;
            }
        }
        for(int i=0;i<m;i++){
            scanf("%d%d%d",&fr,&to,&co);
            fr--;to--;
            war[fr][to]=co;
        }
        for(int k=0;k<n;k++){
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    war[i][j]=min(war[i][j],war[i][k]+war[k][j]);
                }
            }
        }
        int mi=INT_MAX;
        for(int i=0;i<n;i++){
            mi=min(mi,war[s][i]+war[i][g1]+war[i][g2]);
        }
        printf("%d\n",mi);
    }
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pll;
const int N=1e6;
ll v[N+10];
int main()

{

    ll t;
    cin>>t;
    ll a=0,b=0,c=0,d=0;
    while(t--)
    {

        string str;

        cin>>str;

        if(str=="AC")
            a++;

        else if(str=="WA")
            b++;

        else if(str=="TLE")
            c++;

        else
            d++;
    }

    cout<<"AC"<<" x "<<a<<endl;

    cout<<"WA"<<" x "<<b<<endl;

    cout<<"TLE"<<" x "<<c<<endl;

    cout<<"RE"<<" x "<<d<<endl;
}


Measured memory_bytes: 3604
#include <iostream>
#include<iomanip>
#include <map>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <utility>
#include <queue>
#define INF 1e16
#define rep(i,n) for(int i=0;i<n;i++)
#define NO cout<<"NO"<<endl;
#define YES cout<< "YES"<<endl;
#define No cout<< "No"<<endl;
#define Yes cout<< "Yes"<<endl;
#define all(a) a.begin(),a.end()
#define P pair<int,int>
#define space ' '
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

//(int)'a'=97 (int)'A'=65 (int)'1'=49
//おまじない

const int maxn = 100000;

int main(){
    
    ll w,h;
    cin >> h>>w;
    ll ans = INF;
    for(ll i=1;i<=w-1;i++){
        ll w1 = i;
        ll w2 = (w-i)/2;
        ll w3 = w-(w1+w2);
        ll h1 = h/2;
        ll h2 = h-h1;
        if(i<=w-2)ans=min(ans,(max(max(w1,w2),w3)-min(min(w1,w2),w3))*h);
        ans=min(ans,max(max(i*h,h1*(w-i)),h2*(w-i))-min(min(i*h,h1*(w-i)),h2*(w-i)));
    }
    swap(w,h);
    
    for(ll i=1;i<=w-2;i++){
        ll w1 = i;
        ll w2 = (w-i)/2;
        ll w3 = w-(w1+w2);
        ll h1 = h/2;
        ll h2 = h-h1;
        if(i<=w-2)ans=min(ans,(max(max(w1,w2),w3)-min(min(w1,w2),w3))*h);
        ans=min(ans,max(max(i*h,h1*(w-i)),h2*(w-i))-min(min(i*h,h1*(w-i)),h2*(w-i)));
    }
    
    cout << ans<<endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
string s;
int former,latter;
int main(){
  cin >> s;
  for(int i=0;i<s.size();i++){
    if(s[i]=='A'){
      former=i;
      break;
    }
    }
    for(int i=s.size()-1;i>=0;i--){
      if(s[i]=='Z'){
        latter=i;
        break;
      }
      }
      cout << latter-former+1 << endl;
  return 0;
}


Measured memory_bytes: 640
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <algorithm>
#include <cassert>
#include <cfloat>
#include <complex>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define repLRE(i, l, r) for (ll i = (l); i <= (r); ++i)
#define rrepLRE(i, l, r) for (ll i = (l); i >= (r); --i)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define Lower_bound(v, x) \
  distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) \
  distance(v.begin(), upper_bound(v.begin(), v.end(), x))

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;
using T = tuple<ll, ll, ll>;
using vll = vector<ll>;
using vP = vector<P>;
using vT = vector<T>;
using vvll = vector<vector<ll>>;
using vvP = vector<vector<P>>;
using dqll = deque<ll>;

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

/* Macros reg. ends here */

const ll INF = 1LL << 50;

void dfs(vvll& to, vector<bool>& rblFrom1, ll v) {
  if (rblFrom1[v]) return;
  rblFrom1[v] = true;
  for (auto u : to[v]) {
    dfs(to, rblFrom1, u);
  }
}

void rdfs(vvll& ot, vector<bool>& rblToN, ll v) {
  if (rblToN[v]) return;
  rblToN[v] = true;
  for (auto u : ot[v]) {
    rdfs(ot, rblToN, u);
  }
}

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cout << fixed << setprecision(15);

  ll n, m;
  cin >> n >> m;

  vector<bool> rblFrom1(n, false);
  vector<bool> rblToN(n, false);
  vvll to(n);
  vvll ot(n);

  vT eds(m);
  rep(i, m) {
    ll a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    c = -c;
    eds[i] = T(a, b, c);
    to[a].push_back(b);
    ot[b].push_back(a);
  }

  dfs(to, rblFrom1, 0);
  rdfs(ot, rblToN, n - 1);

  vector<bool> ok(n);
  rep(i, n) ok[i] = rblFrom1[i] && rblToN[i];

  vll d(n, INF);
  d[0] = 0;
  bool upd = true;
  ll step = 0;
  while (upd) {
    upd = false;
    for (auto e : eds) {
      ll a, b, c;
      tie(a, b, c) = e;
      if (!ok[a]) continue;
      if (!ok[b]) continue;
      ll newD = d[a] + c;
      if (newD < d[b]) {
        d[b] = newD;
        upd = true;
      }
    }
    step++;
    if (step > n) {
      puts("inf");
      return 0;
    }
  }

  ll ans = -d[n - 1];
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
int main() {
    long long N, ans;
    cin >> N;
    long long v[N+1][3];
    long long dp[N+1][3];
    for (long long i = 1; i <= N; i++) cin >> v[i][0] >> v[i][1] >> v[i][2];
    for (long long i = 0; i <= N; i++) {
        for (long long j = 0; j< 3; j++){
            dp[i][j] = -1;
        }
    }
    for (int i = 0; i < 3; i++) dp[0][i] = 0;
    for (long long i = 1; i <= N; i++) {
        for (long long j = 0; j < 3; j++){
            chmax(dp[i][j], dp[i-1][(j+1)%3] + v[i][j]);
            chmax(dp[i][j], dp[i-1][(j+2)%3] + v[i][j]);
        }
    }
    ans = dp[N][0];
    chmax(ans, dp[N][1]);
    chmax(ans, dp[N][2]);
    cout << ans << endl;
}


Measured memory_bytes: 8236
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>

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

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

typedef long long ll;

using namespace std;
using vec=vector<ll>;
using mat=vector<vec>;
int mod=1e9+7;
mat mul(mat a,mat b)
{
  mat res(a.size(),vec(b[0].size(),0));
  int ha=a.size(),h=b.size(),w=b[0].size();
  for(int i=0;i<ha;i++)
  {
    for(int k=0;k<h;k++)
    {
      for(int j=0;j<w;j++)
      {
        res[i][j]+=a[i][k]*b[k][j];
        res[i][j]%=mod;
      }
    }
  }
  return res;
}

mat pow(mat &a,ll n)
{
  mat b(a.size(),vec(a.size(),0));
  for(int i=0;i<a.size();i++)
  {
    b[i][i]=1;
  }
  while(n>0)
  {
    if(n&1)b=mul(b,a);
    a=mul(a,a);
    n>>=1;
  }
  return b;
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n,k;
  cin>>n>>k;
  mat p(n,vector<ll>(n,0));
  rep(i,n)rep(j,n)cin>>p[i][j];
  mat x(n,vector<ll>(1,1));
  auto q=pow(p,k);
  mul(q,x);
  int res=0;
  rep(i,n)rep(j,n){res+=q[i][j];res%=mod;}
  cout<<res<<endl;




  return 0;

}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i = (m); i <= (n); i++)
#define zep(i,m,n) for(ll i = (m); i < (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,m,n) for(int i = (m); i <= n; i++){cout << (x[i]) << " ";} cout<<endl;

int main(){
    cin.tie(0); ios::sync_with_stdio(false);
    
    ll x; cin >> x;
    print(1 - x)
    
    return 0;
}

Measured memory_bytes: 3612
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

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

int main() {
	int n;
	while(cin >> n && n) {
		vector<int> a,b;
		bool used[205];
		memset(used, 0, sizeof(used));

		int x;
		rep(i, n) {
			cin >> x;
			used[x] = true;
			a.push_back(x);
		}

		sort(a.begin(), a.end());

		REP(i, 1, 2*n + 1) {
			if(used[i]) continue;
			b.push_back(i);
		}

		int res = 0, i = 0;
		while(true) {
			if(a.size() == 0 || b.size() == 0) break;

			if(i % 2 == 0) {
				vector<int>::iterator ite = upper_bound(a.begin(), a.end(), res);
				if(ite == a.end()) {
					res = 0;
				} else {
					res = *ite;
					a.erase(ite);
				}
			} else {
				vector<int>::iterator ite = upper_bound(b.begin(), b.end(), res);
				if(ite == b.end()) {
					res = 0;
				} else {
					res = *ite;
					b.erase(ite);
				}
			}

			i++;
		}

		cout << b.size() << endl;
		cout << a.size() << endl;
	}

	return 0;
}

Measured memory_bytes: 1220
N,A,B=map(int,input().split())

if int(N) <= int(A):
  print(int(N))
elif int(N) <= int(A + B):
  print(int(A))
else:
  a = int(N//(A+B))
  b = int(N - (A+B)*a)
  c = min(b,A)
  print(a*A+c)

Measured memory_bytes: 38512
#include <algorithm>
#include <array>
#include <bitset>
#include <complex>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <queue>

using namespace std;

struct BoolName : numpunct<char> {
  string t, f;
  BoolName (string t = "Yes", string f = "No") : t(t), f(f) {}
  string do_truename() const {return t;}
  string do_falsename() const {return f;}
};

struct Initializer {
  Initializer() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(15) << boolalpha;
    cout.imbue(locale(cout.getloc(), new BoolName));
  }
} initializer;

template<typename T> istream& operator>>(istream &s, vector<T> &v) {
  for (T &t : v) s >> t;
  return s;
}

template<typename T> ostream& operator<<(ostream &s, const vector<T> &v) {
  for (const T &t : v) s << t << endl;
  return s;
}

void set_bool_name(string t, string f) {
  cout.imbue(locale(cout.getloc(), new BoolName(t, f)));
}

int main() {
  int n;
  cin >> n;
  if (n == 1) {
    cout << "Hello World" << endl;
  } else {
    int a, b;
    cin >> a >> b;
    cout << a + b << endl;
  }
}



Measured memory_bytes: 256
/*Read the problem carefully before starting to work on it*/
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//using namespace boost::multiprecision;
//#include <ext/pb_ds/assoc_container.hpp> 
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;

#define pb push_back
#define eb emplace_back
#define mp(x,y) make_pair(x,y)
#define mod 1000000007

double PI=3.1415926535897932384626;

//template<typename T> T power(T x,T y,ll m=mod){T ans=1;while(y>0){if(y&1LL) ans=(ans*x)%m;y>>=1LL;x=(x*x)%m;}return ans%m;}

//typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ost;

#define fi first
#define se second

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll A,B,M;
	cin>>A>>B>>M;
	vector<ll>a(A,0),b(B,0);
	for(ll i=0;i<A;i++)
		cin>>a[i];
	for(ll i=0;i<B;i++)
		cin>>b[i];
	ll one=*min_element(a.begin(),a.end());
	ll two=*min_element(b.begin(),b.end());
	ll ans=one+two;
	for(ll i=0;i<M;i++)
	{
		ll x,y,c;
		cin>>x>>y>>c;
		x--;y--;
		ll val=a[x]+b[y]-c;
		ans=min(ans,val);
	}
	cout<<ans;
    return 0;
}


//252908XL

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define int long long
//Compiler version g++ 6.3.0

deque<int> d;
signed main()
{
  int n,t;cin>>n;
  for(int i=1;i<=n;i++){
    cin>>t;
    if(i&1){
      d.push_back(t);
    }
    else {
      d.push_front(t);
    }
  }
  vector<int> v;
  for(auto x: d){
    v.push_back(x);
  }
  if((n&1)){
    reverse(v.begin(),v.end());
  }
  for(auto x:v){
    cout<<x<<" ";
  }
}

Measured memory_bytes: 6000
// ALDS1_14_A/B: String search (DFA)

import java.io.PrintWriter;
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    char[] T = sc.next().toCharArray();
    char[] P = sc.next().toCharArray();
    PrintWriter pw = new PrintWriter(System.out);

    // preprocess
    int[] pi = new int[P.length + 1];
    pi[0] = -1;
    int k = -1;
    for (int i = 1; i <= P.length; ++i) {
      while (k >= 0 && P[k] != P[i - 1]) k = pi[k];
      pi[i] = ++k;
    }

    // search
    int j = 0;
    for (int i = 1; i <= T.length; ++i) {
      while (j >= 0 && P[j] != T[i - 1]) j = pi[j];
      ++j;
      if (j == P.length) {
        pw.println(i - P.length);
        j = pi[j];
      }
    }
    pw.flush();
  }
}


Measured memory_bytes: 26200
#include<bits/stdc++.h>
using namespace std;
//#define int long long
const int M=998244353,N=1000002;
int pw(int x,int y){
	int z=1;
	for (;y;y>>=1,x=1ll*x*x%M)
		if (y&1) z=1ll*z*x%M;
	return z;
}
int INV(int x){return pw(x,M-2);}
int n,i,j,a[52];
bool chk(){
	for (int i=1;i<=n;i++)
		if (a[i]!=i) return 0;
	return 1;
}
signed main(){
	scanf("%d",&n);
	for (i=1;i<=n;i++) scanf("%d",&a[i]);
	if (chk()) return puts("YES"),0;
	for (i=1;i<=n;i++)
		for (j=i+1;j<=n;j++){
			swap(a[i],a[j]);
			if (chk()) return puts("YES"),0;
			swap(a[i],a[j]);
		}
	puts("NO");
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
  ll books[100];
  ll N,K;
  ll highest=0;
  cin>>N>>K;
  for(ll i=0;i<100;i++) cin>>books[i];
  sort(books,books+N);
  reverse(books,books+N);
  for(ll i=0;i<K;i++) highest+=books[i];
  cout<<highest<<endl;
}


Measured memory_bytes: 256