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

#define N 200005
#define maxN 1000000007
#define PI 3.14159265358979
#define bb __builtin_popcount
#define ll long long
int x, y, m, n;
int a[N], b[N];
void solve() {
    cin >> m >> n >> x >> y;
    for (int i = 1; i <= m; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    for (int i = 1; i <= m; i++) x = max(x, a[i]);
    for (int i = 1; i <= n; i++) y = min(y, b[i]);
    if (x < y) cout << "No War";
    else cout << "War";
}
int main() {
    //freopen("main1.in", "r", stdin);
    //freopen("main.in", "w", stdout);
    //freopen("main.out", "w", stdout);
    solve();
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}
///Hamita


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

int main(){
  int N,K;
  cin >> N >> K;
  int a[K];
  for(int i=0;i<K;i++)
    cin >> a[i];
  for(int j=N;N<10000;j++){
    int b = j;
    bool flag=0;
    for(int m=0;m<5;m++){
    	for(int l=0;l<K;l++){
    		if(b%10 == a[l]){
        		flag = 1;
        	}
    	}
   		b = b / 10;
      	if(b == 0)
          break;
    }
    if(!flag){
    	cout << j << endl;
    	break;
    }
  }
}


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

const int N = 404, M = 1e5 + 100;

int n, m, x[M], y[M];
bool bad[N];
bitset<N> s[N];

void input() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> x[i] >> y[i];
		x[i]--;
		y[i]--;
	}
}

void ready(int v) {
	s[v][v] = true;
	for (int i = m - 1; ~i; i--) {
		int a = x[i], b = y[i];
		if (s[v][a] && s[v][b]) {
			bad[v] = true;
			return;
		}
		if (s[v][a])
			s[v][b] = true;
		if (s[v][b])
			s[v][a] = true;
	}
}

void Ready() {
	for (int v = 0; v < n; v++)
		ready(v);
}

void output() {
	int ans = 0;
	for (int u = 0; u < n; u++)
		for (int v = u + 1; v < n; v++)
			if (!(bad[u] || bad[v] || (s[u] & s[v]).count()))
				ans++;
	cout << ans << '\n';
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	input();
	Ready();
	output();
}


Measured memory_bytes: 1024
#include "iostream"
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <cstring>
#include <math.h>
#include <cctype>
#include <stack>
#include <vector>
#include <list>
#include <queue>
using namespace std;
using ll=long long;
#define mod  1000000007

int main(int argc, char const *argv[]) {
  ll n,ans=1;
  std::cin >> n;
  int prime[1010];

  for(int i=0; i<=1000; i++) prime[i]=1;

  for(int i=n; i>=1; i--){
    int a=i;
    for(int j=2; j<=n; j++){
      while(a%j==0){
        prime[j]++;
        a/=j;
      }
    }
  }
  for(int i=0; i<=n; i++){
    ans=(ans*prime[i])%mod;
  }

  std::cout << ans << '\n';

  return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる
mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

A, B, H, M = LI()

pi = math.pi
h_p = [A * math.cos(2 * pi * (H * 60 + M) / 720), A * math.sin(2 * pi * (H * 60 + M) / 720)]
m_p = [B * math.cos(2 * pi * M / 60), B * math.sin(2 * pi * M / 60)]

# print(h_p, m_p)
length = ((h_p[0] - m_p[0])**2 + (h_p[1] - m_p[1])**2)**0.5
print(length) 


Measured memory_bytes: 10972
N,Q = map(int, input().split())
Edge = [set() for _ in range(N+1)]
for i in range(N-1):
  e1,e2 = map(int, input().split())
  Edge[e1].add(e2)
  Edge[e2].add(e1)
Counter = [0] * (N+1)
for i in range(Q):
  p,x = map(int, input().split())
  Counter[p] += x

#print(Edge)
  
Visited = [False] * (N+1)
stack = {1}
while (stack):
  stack2 = set()
  for i in range(len(stack)):
    e1 = stack.pop()
    for e2 in Edge[e1]:
      if not Visited[e2]:
        Counter[e2] += Counter[e1]
        stack2.add(e2)
    Visited[e1] = True
  stack = stack2
  #print(Visited)

print(*[Counter[i] for i in range(1,N+1)])


Measured memory_bytes: 132844
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cassert>
#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <sstream>
#include <bitset>
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define invrepr(i,a,b) for(int i=b-1;i>=a;i--)
#define invrep(i,n) invrepr(i,0,n)

using namespace std;
typedef long long ll;
const ll MOD=1e9+7;

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


    ll ans=0;
    ll anss =0;
    ll count=0;
    ll i,j,h;
    ll Q,N,K,P,A,B;
    
    long double a, b;
    long double x;

    vector<ll> aa;
    string S;

    ll flag=0;
    ll temp=0;

    cin  >> K>>A>>B;

    for(i=A;i<B+1;i++){
        if (i%K==0){
            cout << "OK"<<endl;
            return 0;
        }
    }
    cout << "NG"<<endl;

    return 0;
}

Measured memory_bytes: 3652
#include<stdio.h>
int linsearch(int, int A[], int);

int main(){
  int n, i, q, c = 0;
  scanf("%d", &n);
  int S[n];
  for(i = 0; i < n; i++) scanf("%d", &S[i]);
  scanf("%d", &q);
  int T[q];
  
  for(i = 0; i < q; i++) {
    scanf("%d", &T[i]);
    if(linsearch(n, S, T[i]) == 1) c += 1;
    
  }
  printf("%d\n", c);

  return 0;
}

int linsearch(int n, int A[], int key){
  int i = 0;

  while(1){
    if(A[i] == key) return 1;
    i++;
    if(i == n) break;
  }
  return -1;
}



Measured memory_bytes: 2108
n = int(input())
*ls_a, = input().split()
ls_b = ls_a[:]
for i in range(n):
    for j in range(n-1, i, -1):
        if ls_a[j][1:] < ls_a[j-1][1:]:
            ls_a[j], ls_a[j-1] = ls_a[j-1], ls_a[j]

print(*ls_a)
print("Stable")

for i in range(n):
    minj = i
    for j in range(i, n):
        if ls_b[j][1:] < ls_b[minj][1:]:
            minj = j
    ls_b[i], ls_b[minj] = ls_b[minj], ls_b[i]
print(*ls_b)
if ls_a == ls_b:
    print("Stable")
else:
    print("Not stable")



Measured memory_bytes: 5604
use std::io;
use std::str::FromStr;

type Pair = (u64, u64);

fn input_tuple() -> (u64, u64) {
    let mut line: String = String::new();
    io::stdin().read_line(&mut line);
    let vec: Vec<u64> = line.split_whitespace().map(|s| s.parse().unwrap()).collect();
    (vec[0], vec[1])
}

fn main() {
    let (n, m) = input_tuple();
    let mut prefectures: Vec<Vec<Pair>> = vec![Vec::new(); n as usize];
    for i in 0..m {
        let (p, y) = input_tuple();
        prefectures[p as usize - 1].push((i, y));
    }

    for i in 0..n {
        prefectures[i as usize].sort_by(|x, y| x.1.cmp(&y.1));
    }
    // println!("{:?}", prefectures);
    let mut ans = vec![0; m as usize];
    for i in 0..n as usize {
        for j in 0..prefectures[i].len() {
            ans[prefectures[i][j].0 as usize] = (i+1) * 1_000_000 + j+1;
        }
    }
    for a in ans {
        println!("{: >012}", a);
    }
}


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

int main() {
  int n,ans=0; cin>>n;
  vector<int> a(n);
  for(int i=0; i<n; i++) cin>>a[i];
  for(int i=0; i<n; i++){
    for(int j=i; j<n; j++){
      ans = max(ans,abs(a[i]-a[j]));
    }
  }
  cout<<ans;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
string s;
ll ans,cnt[2200],num,t=1;
int main()
{
   cin>>s;
   for(int i=s.size()-1;i>=0;i--)
   {
   	   num=(num+(s[i]-'0')*t)%2019;
   	   cnt[num]++;
   	   t=t*10%2019;
   }
   for(int i=1;i<2019;i++)
   {
   	   if(cnt[i]>1) ans+=(cnt[i]-1)*cnt[i]/2;
   }
   ans+=cnt[0]*(cnt[0]+1)/2;
   cout<<ans;
return 0;
}


Measured memory_bytes: 3796
#include <bits/stdc++.h>
    using namespace std;
    int main() {
      int n=0;
      int x=0;
      int t=0;
      
      cin >> n >> x >> t;
     
      int count = 0;
      
      count = n/x;
      if(n%x > 0){
       count++; 
      }
      
      cout << count*t <<endl;
    }

Measured memory_bytes: 3608
import sys

def knappack(N, W, vs, ws):
    dp = [0] * (W + 1)
    for i in range(N):
        for j in range(W, ws[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - ws[i]] + vs[i])
            
    return dp[-1]
    
    
if __name__ == '__main__':
    line = sys.stdin.readline()
    Nstr, Wstr = line.split()
    N, W = int(Nstr), int(Wstr)
    vs, ws = [], []
    for i in range(N):
        line = sys.stdin.readline()
        v, w = line.split()
        v, w = int(v), int(w)
        vs.append(v)
        ws.append(w)
    sys.stdout.write(str(knappack(N, W, vs, ws)))
    sys.stdout.write('\n')
    

Measured memory_bytes: 4748
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
using namespace std;

int main() {
    int N,K; cin >> N >> K;
    long long c[100010]; REP(i,N) cin >> c[i];
    long long ans=999999999;
    for(int i=0;i<N-K+1;i++){
        long long t=999999999;
        if (c[i]<0 && c[i+K-1]>0){
            t = min((abs(c[i])+abs(c[i+K-1]-c[i])),
            (abs(c[i+K-1])+abs(c[i+K-1]-c[i])));
        }
        else {
            t= max(abs(c[i]),abs(c[i+K-1]));
        }
        

        
        ans=min(ans,t);
    }
    cout << ans << endl;  

    return 0;
}

Measured memory_bytes: 1024
#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define rep(i, l, r) for (ll i = (l); i < (r); ++i)
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define vi vector<int>
#define vll vector<ll>
#define pii pair<int, int>
#define pll pair<ll, ll> 
#define pdd pair<ld, ld> 
#define pb push_back
#define reset(x,v) memset(x,v,sizeof(x))
#define mod 998244353
using namespace std;

void dfs(vector<int> adj[], int sv, vector<bool> &vis){
	vis[sv] = true;
	for(int i = 0; i < adj[sv].size(); i++){
		if(!vis[adj[sv][i]]){
			dfs(adj, adj[sv][i], vis);
		}
	}
}
ll power(ll x, ll y){  
	if(x == 1 || y == 0)
		return 1;
    ll res = 1;   
    x = x % mod; 
    if (x == 0) 
		return 0;  
    while (y > 0){  
        if (y & 1)  
            res = (res * x) % mod;  
        y = y >> 1; 
        x = (x * x) % mod;  
    }  
    return res;  
}  


int main(){
	FASTIO
	int n, x, y;
	cin >> n >> x >> y;
	vector<int> ans(n, 0);
	rep(i, 1, n + 1){
		rep(j, i + 1, n + 1){
			int d = min(j - i, abs(x - i) + 1 + abs(y - j));
			ans[d]++;
		}
	}
	rep(i, 1, n)
		cout << ans[i] << endl;
    return 0;
}


Measured memory_bytes: 3656
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5;

struct point {
  int x, y, id;
};
inline bool operator <(const point &a, const point &b) {
  return a.x < b.x || (a.x == b.x && a.y < b.y);
}

int n, a, b, d, par[N];
ll cnte[N], que[N];
point p[N];

int root(int v) {
  return (par[v] < 0) ? v : (par[v] = root(par[v]));
}

void join(int x, int y, ll val) {
  x = root(x); y = root(y);
  cnte[x] += val;
  if (x == y) return;
  if (par[x] > par[y]) swap(x, y);
  par[x] += par[y];
  cnte[x] += cnte[y];
  par[y] = x;
}

int main() {
  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  cin >> n >> a >> b;
  for (int i = 1, x, y; i <= n; ++i) {
    cin >> x >> y;
    p[i] = {x - y, x + y, i};
    par[i] = -1;
  }
  d = max(abs(p[a].x - p[b].x), abs(p[a].y - p[b].y));

  sort(p + 1, p + 1 + n);
  for (int i = 1, L = 1, R = 1; i <= n; ++i) {
    while (L <= n && (p[L].x < p[i].x + d || (p[L].x == p[i].x + d && p[L].y < p[i].y - d))) ++L;
    while (R <= n && (p[R].x < p[i].x + d || (p[R].x == p[i].x + d && p[R].y <= p[i].y + d))) ++R;
    if (L == n + 1 || R == L || p[L].x != p[i].x + d) continue;
    join(p[i].id, p[L].id, 1);
    ++que[L]; --que[R - 1];
  }
  for (int i = 1; i <= n; ++i) {
    que[i] += que[i - 1];
    if (que[i]) join(p[i].id, p[i + 1].id, que[i]);
  }

  for (int i = 1; i <= n; ++i) swap(p[i].x, p[i].y);
  sort(p + 1, p + 1 + n);
  for (int i = 1; i <= n; ++i) que[i] = 0;
  for (int i = 1, L = 1, R = 1; i <= n; ++i) {
    while (L <= n && (p[L].x < p[i].x + d || (p[L].x == p[i].x + d && p[L].y <= p[i].y - d))) ++L;
    while (R <= n && (p[R].x < p[i].x + d || (p[R].x == p[i].x + d && p[R].y < p[i].y + d))) ++R;
    if (L == n + 1 || R == L || p[L].x != p[i].x + d) continue;
    join(p[i].id, p[L].id, 1);
    ++que[L]; --que[R - 1];
  }
  for (int i = 1; i <= n; ++i) {
    que[i] += que[i - 1];
    if (que[i]) join(p[i].id, p[i + 1].id, que[i]);
  }

  cout << cnte[root(a)];
  return 0;
}

Measured memory_bytes: 3328
#include<iostream>
using namespace std;
int main(){
	int N,K;
	int l[50];
	
	int i,j;
	int A,B;
	
	cin>>N>>K;
	for(i=0;i<N;i++){
		cin>>l[i];
	}
	
	A=l[0];
	for(i=0;i<N;i++){
		for(j=0;j<N-i-1;j++){
			if(l[j]<l[j+1]){
				A=l[j];
				l[j]=l[j+1];
				l[j+1]=A;
			}
		}
	}
	B=0;
	for(i=0;i<K;i++){
		B=B+l[i];
	}
	cout<<B;

}
			
			 
			 	

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = int_fast64_t;
const int mod = 1e9 + 7;
const int inf = (1 << 30) - 1;
const ll infll = (1LL << 61) - 1;
#define fast() ios::sync_with_stdio(false), cin.tie(nullptr)
#pragma GCC target("avx2")

ll N, ans;

int main()
{
	fast();
	cin >> N;
	for (ll i = 2, M = N, z = 2; i * i <= M && N != 1; z = ++i)
	{
		while (N % z == 0)
			ans++, N /= z, z *= i;
		while (N % i == 0)
			N /= i;
	}

	cout << ans + (N != 1) << "\n";
}


Measured memory_bytes: 3700
a, b = map(float, input().split())

a = int(a)

# print(a)
# print(int(b*100))

# ans = (a * int(b * 100)) // 100
b = round(b * 100)
# print((b))
ans = (a * int(b)) // 100
# ans = (a * int(b * 100))
# ans = ans // 100

print(int(ans))
# print((999990000000001*999)//100)
# print(9.99 * 100)


Measured memory_bytes: 9092
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
using namespace std;

long long ans = 0;

int comb(int n ,int k){
    if(k == 3){
        return n*(n-1)*(n-2)/6;
    }
    else if(k == 2){
        return n*(n-1)/2;
    }
    else if(k == 1) return n;
    else return 1;
}

void solve(string s, int k){
    int n= s.size();
    if(n < k) return;
    if(k == 0){
        ans += 1;
        return;
    }
    int a = s.at(0) - '0';
    string sub = s.substr(1, string::npos);
    if(a > 0){
    ans += comb(n-1,k)*pow(9,k);
    ans += (a-1)*comb(n-1,k-1)*pow(9,k-1);
    solve(sub,k-1);
    }
    else{
        solve(sub,k);
    }
}

int main(){
    string s;
    cin >> s;
    int k;
    cin >> k;
    solve(s,k);
    cout << ans << endl;
}




Measured memory_bytes: 384
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int N;
	cin>>N;
	for(int i=0;i<N;i++){
		double x1,y1,x2,y2,x3,y3,x4,y4;
		cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4;
		if((x1==x2&&y1==y2)||(x3==x4&&y3==y4))cout<<"NO"<<endl;
		else if(fabs(x2-x1)<0.00000000001&&fabs(x4-x3)<0.00000000001)cout<<"YES"<<endl;
		else if(fabs((y2-y1)/(x2-x1)-(y4-y3)/(x4-x3))<0.0000000000001)cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0;
}
	

Measured memory_bytes: 1228
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn =500000+10;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
char s[maxn];
int q;
set<int> Set[26];
int main(){
	int n1;
	cin>>n1;
	scanf("%s", s+1);
	cin>>q;
	int n=strlen(s+1);
	for(int i = 1; i <= n; i++) 
		Set[s[i]-'a'].insert(i);
	for(int i = 0; i < q; i++) {
		int op;
		cin>>op;
		if (op == 1) {
			int p; char c;
			scanf("%d %c", &p, &c);
			int cur = s[p]-'a';
			if (Set[cur].count(p))
				Set[cur].erase(Set[cur].find(p));
			s[p]=c;
			Set[c-'a'].insert(p);
		} else {
			int l, r, ans = 0;
			scanf("%d%d", &l, &r);
			for (int j = 0; j < 26; j++) {
				int cur = *Set[j].lower_bound(l);
				if (cur >= l && cur <= r) {
					ans++;
				}
			}
			cout << ans << "\n";
		}
	}
	return 0;
}

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

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

    if (a == 1 || b == 1) {
        if (a == b) {
            cout << "Draw" << endl;
        }
        else if (a == 1) {
            cout << "Alice" << endl;
        }
        else {
            cout << "Bob" << endl;
        }
    }
    else {
        if (a == b) {
            cout << "Draw" << endl;
        }
        else if (a > b) {
            cout << "Alice" << endl;
        }
        else {
            cout << "Bob" << endl;
        }
    }

    return 0;
}


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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;

void Main()
{
	string s;
  	cin >> s;
  	map<int,int> cnt;
  	rep(i,s.size()) {
    	cnt[s[i]-'a']++;
    }
  	//for (auto m:cnt) cout << (char)('a' + m.first) << ": " << m.second << endl;
	rep(i,26) if(cnt[i]>1) {
    	puts("no");
      	return;
    }
	puts("yes");
  	return;
}

int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
	int N,q,ans=0;
  	cin >>N>>q;
  	typedef pair<string,int>x;
  	queue<x>que;
  	
  	for(int i=0;i<N;i++){
     string a; int b;
    cin >>a>>b;
    que.push(x(a,b));
    }
  	pair<string,int>p;
  	while(que.size()){
    	p=que.front();que.pop();
    	if(p.second<=q){
          	ans+=p.second;
        	cout<<p.first<<' '<<ans<<endl;
        }
    	else{
        	ans+=q;
          	p.second=p.second-q;
          	que.push(p);         
        }
    } 
}


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

int main() {
  int A;
  int B;
  int C;
  int D;
  cin >> A >> B >> C >> D;

  while (C >= 0) {
    C = C -B;
    if (C <=0){
    cout << "Yes" << endl;
      break;
    }
    A = A-D;
     if (A <=0){
    cout << "No" << endl;
      break;
    }
  }

  return 0;
}

Measured memory_bytes: 3588
from collections import defaultdict
d = defaultdict(int)

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

x = 0
y = 0

for a in A:
  d[a] += 1
  
for i in d:
  if d[i] >= 2:
    x += 1
    y += d[i] - 1
    
if y % 2 == 0:
  print(N-y)
else:
  print(N-y-1)

Measured memory_bytes: 18648
#include <inttypes.h>
#include <math.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void)
{
    intmax_t A, B, C, K;
    intmax_t ans = 0;

    scanf("%jd%jd%jd%jd", &A, &B, &C, &K);

    if (A < K) {
        ans = A;
    } else {
        ans = K;
    }
    K -= A;
    K -= B;
    if (K > 0) {
        ans -= K;
    }

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

    return 0;
}


Measured memory_bytes: 2156
/* imports all std modules {{{*/
import
  std.algorithm,
  std.array,
  std.ascii,
  std.base64,
  std.bigint,
  std.bitmanip,
  std.compiler,
  std.complex,
  std.concurrency,
  std.container,
  std.conv,
  std.csv,
  std.datetime,
  std.demangle,
  std.encoding,
  std.exception,
  std.file,
  std.format,
  std.functional,
  std.getopt,
  std.json,
  std.math,
  std.mathspecial,
  std.meta,
  std.mmfile,
  std.net.curl,
  std.net.isemail,
  std.numeric,
  std.parallelism,
  std.path,
  std.process,
  std.random,
  std.range,
  std.regex,
  std.signals,
  std.socket,
  std.stdint,
  std.stdio,
  std.string,
  std.system,
  std.traits,
  std.typecons,
  std.uni,
  std.uri,
  std.utf,
  std.uuid,
  std.variant,
  std.zip,
  std.zlib;
/*}}}*/

/* libnum {{{*/
void amax(N, Args...)(ref N x, Args y) {
  x = x.max(y);
}
void amin(N, Args...)(ref N x, Args y) {
  x = x.min(y);
}
auto maxE(R)(R r) if (isInputRange!R) {
  ElementType!R x = r.front;
  r.popFront();
  foreach (y; r) x.amax(y);
  return x;
}
auto minE(R)(R r) if (isInputRange!R) {
  ElementType!R x = r.front;
  r.popFront();
  foreach (y; r) x.amin(y);
  return x;
}
/*}}}*/


/+---test
3 3
...
...
...
---+/

/+---test
3 5
...#.
.#.#.
.#...
---+/

enum long INF = 100000000;

void main(string[] args) {
  long H, W;
  readf(" %d %d ", &H, &W);

  auto S = new bool[][](H);
  foreach (ref s; S) {
    s = readln.map!(c => c == '.').array;
  }

  auto dist = new long[][](H*W, H*W);
  foreach (ref d; dist) d[] = INF;

  foreach (y; 0..H) foreach (x; 0..W) {
    if (!S[y][x]) continue;
    dist[y*W+x][y*W+x] = 0;
    if (y && S[y-1][x]) {
      dist[y*W+x][y*W-W+x] = 1;
    }
    if (x && S[y][x-1]) {
      dist[y*W+x][y*W+x-1] = 1;
    }
    if (y+1 < H && S[y+1][x]) {
      dist[y*W+x][y*W+W+x] = 1;
    }
    if (x+1 < W && S[y][x+1]) {
      dist[y*W+x][y*W+x+1] = 1;
    }
  }
  foreach (y1; 0..H) foreach (x1; 0..W) foreach (y2; 0..H) foreach (x2; 0..W) foreach (y3; 0..H) foreach (x3; 0..W) {
    dist[y2*W+x2][y3*W+x3].amin(dist[y2*W+x2][y1*W+x1] + dist[y1*W+x1][y3*W+x3]);
  }

  long ans;
  foreach (i; 0..H*W) foreach (j; 0..H*W) {
    if (dist[i][j] < INF) ans.amax(dist[i][j]);
  }
  ans.writeln;
}


Measured memory_bytes: 3708
#include<bits/stdc++.h>
#ifdef LOCAL
#include "lib/debug.hpp"
#else
#define debug(...) 1
#endif
#define ALL(a) (a).begin(), (a).end()
#define rep(i, n) REP(i, 0, (n))
#define repc(i, n) REPC(i, 0, (n))
#define REP(i, n, m) for (int i = (int)(n); i < (int)(m); i++)
#define REPC(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define REPCM(i, n, m) for (int i = (int)(n); i >= (int)(m); i--)
using namespace std;
using ll = int_fast64_t;
using pr = pair<ll, ll>;
using vll = vector<ll>;
using vpr = vector<pr>;
template<class T> inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } else return false; }
template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }
struct LCA {
  int N, K;
  std::vector<std::vector<int> > G, parent;
  std::vector<int> depth;

  LCA(int n) : N(n) {
    K = (int)ceil(log2(N));
    G.resize(N);
    parent.resize(std::max(K, 1), std::vector<int>(N, -1));
    depth.resize(N, -1);
  }

  void add_edge(int u, int v) {
    G[u].push_back(v);
    G[v].push_back(u);
  }

  void dfs(int u, int p, int d) {
    if(depth[u] >= 0) return;
    parent[0][u] = p;
    depth[u] = d;
    for(const auto& v : G[u]) {
      dfs(v, u, d+1);
    }
  }

  void set_root(int u) {
    dfs(u, -1, 0);
    for(int k = 1; k < K; k++) {
      for(int i = 0; i < N; i++) {
        if(parent[k-1][i] == -1) {
          parent[k][i] = -1;
        } else {
          parent[k][i] = parent[k-1][parent[k-1][i]];
        }
      }
    }
  }

  int query(int u, int v) {
    if(depth[u] < depth[v]) std::swap(u, v);
    for(int i = K-1; i >= 0; i--) {
      if(parent[i][u] != -1 && depth[parent[i][u]] >= depth[v]) {
        u = parent[i][u];
      }
    }
    if(u == v) return u;
    for(int i = K-1; i >= 0; i--) {
      if(parent[i][u] != parent[i][v]) {
        u = parent[i][u];
        v = parent[i][v];
      }
    }
    return parent[0][u];
  }

  void dfs2(int u, int p, int& cnt, vector<vector<int> >& memo) {
    if(p != -1 && memo[u][p]) cnt++;
    for(const auto& v : G[u]) if(v != p) {
      dfs2(v, u, cnt, memo);
    }
  }
};

void answer() {
  ll n; cin >> n;
  LCA lca(n);
  rep(i,n-1) {
    ll a, b; cin >> a >> b;
    a--; b--;
    lca.add_edge(a, b);
  }
  lca.set_root(0);
  ll m; cin >> m;
  vector<ll> u(m), v(m);
  rep(i, m) {
    cin >> u[i] >> v[i];
    u[i]--; v[i]--;
  }
  vector<vector<int> > memo;
  auto add_all = [&](int i, int cur, int common) {
    while(cur != common) {
      memo[cur][lca.parent[0][cur]]++;
      cur = lca.parent[0][cur];
    }
  };
  ll ans = ll(pow(2, n-1));
  int lim = int(pow(2, m));
  REP(i, 1, lim) {
    memo.assign(n, vector<int>(n, 0));
    rep(j, m) if((i>>j)&1) {
      int common = lca.query(u[j], v[j]);
      add_all(i, u[j], common);
      add_all(i, v[j], common);
    }
    int cnt = 0;
    lca.dfs2(0, -1, cnt, memo);
    if(__builtin_popcount(i)%2) {
      ans -= ll(pow(2, n-1-cnt));
    } else {
      ans += ll(pow(2, n-1-cnt));
    }
  }
  cout << ans << "\n";
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  answer();
  return 0;
}

Measured memory_bytes: 384
import           Control.Monad
import           Data.Maybe
import qualified Data.ByteString.Char8         as C8

inf :: Int
inf = 100000

getInt :: IO Int
getInt = fmap (fst . fromJust . C8.readInt) C8.getLine

getInts :: IO [Int]
getInts = fmap (map (fst . fromJust . C8.readInt) . C8.words) C8.getLine

main :: IO ()
main = do
    [n, a, b, c] <- getInts
    ls           <- replicateM n $ getInt
    print $ solve ls [0, 0, 0] [a, b, c]

solve :: [Int] -> [Int] -> [Int] -> Int
solve [] xs as = if product xs == 0
    then inf
    else subtract 30 . sum . zipWith (\s t -> abs (s - t)) xs $ as

solve (l : ls) [x, y, z] as = minimum
    [ solve ls [x, y, z] as
    , 10 + solve ls [x + l, y, z] as
    , 10 + solve ls [x, y + l, z] as
    , 10 + solve ls [x, y, z + l] as
    ]
solve _ _ _ = 0


Measured memory_bytes: 1020
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <climits>
using namespace std;
#define MOD int(1e9 + 7)
#define INF (long long)(1e18)

int main()
{
    cout.precision(18);

    long long N, M, X;
    vector<vector<long long>> A;

    cin >> N >> M >> X;
    for (long long i = 0; i < N; i++)
    {
        vector<long long> tv;
        for (long long j = 0; j < M + 1; j++)
        {
            long long t;
            cin >> t;
            tv.push_back(t);
        }
        A.push_back(tv);
    }

    long long m = LLONG_MAX;
    for (long long i = 0; i < (long long)pow(2, N); i++)
    {
        vector<long long> tv(M, 0);
        long long v = 0;
        for (long long j = 0; j < N; j++)
        {
            if ((i >> j) & 1 > 0)
            {
                v += A[j][0];
                for (long long k = 0; k < M; k++)
                    tv[k] += A[j][k + 1];
            }
        }

        bool f = false;
        for (long long j = 0; j < M; j++)
            if (tv[j] < X)
                f = true;

        if (f == false)
        {
            m = min(m, v);
        }
    }

    if(m == LLONG_MAX)
        cout << -1 << endl;
    else
        cout << m << endl;
}

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


using namespace std;

#define int long long
#define all(a) a.begin(),a.end()
#define sz(x) ((int)x.size())
#define ff first 
#define ss second 
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<string> vs;
typedef map<int,int> mii;
typedef map<char,int> mci;
typedef vector<vector<int>> vvi;
typedef vector<pair<int,int>> vpii;
template<class T>
istream &operator>>(istream &in, vector<T> &arr){
	for(auto &x: arr) in >> x;
	return in;
}


signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;

    vi a(n);
    cin >> a;
    vvi dp(n,vi(n));
    for(int l = n - 1; l >= 0; --l){
        for(int r = l; r < n; ++r){
            if(l == r){
                dp[l][r] = a[l];
            }else{
                dp[l][r] = max(a[l] - dp[l+1][r],a[r] - dp[l][r - 1]);
            }
        }
    }
    // cout << dp[0][n-1];
    cout << dp[0][n-1];
}

Measured memory_bytes: 70784
//============================================================================
// Name        : alds1_3_c_double_linked_list.cpp
// Author      : lovesaemi
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <cstdio>
#include <cstdlib>
#include <cstring>

struct Node {
	int key;
	Node *next, *prev;
};
Node *nil;

Node* listSearch(int key) {
	Node *cur = nil->next;
	while (cur != nil && cur->key != key) {
		cur = cur->next;
	}
	return cur;
}
void init() {
	nil = (Node *) malloc(sizeof(Node));
	nil->next = nil;
	nil->prev = nil;
}
void printList() {
	Node *cur = nil->next;
	int isf = 0;
	while (1) {
		if (cur == nil) {
			break;
		}
		if (isf++ > 0) {
			printf(" ");
		}
		printf("%d", cur->key);
		cur = cur->next;
	}
	printf("\n");
}

void deleteNode(Node *t) {
	if (t == nil) {
		return;
	}
	t->prev->next = t->next;
	t->next->prev = t->prev;
	free(t);
}
void deleteFirst() {
	deleteNode(nil->next);
}
void deleteLast() {
	deleteNode(nil->prev);
}
void deleteKey(int key) {
	deleteNode(listSearch(key));
}
void insert(int key) {
	Node *x = (Node *) malloc(sizeof(Node));
	x->key = key;
	x->next = nil->next;
	nil->next->prev = x;
	nil->next = x;
	x->prev = nil;
}
int main() {
	int key, n, i;
	int size = 0;
	char com[20];
	int np = 0, nd = 0;
	scanf("%d", &n);
	init();
	for (i = 0; i < n; i++) {
		scanf("%s%d", com, &key);
		if (com[0] == 'i') {
			insert(key);
			np++;
			size++;
		} else if (com[0] == 'd') {
			if (strlen(com) > 6) {
				if (com[6] == 'F')
					deleteFirst();
				else if (com[6] == 'L')
					deleteLast();
			} else {
				deleteKey(key);
				nd++;
			}
			size--;
		}
	}
	printList();
	return 0;
}



Measured memory_bytes: 33828
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
const long long mod = 1e9+7;
//////////////////////////////////

int main() {
  int x, y; cin >> x >> y;

  for(int i=0; i<=x; i++) {
    int j = x - i;
    if (i * 2 + j * 4 == y) {
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;

  return 0;
}

// EOF

Measured memory_bytes: 3588
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
ll a[114514];
int main(){
  ll n;
  cin>>n;
  ll dis=0;
  for(int i=1;i<=n;i++){
    cin>>a[i];
    dis+=abs(a[i]-a[i-1]);
  }
  dis+=abs(a[n]);
  for(int i=1;i<=n;i++){
    ll ans=dis-abs(a[i]-a[i-1])-abs(a[i+1]-a[i])+abs(a[i+1]-a[i-1]);
    cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 2048
#include "bits/stdc++.h"
using namespace std;
#define long int64_t

struct Solver {
	void solve() {
		int N;
		cin >> N;

		vector<int> A( N+1 );
		for( int i = 1; i <= N; ++i ) { cin >> A[i]; }
		sort( A.begin(), A.end() );

		long ans = 0;
		for( int i = 1; i < N; ++i ) {
			ans += A[N - i/2];
		}
		cout << ans << endl;
	}
};

int main() {
	ios::sync_with_stdio( false );
	cout << fixed << setprecision( 10 );
	Solver().solve();
	return 0;
}


Measured memory_bytes: 4052
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

class UnionFindTree
{
    int n;
    vector<int> parent; // 親ノード
    vector<int> rank;   // 木の高さの上限
    vector<int> num;    // グループの要素数
    int find(int x){
        if(parent[x] == x)
            return x;
        return parent[x] = find(parent[x]);
    }
public:
    UnionFindTree(int n0){ // コンストラクタ
        n = n0;
        parent.resize(n);
        for(int i=0; i<n; ++i)
            parent[i] = i;
        rank.assign(n, 0);
        num.assign(n, 1);
    }
    void unite(int x, int y){ // xとyのグループを併合
        if((x = find(x)) != (y = find(y))){
            if(rank[x] < rank[y]){
                parent[x] = y;
                num[y] += num[x];
            }else{
                parent[y] = x;
                if(rank[x] == rank[y])
                    ++ rank[x];
                num[x] += num[y];
            }
            -- n;
        }
    }
    bool same(int x, int y){ // xとyのグループが同じかを調べる
        return find(x) == find(y);
    }
    int getNum(){ // グループの数を返す
        return n;
    }
    int getNum(int x){ // xのグループの要素数を返す
        return num[find(x)];
    }
};

class Data
{
public:
    int a, b, c;
    bool operator<(const Data& d) const{
        return c < d.c;
    }
};

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

    vector<Data> d(n);
    for(int i=0; i<n; ++i)
        cin >> d[i].a >> d[i].b >> d[i].c;
    sort(d.begin(), d.end());

    UnionFindTree uft(n);
    long long ret = 0;
    for(int i=0; i<n; ++i){
        ret += (long long)uft.getNum(d[i].a) * uft.getNum(d[i].b) * d[i].c;
        uft.unite(d[i].a, d[i].b);
    }

    cout << ret << endl;

    return 0;
}

Measured memory_bytes: 5756
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REP(i,b) FOR(i,0,b)
#define RFOR(i,a,b) for (int i = a-1; i >= b; i--)
#define RREP(i,a) RFOR(i,a,0)
#define REPALL(i,v) for (int i = 0; i < v.size(); i++)
#define RREPALL(i,v) for (int i = v.size()-1; i >= 0; i--)
#define ALL(v) v.begin(), v.end()
#define SORT(v) sort(v.begin(), v.end())
#define MIN_ELEMENT(v) min_element(v.begin(), v.end())
#define MAX_ELEMENT(v) max_element(v.begin(), v.end())
#define COUNT(v,n) count(v.begin(), v.end(), n)
void YES(bool flag) {cout<<(flag ? "YES" : "NO")<<endl;}
void Yes(bool flag) {cout<<(flag ? "Yes" : "No")<<endl;}
void yes(bool flag) {cout<<(flag ? "yes" : "no")<<endl;}
typedef long long ll;
typedef unsigned long long ull;
const int INF = 1e7;
const ll MOD = 1e9 + 7;

string s, t;
vector<vector<int>> appr(26);

bool check()
{
    vector<bool> exist(26, false);
    REPALL(i,s) {
        exist[s[i] - 'a'] = true;
        appr[s[i] - 'a'].push_back(i);
        appr[s[i] - 'a'].push_back(i + s.size());
    }
    REP(i,26)
        SORT(appr[i]);
    bool rtn = true;
    REPALL(i,t)
        rtn &= exist[t[i] - 'a'];
    return rtn;
}

int main()
{
    cin>>s>>t;

    if (!check()) {
        cout<<-1<<endl;
        return 0;
    }

    ll idx_s = 0ll, idx_t = 0ll;
    if (s[0] == t[0]) {
        idx_t++;
    }
    while (idx_t < t.size()) {
        idx_s += *upper_bound(ALL(appr[t[idx_t]-'a']), idx_s % s.size())
                - idx_s % s.size();
        idx_t++;
    }
    cout<<idx_s+1<<endl;

    return 0;
}


Measured memory_bytes: 1724
import java.util.*;

public class Main {

    public static void main(String args[])  {


        Scanner scan = new Scanner(System.in);

        int n = scan.nextInt();
        int[] list = new int[n];
        int sum = 0;

        for (int i =0; i<n; i++) {
            int a = scan.nextInt();

            if (i % 2== 0 && a % 2== 1) {
                sum++;
            }
        }
        System.out.println(sum);

    }

}

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

#define rep(i,j,n) for(int i=j;i<n;++i)
#define all(i) i.begin(),i.end()
#define rall(i) i.rbegin(), i.rend()
#define INF 1e9
#define LINF 1e18
const int mod = 1e9 + 7;

typedef long long i64;
typedef pair<int, int> pi;

template <class T> using vt = vector<T>;
template <class T> using vvt = vector<vector<T>>;

i64 gcd(i64 n, i64 m) {return (m == 0? n : gcd(m, n % m));}
i64 lcd(i64 n, i64 m) {return (n / gcd(n, m) * m);}
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

void dfs(int v, vvt<int> &edge, vt<bool> &visited) {
  if(visited[v]) return;

  visited[v] = true;
  for(auto &it : edge[v]) {
    dfs(it, edge, visited);
  }
}

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

  int n, m;
  cin >> n >> m;
  vvt<int> edge(n);
  rep(i, 0, m) {
    int x, y, z;
    cin >> x >> y >> z;
    x--; y--;
    edge[x].push_back(y);
    edge[y].push_back(x);
  }

  vt<bool> visited(n, false);
  int ans = 0;
  rep(i, 0, n) {
    if(!visited[i]) {
      ans++;
      dfs(i, edge, visited);
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 10368
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define DEBUGP(val) cerr << #val << "=" << val << "\n"

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PI;
const ll mod = 1e9 + 7;



int main(void) {
  double n, m, d;
  cin >> n >> m >> d;
  double tmp = -1;
  if (d == 0) {
    tmp = n;
  } else {
    tmp = 2 * (n - d);
  }
  printf("%.15f\n", tmp * (m - 1) / n / n);
}


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

int main() {
  int N = 123456*2;
  std::vector<int> p(N+1, 1);
  p[0] = p[1] = 0;
  for (int i = 2; i*i <= N; ++i) {
    if (!p[i]) continue;
    for (int j = i*i; j <= N; j += i)
      p[j] = 0;
  }

  for (int i = 1; i <= N; ++i) p[i] += p[i-1];

  while (true) {
    int n;
    scanf("%d", &n);
    if (n == 0) break;

    printf("%d\n", p[n+n]-p[n]);
  }
}



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

void solve() {
    rep(i, 5) {
        int x; cin >> x;
        if (x == 0) cout << i + 1 << endl;
    }
}

int main() {
    solve();
    return 0;
}


Measured memory_bytes: 3600
N, M, X = map(int,input().split())
A = []

for i in range(N):
  A.append(input().split())

minCost = pow(10,5) * N     # 購入金額の最安値
clearFlag = 0               # 達成可否判定
bit = "0" + str(N) + "b"    # 2進数のフォーマット指定

for i in range(pow(2,N)):
  # 購入する参考書を1、購入しない参考書を0のビットで表す
  buy = format(i, bit)
  
  # 購入金額を計算
  cost = 0
  for j in range(N):
    cost += (int(A[j][0]) * int(buy[j]))
  
  # アルゴリズムの習熟度を計算
  flag = 1
  for s in range(M):
    skill = 0
    for t in range(N):
      skill += (int(A[t][s+1]) * int(buy[t]))
    # 習熟度がXを超えているか確認
    if skill < X:
      flag = 0
      break
  
  # 全てのアルゴリズムで習熟度がXを超えていて、
  # 購入金額が暫定最安値よりも安い場合
  # 暫定最安値を更新
  if (flag == 1) & (cost <= minCost):
    clearFlag = 1
    minCost = cost

# 結果出力
if clearFlag == 1:
  print(minCost)
else:
  print(-1)

Measured memory_bytes: 9212
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
using namespace std;
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
using namespace std;
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define all(a) a.begin(),a.end()
#define rall(c) (c).rbegin(),(c).rend()
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll inf=1e9+7;
const ll mod=998244353;
ll V,E;
vector<vector<pll> >G(1010);
vector<ll>d(1010);
bool Bellman_Ford(ll s){
    bool f=1;
    d[s]=0;
    ll cnt=0;
    while(true){
        if(cnt==V){
            f=0;break;
        }
        cnt++;
        bool update=0;
        rep(i,V){
            for(auto e:G[i]){
                if(d[i]!=inf*inf&&d[e.first]>d[i]+e.second){
                    d[e.first]=d[i]+e.second;
                    update=true;
                }
            }
        }
        if(!update)break;
    }
    return f;
}
int main(){
    cin>>V>>E;
    rep(i,E){
        ll a,b,c;cin>>a>>b>>c;
        a--;b--;
        G[a].pb(mp(b,-c));
    }
    rep(i,V)d[i]=inf*inf;
    if(Bellman_Ford(0)){
        cout<<-d[V-1]<<endl;
    }else{
        ll k=d[V-1];
        Bellman_Ford(0);
        if(k==d[V-1])cout<<-d[V-1]<<endl;
        else cout<<"inf"<<endl;
    }
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define uli unsigned long long int
#define INF 999999999
#define rep(i,m,n) for(lli i = m;i < n;i++)
#define rrep(i,m,n) for(lli i=m;i>n;i--)
#define pb(n) push_back(n)
#define Sort(n) sort(n.begin(), n.end())
#define Rev(n) reverse(n.begin(),n.end())
#define Out(S) cout << S << endl
#define NeOut(S) cout << S
#define HpOut(S) cout << setprecision(20) << S << endl
#define Vecpr(K,L1,L2,N) vector<pair<L1,L2>> K(N)
#define Vec(K,L,N,S) vector<L> K(N,S)
#define DV(K,L,N,M,R) vector<vector<L>> K(N, vector<L>(M,R))
#define mod 1000000007
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a)
int main(){
  lli A=0,B,C,D,E,F,N,M,K,sum=0,num=0,cnt=1,next=0;
  cin >> N >> K;
  Vec(issafe,bool,N+1,true);
  Vec(DP,lli,N+1,0);
  rep(i,0,K){
    cin >> A;
    issafe[A]=false;
  }
  DP[0]=1;
  if(issafe[1])DP[1]=1;
  rep(i,2,N+1)if(issafe[i])DP[i]=(DP[i-1]+DP[i-2])%mod;
  Out(DP[N]);
}


Measured memory_bytes: 1024
#include <memory.h>

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>

using namespace std;

#define mod 1000000007

int main() {
	int n;
	cin >> n;
	int a[200000];
	int restBrickNum = 0;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		if (a == restBrickNum + 1) {
			restBrickNum++;
		}
	}
	if (restBrickNum == 0)
		cout << -1 << endl;
	else
		cout << n - restBrickNum << endl;
}

Measured memory_bytes: 256
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

k = int(input())
a,b = myinput()

for i in range(a,b+1):
    if i%k==0:
        print("OK")
        exit()
    else:
        pass
print("NG")
exit()

Measured memory_bytes: 68272
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC optimize("no-stack-protector,fast-math")
#define IO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#include<iostream>
#include<bits/stdc++.h>
#define ll long long 
using namespace std;
string s;
int f, l;
void ans() {
  for(int i = 0; i < 26; ++i) {
    int bf = -1;
    for(int j = 0; j < s.size(); ++j) {
      if(s[j] == 'a' + i) {
        if(bf != -1 && j - bf <= 2) {
          f = bf + 1;
          l = j + 1;
          return;
        }
        bf = j;
      }
    }
  }
}
int main() {
  f = l = -1;
  cin >> s;
  ans();
  cout << f << " " << l << endl;
  return 0;
}

Measured memory_bytes: 512
n = int(input())
atob = []
ans = 0
for i in range(n):
    x,y = map(int,input().split())
    ans += x
    atob.append(x+y)
    
atob.sort(reverse=True)

for i in range(n//2):
    ans -= atob[2*i+1]
    
print(ans)

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

#define LL long long
#define VI vector<int>
#define VVI vector<vector<int>>
#define VVVI vector<vector<vector<int>>>
#define VVVVI vector<vector<vector<vector<int>>>>
#define VL vector<LL>
#define VVL vector<vector<LL>>
#define VVVL vector<vector<vector<LL>>>
#define VVVVL vector<vector<vector<vector<LL>>>>
#define VB vector<bool>
#define FOR(i,a,b) for(int i= (a); i<((int)b); ++i)
#define RFOR(i,a) for(int i=(a); i >= 0; --i)
#define FOE(i,a) for(auto i : a)
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v,x) (std::find(v.begin(), v.end(), x) != v.end())
#define BIT(n) (1LL<<(n))
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
#define EPS 1e-14

template<class T> T ceil(T a, T b) { return (a + b - 1) / b; }
template<class T> void print(T x) { std::cout << x << std::endl; }

const std::string YES = "YES", Yes = "Yes", NO = "NO", No = "No";
const std::vector<int> dy = { 0, -1, 0, 1 }, dx = { 1, 0, -1, 0 };    // 4近傍（右, 下, 左, 上）

using namespace std;

const int MOD = 100000;

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

    while (true) {
        int W, H;
        cin >> W >> H;
        if (W == 0 and H == 0) { break; }

        // dp[i][j][k][l] = 位置(i, j)
        VVVVI dp(H, VVVI(W, VVI(3, VI(3, 0))));
        dp[0][0][2][2] = 1;

        FOR(y, 0, H) {
            FOR(x, 0, W) {
                FOR(k, 0, 3) {
                    FOR(l, 0, 3) {
                        // 上に行く
                        if (y + 1 < dp.size()) {
                            if (k == 2 or l == 0 or (k == l)) {
                                (dp[y + 1][x][l][0] += dp[y][x][k][l]) %= MOD;
                            }
                        }
                        // 右に行く
                        if (x + 1 < dp[0].size()) {
                            if (k == 2 or l == 1 or (k == l)) {
                                (dp[y][x + 1][l][1] += dp[y][x][k][l]) %= MOD;
                            }
                        }
                    }
                }
            }
        }

        LL ans = 0;
        FOR(k, 0, 3) {
            FOR(l, 0, 3) {
                (ans += dp[H - 1][W - 1][k][l]) %= MOD;
            }
        }
        print(ans % MOD);
    }
    return 0;
}


Measured memory_bytes: 5228