akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }

/*
 <url:>
 問題文============================================================
 =================================================================
 解説=============================================================
 ================================================================
 */

ll solve(){
    ll res = 0;
    ll N,M; cin >>N >> M;
    vector<vector<ll>> G(N,vector<ll>(N,LINF));
    for(int i = 0; i < N;i++) G[i][i] = 0;
    vector<pair<pll,ll>> edges(M);
    for(int i = 0; i < M;i++){
        ll a,b,c; cin >> a >> b >> c; a--; b--;
        G[a][b] = G[b][a] = min(G[a][b],c);
        edges[i] = {{a,b},c};
    }
    for(int i = 0; i < N;i++){
        for(int j = 0; j < N;j++){
            for(int k = 0; k < N;k++){
                G[j][k] = min(G[j][k],G[j][i]+G[i][k]);
            }
        }
    }
    
    for(int i = 0; i < M;i++){
        [&]{
            for(int j = 0; j < N;j++){
                for(int k = 0; k < N;k++){
                    if(j==k) continue;
                    if(G[j][k] == G[j][edges[i].first.first] + edges[i].second + G[edges[i].first.second][k]){
                        return;
                    }
                }
            }
            res++;
        }();
    }
    return res;
}
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    cout << solve() << endl;
    return 0;
}


Measured memory_bytes: 384
use std::io::{self, BufRead};
use std::cmp::min;

fn dist(s: i32, t: i32, x: i32, y: i32) -> i32 {
  min(t - s, (x - s).abs() + 1 + (t - y).abs())
}

fn main() {
  let stdin = io::stdin();
  let mut lines = stdin.lock().lines();
  let xs: Vec<i32> = lines.next().unwrap().unwrap().split(' ').map(|x| x.parse().unwrap()).collect();
  let n = xs[0];
  let x = xs[1] - 1;
  let y = xs[2] - 1;

  let mut counts = vec![0; n as usize - 1];
  for i in 0..n {
    for j in (i+1)..n {
      let d = dist(i, j, x, y);
      counts[d as usize - 1] += 1;
    }
  }

  for i in 0..(n-1) {
    println!("{}", counts[i as usize]);
  }
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
int main(void){
    char n[4];
    cin >> n;
    int a=n[0]-'0', b=n[1]-'0', c=n[2]-'0', d=n[3]-'0';
    if(a+b+c+d==7) cout << a<<"+"<<b<<"+"<<c<<"+"<<d<<"="<<"7"<< endl;
    else if(a-b+c+d==7) cout << a<<"-"<<b<<"+"<<c<<"+"<<d<<"="<<"7"<< endl;
    else if(a+b-c+d==7) cout << a<<"+"<<b<<"-"<<c<<"+"<<d<<"="<<"7"<< endl;
    else if(a+b+c-d==7) cout << a<<"+"<<b<<"+"<<c<<"-"<<d<<"="<<"7"<< endl;
    else if(a-b-c+d==7) cout << a<<"-"<<b<<"-"<<c<<"+"<<d<<"="<<"7" << endl;
    else if(a+b-c-d==7) cout << a<<"+"<<b<<"-"<<c<<"-"<<d<<"="<<"7" << endl;
    else if(a-b+c-d==7) cout << a<<"-"<<b<<"+"<<c<<"-"<<d<<"="<<"7" << endl;
    else if(a-b-c-d==7) cout << a<<"-"<<b<<"-"<<c<<"-"<<d<<"="<<"7" << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long int64;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = 1<<29;
const long long  INFL = 1e18;
const int MOD = 1000000007;
const int MAX = 210000;
const int MAX_NUM = 999999999;
int64 N;
int ans;
vector<int> target = {7, 5, 3};
void dfs(int64 num) {
	if (num > N) return;
	int64 t_num = num; 
	bool flg_7 = false;
	bool flg_5 = false;
	bool flg_3 = false;
	while (t_num > 0) {
		int modulo = t_num % 10;
		if (modulo == 7) flg_7 = true;
		if (modulo == 5) flg_5 = true;
		if (modulo == 3) flg_3 = true;
		t_num /= 10;	
	}
	if (flg_7 == true && flg_5 == true && flg_3 == true) ans++;
	dfs((num * 10) + target[0]);
	dfs((num * 10) + target[1]);
	dfs((num * 10) + target[2]);	
}
void solve() {
	cin >> N;
	for (int i = 0; i < target.size(); ++i) {
		dfs(target[i]);
	}
	cout << ans << endl;
	return;
}
int main() {
	solve();
	return 0;
}

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

using namespace std;

const int MAX = 100005;
vector<int> V[MAX];
int depth[MAX];

int main(){
  
  for(int i = 0; i < MAX; i++) V[i].clear();
  string in;
  getline(cin , in);
  string s = "";
  for(int i = 0; i < (int)in.length(); i++) if(in[i] != ' ') s += in[i];

  V[0].push_back(0);
  depth[0] = 0;
  int p = 0;
  for(int i = 0; i < (int)s.length(); i++){
    if(s[i] == '(') p++;
    if(s[i] == ')') p--;
    V[p].push_back(i+1);
    depth[i+1] = p;
  }

  long long ans = 0;
  for(int i = 1; i < (int)s.length(); i++)
    ans += V[depth[i]].end()-upper_bound(V[depth[i]].begin(), V[depth[i]].end(), i);
  cout << ans << endl;

  return 0;
}

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

int main() {
  int n,m,X,Y;
  cin>>n>>m>>X>>Y;
  vector<int> x(n);
  vector<int> y(m);
  rep(i, 0, n) cin >> x[i];
  rep(i, 0, m) cin >> y[i];

  bool frag = false;
  rep(z, X+1, Y+1) {
    int cnt = 0;
    rep(i, 0, n) if (x[i] < z) cnt++;
    rep(i, 0, m) if (y[i] >= z) cnt++;
    if (cnt == n+m) frag = true;
  }
  if (frag) cout << "No War" << endl;
  else cout << "War" << endl;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    int n;
    float cf, cp;
    cin>>n;
        cp=n*1.0;
        if(n%2==0){
            cf=n/2;
        }
        else{
            cf=n/2+1;
        }
        cout<<cf/cp;

        return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n,m,ans=0;
vector <pair<int,int> > v;
int main() {
	cin>>n>>m;
	for (int i=0; i<m; i++) {
		int x,y;
		cin>>x>>y;
		if (x>y) swap (x,y);
		v.push_back(make_pair(x,y));
	}
	sort (v.begin(),v.end());
	int t=v[0].first;
	int p=v[0].second;
	for(int i=1; i<m; i++) {
		if(t!=v[i].first) t=v[i].first;
		if(p>v[i].second) p=v[i].second;
		if(t>=p) {
			ans++;
			t=v[i].first;
			p=v[i].second;
		}
	}
	cout<<ans+1;
}

Measured memory_bytes: 1400
#include "bits/stdc++.h"
using namespace std;
///////////////////////////////////////////
const long long int INF = 1LL<<60;
const long long int Mod = 1000000007;
using ll = long long int; using ci = const int;
using vi = vector<int>;  using Vi = vector<long long int>;
using P = pair<int, int>;  using PLL = pair<ll, ll>;
using matrix = vector<vector<ll>>;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define rep(i,N) for(ll i = 0; i < (ll)N; i++)
#define repi(i,a,b) for(ll i = ll(a); i < ll(b); ++i)
template<class T>bool chmax(T &former, const T &b) { if (former<b) { former=b; return true; } return false; }
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return true; } return false; }
template<class T>T sqar(T x){ return x*x; }//sqrt(x)は平方根;
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(v[0])>()) //降順でVをソート
#define p_queue(v) priority_queue<v, vector<v>, greater<v> >
template<class T> inline void princ(T x){cout<<x<<" ";}; 
template<class T> inline void print(T x){cout<<x<<"\n";};
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
///////////////////////////////////////////////////////////////////////////////////

ll h,n;
Vi a;

int main(){
	cin.tie(0);ios::sync_with_stdio(false);
	std::cout<<std::fixed<<std::setprecision(30);
	cin>>h>>n;
	ll sum = 0;
	rep(i,n){
		ll inp;
		cin>>inp;
		sum += inp;
	}
	if(sum>=h)print("Yes");
	else print("No");
	return 0;
}

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

long memo[110000];

const int MOD = 1000000007;
template <typename T> long pow_mod(T base, T exp, const T modulus = 1000000007) {
	base %= modulus;
	long result = 1L;
	while (exp > 0) {
		if (exp & 1) result = (result * base) % modulus;
		base = (base * base) % modulus;
		exp >>= 1;
	}
	return result;
}

long func(int a){
	if(memo[a] != 0) return memo[a];
	if(a == 1) return memo[a] = 1;
	memo[a-1] = func(a - 1) % MOD;
	return memo[a] = a * memo[a-1] % MOD;
}

int main(){
	int n, m;
	scanf("%d%d", &n, &m);
	long ans = 0;
	if(abs(n - m) > 1) printf("0\n");
	else{
		if(n == m) {
			ans = pow_mod(func(n), 2L) * 2 % MOD;
		}else{
			int b = max(n, m);
			ans = pow_mod(func(b - 1), 2L) * b % MOD;
		}
		printf("%ld\n", ans);
	}
}


Measured memory_bytes: 4096
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		long m = scan.nextLong();
		long n = scan.nextLong();

		System.out.println(run(m, n, (long) 1000000007));
		scan.close();
		System.exit(0);
	}

	private static long run(long m, long n, long M) {
		long result = 1;
		for (long i = 1; i <= n; i++) {
			result *= m;
			if (result >= M) {
				result = result % M;
				result = run(result, (long) n / i, (long) 1000000007);
				i = n - (n % i);
			}
		}
		return result;
	}
}

Measured memory_bytes: 26408
#include<iostream>
#include<map>
using namespace std;
#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define N 1500001
int is_exist[N]={0};
int cnt[N]={0};
int solve(int n,int m,int *h,int *w,int tc){
  map<int,int> M;
  rep(i,m){//length
    int tmp=0;
    rep(j,i+1){
      tmp+=w[j];
    }
    if( is_exist[tmp]!=tc)is_exist[tmp]=tc,cnt[tmp]=1;
    else cnt[tmp]++;
    REP(j,i+1,m){
      tmp=tmp-w[j-i-1]+w[j];
      if ( is_exist[tmp]!=tc)is_exist[tmp]=tc,cnt[tmp]=1;
      else cnt[tmp]++;
    }
  }

  int ret = 0;
  rep(i,n){
    int tmp=0;
    rep(j,i+1){
      tmp+=h[j];
    }
    if (is_exist[tmp]==tc)ret+=cnt[tmp];
    REP(j,i+1,n){
      tmp=tmp-h[j-i-1]+h[j];
      if ( is_exist[tmp] ==tc)ret+=cnt[tmp];
    }
  }
  return ret;
}

main(){
  int n,m;
  int h[1500],w[1500];
  int tc=0;
  //while(cin>>n>>m && n){
  while(scanf("%d%d",&n,&m) && n){
    tc++;
    rep(i,n)scanf("%d",&h[i]);//cin>>h[i];
    rep(j,m)scanf("%d",&w[j]);//cin>>w[j];
    cout << solve(n,m,h,w,tc) << endl;
  }
}

Measured memory_bytes: 4840
for inning in range(int(input())):
    out=0
    runner=[0]*4
    while out<3:
        event=input()
        if event=="HIT":
            for i in range(3,0,-1):
                runner[i]+=runner[i-1]
                runner[i-1]=0
            runner[0]=1
        elif event=="HOMERUN":
            runner[3]+=1
            for i in range(3,0,-1):
                runner[3]+=runner[i-1]
                runner[i-1]=0
        elif event=="OUT":
            out+=1
        #print(runner)
    print(runner[3])



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


int main()
{
  int n; cin >> n;
  vector<int> a(n);
  map<int, ll> p;
  rep(i, n)
  {
    cin >> a[i];
    p[a[i]]++;
  }
  vector<int> b = a;
  sort(b.begin(), b.end());
  b.erase(unique(b.begin(), b.end()), b.end());
  ll comb = 0;
  for (int i : b)
    comb += p[i] * (p[i] - 1) / 2;
  rep(i, n)
  {
    if (p[a[i]] == 1)
      printf("%lld\n", comb);
    else
      printf("%lld\n", comb - p[a[i]] + 1);
  }
}

Measured memory_bytes: 11008
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);

		int aNum = scan.nextInt();
		int bNum = scan.nextInt();

		boolean eatFlag = false;

		if((aNum % 3 == 0) || (bNum % 3 == 0) || ((aNum + bNum) % 3 == 0)) {
			eatFlag = true;
		}

		if(eatFlag) {
			System.out.println("Possible");
		} else {
			System.out.println("Impossible");
		}
	}

}

Measured memory_bytes: 20436
l = []
for i in range(5): l.append(int(input()))
ok = False
for i in range(5):
    if l[i] % 10 != 0: ok = True
if ok == 0:
    print(sum(l))
    exit()
mini = 9
for i in range(5):
    if l[i] % 10 != 0 and l[i] % 10 < mini % 10:
        mini = l[i]
ans = mini
for i in range(5):
    d = l[i] // 10
    if l[i] % 10 != 0: d += 1
    ans += d * 10
d = mini // 10
d += 1
ans -= d * 10
print(ans)

Measured memory_bytes: 61968
inf = float("inf")
V,E = map(int, input().split())

d = [[0 if i == j else inf for i in range(V)] for j in range(V)]

for i in range(E):
    s,t,c = map(int, input().split())
    d[s][t] = c

def wf():
    for k in range(V):
        for i in range(V):
            for j in range(V):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
wf()

flag = True
for i in range(V):
    if d[i][i] < 0:
        flag = False
        break
if flag:
    for i in range(V):
        print(" ".join("INF" if j == inf else str(j) for j in d[i]))
else: print("NEGATIVE CYCLE")

Measured memory_bytes: 8156
A = int(input()) - 1
B = 1
o = 100000

def digitsum(x):
    s = 0
    while x > 0:
        s += x%10
        x //= 10
    return s

while A >= 1:
    o = min(digitsum(A)+digitsum(B),o)
    A-=1
    B+=1

print(o)

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

int main() {
	string ch, x;
	int a = 0;
	cin >> ch;
	cin >> x;
	for (int i = 0;i < ch.size() && a == 0;i++) {
		if (ch[i] == x[0]) {
			for (int j = 0;j < x.size();j++) {
				int ss = i + j;
				if (ss >= ch.size())ss = ss - ch.size();
				//cout << j << ":" << x.size() << endl;
				if (ch[ss] == x[j]) {
					a = 1;
				}else {
					a = 0;
					break;
				}
			}
		}
	}
	if(a == 1)cout << "Yes" << endl;
	if (a == 0)cout << "No" << endl;

	return 0;
}



Measured memory_bytes: 3188
#include<stdio.h>

void matrixChainOrder(int);
int min(int,int);

int p[101],m[101][101];

int main(){
  int c,i,n,r;

  scanf("%d",&n);
  for(i=0;i<n;i++) scanf("%d%d",&p[i],&p[i+1]);

  matrixChainOrder(n);

  printf("%d\n",m[1][n]);

  return 0;
}

void matrixChainOrder(int n){
  int i,j,k,l,q;

  for(i=1;i<=n;i++) m[i][i]=0;

  for(l=2;l<=n;l++){
    for(i=1;i<=n-l+1;i++){
      j=i+l-1;
      m[i][j]=100000000;
      for(k=i;k<j;k++){
	q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
	m[i][j]=min(m[i][j],q);
      }
    }
  }
}

int min(int a,int b){
  if(a<=b) return a;
  else return b;
}



Measured memory_bytes: 2132
#include <stdio.h>

int main(void) {
	// your code goes here
	long long n,k,x,y;
	scanf("%lld%lld%lld%lld", &n, &k, &x, &y);
	long long ans;
	if(n<k) ans=n*x;
	else ans=k*x+(n-k)*y;
	printf("%lld", ans);
}

Measured memory_bytes: 128
#include <iostream>
#include <cstring>

using namespace std;
int a[8005];
bool f[8005][16005];
int j=0;
void findx(int t,int x)
{
	if(f[t][x+8000]) return;
	if(t+2<=j)
	{
		findx(t+2,x+a[t+2]);
		findx(t+2,x-a[t+2]);
	}
	f[t][x+8000]=true; 
}
void findy(int t,int y)
{
	if(f[t][y+8000]) return;
	if(t+2<=j)
	{
		findy(t+2,y+a[t+2]);
		findy(t+2,y-a[t+2]);
	}
	f[t][y+8000]=true; 
}
int main()
{
	memset(f,0,sizeof(f));
	int x,y;string s;
	cin>>s>>x>>y;
	int cnt=0;
	for(int i=0;i<s.size();i++)
	{ 
		if(s[i]=='F')
		{
			cnt++;
		}
		else
		{
			a[++j]=cnt;
			cnt=0;
		}
	}
	if(cnt!=0) a[++j]=cnt;
	a[0]=0;
	findx(1,a[1]);
	findy(0,0);
	if(j%2==0)
	{
		if(f[j-1][x+8000]==1&&f[j][y+8000]==1) cout<<"Yes";
		else cout<<"No"; 
	}
	else
	{
		if(f[j][x+8000]==1&&f[j-1][y+8000]==1) cout<<"Yes";
		else cout<<"No";
	}
	return 0;
} 

Measured memory_bytes: 125568
from sys import stdin
n = int(stdin.readline().rstrip())
AB = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n)]
kouhuku = [i[0]+i[1] for i in AB]
kouhuku.sort(reverse=True)
aoki = sum(i[1] for i in AB)
takahashi = sum(kouhuku[::2])
print(takahashi-aoki)

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

#define MOD		1000000007
#define ll		long long int
#define pll		pair<ll, ll>
#define pb		push_back
#define endl	"\n"
#define f 		first
#define s 		second
#define fastio 	ios_base::sync_with_stdio(false);cin.tie(NULL)

ll power(ll x, ll y) { ll ans = 1; x %= MOD; while (y) {if (y & 1)ans = (x * ans) % MOD; x = (x * x) % MOD; y >>= 1;} return ans;}

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}

#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)

void solve() {

}

int main() {

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	fastio;
	ll n, k;
	cin >> n >> k;
	vector<ll> arr(n);
	ll lo = 1;
	ll hi = 1;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		hi = max(hi, arr[i]);
	}
	
	if(k == 0) {
	    cout << hi << endl;
	    return 0;
	}
	

	ll ans = hi;

	while (lo < hi) {
// 		debug(lo, hi, k);
		ll mid = lo + (hi - lo) / 2;

		ll currCuts = 0;

		for (int i = 0; i < n; i++) {
			currCuts += (arr[i] / mid);
			if(arr[i] % mid == 0) {
			    currCuts--;
			}
		}

		if (currCuts > k) {
			lo = mid + 1;
		} else {
			hi = mid;
			ans = mid;
		}

// 		debug(mid, currCuts);
	}

	cout << ans << endl;
}

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

class Main {

	private static final int V = 100005;

	private static List<Integer>[] G;
	private static boolean[] visited;
	private static long[] count = new long[2];

	protected static void dfs(int v) {
		if (visited[v]) return;
		visited[v] = true;
		count[v / V]++;
		for (int nv : G[v]) dfs(nv);
	}

	public static void main(String[] args) throws Exception {
		final Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();

		G = new ArrayList[V * 2];
		for (int i = 0; i < V * 2;
			 i++) {
			G[i] = new ArrayList<>();
		}

		for (int i = 0; i < N; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt() + V;
			G[x].add(y);
			G[y].add(x);
		}

		long answer = 0;
		visited = new boolean[V * 2];
		for (int i = 0; i < V * 2; i++) {
			if (visited[i]) continue;
			dfs(i);
			answer += count[0] * count[1];
			count[0] = count[1] = 0;
		}

		System.out.println(answer - N);
	}
}


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

constexpr ll INF = INT_MAX;

void chmax(ll &a, ll b){
    a = max(a, b);
}

int main() {
    int N, M, T;
    cin >> N >> M >> T;
    vector<vector<ll> > dp(21,vector<ll>(T,-INF/2));  // dp[i][j] 2^i個以下のボールを使って余りをjにするときの商の最大
    dp[0][0] = 0;
    for(int i=0;i<N;i++){
        ll a;
        cin >> a;
        chmax(dp[0][a%T], a/T);
    }
    // ダブリング
    for(int i=0;i<20;i++){
        for(int j=0;j<T;j++){
            for(int k=j;k<T;k++){
                int l = (j+k)%T, c = (j+k)/T;
                chmax(dp[i+1][l], dp[i][l]);
                if(dp[i][j] >= 0 && dp[i][j] >= 0){
                    chmax(dp[i+1][l], dp[i][j]+dp[i][k] + c);
                }
            }
        }
    }
    // dpを元にM個以下のときの最大値を計算
    vector<vector<ll> > ans(2,vector<ll>(T,-INF/2));
    ans[0][0] = 0;
    for(int m=M,i=0;m>0;m>>=1,i++){
        if(m&1){
            for(int j=0;j<T;j++){
                for(int k=0;k<T;k++){
                    int l = (j+k)%T, c = (j+k)/T;
                    chmax(ans[1][l], ans[0][l]);
                    if(ans[0][j] >= 0 && dp[i][k] >= 0){
                        chmax(ans[1][l], ans[0][j]+dp[i][k]+c);
                    }
                }
            }
            for(int j=0;j<T;j++){
                ans[0][j] = ans[1][j];
            }
        }
    }
    // 累積max
    for(int i=T-2;i>=0;i--){
        chmax(ans[0][i], ans[0][i+1]);
    }
    int Q;
    cin >> Q;
    for(;Q>0;Q--){
        ll a, b;
        cin >> a >> b;
        if(ans[0][a] >= b){
            cout << "yes" << endl;
        }
        else{
            cout << "no" << endl;
        }
    }
    return 0;
}



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

#define fi first
#define se second
#define endl '\n'
#define lc (rt<<1)
#define rc (rt<<1|1)
#define mp make_pair
#define pb push_back
#define lowbit(a) (a&(-a))
#define sz(x) (int)(x).size()
#define all(x) x.begin(),x.end()
#define mst(a,v) memset(a,v,sizeof(a))
#define debug(x) cout<<#x": "<<x<<'\n';
#define IOS {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ld> vd;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

const int N=100010;
const int mod=1e9+7;
const ld PI=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;

template<typename T>inline void gmax(T &A,T B) {(A<B)&&(A=B);}
template<typename T>inline void gmin(T &A,T B) {(A>B)&&(A=B);}

template <class T>
inline bool re(T &ret)
{
    char c;
    int sgn;
    if(c=getchar(),c==EOF) return 0;
    while(c!='-'&&(c<'0'||c>'9')) c=getchar();
    sgn=(c=='-')?-1:1;
    ret=(c=='-')?0:(c-'0');
    while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
    ret*=sgn;
    return 1;
}

ll dp[N];
int w[111],v[111];

int main()
{
#ifdef local
    //freopen("in.txt", "r", stdin);
#endif
    IOS;
    int n,c;
    cin>>n>>c;
    for(int i=1; i<=n; i++) cin>>w[i]>>v[i];
    mst(dp,0x3f);
    dp[0]=0;
    for(int i=1; i<=n; i++)
        for(int j=1000*n; j>=v[i]; j--)
        gmin(dp[j],dp[j-v[i]]+w[i]);
    for(int i=1000*n; ~i; i--) if(dp[i]<=c) return cout<<i,0;
    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define N 100005
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
	int ans=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
	return ans;
}
int n,k,first[N],cnt,fa[N],val[N],low[N],high[N],ans[N],rt;
bool is[N];
struct edge{int v,next;}e[N<<1];
inline void add(int u,int v){e[++cnt].v=v,e[cnt].next=first[u],first[u]=cnt;}
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
inline bool dfs1(int p,int fa,bool tmp){
	if(is[p]&&tmp!=(val[p]&1))return false;
	for(int i=first[p];i;i=e[i].next){
		int v=e[i].v;
		if(v==fa)continue;
		if(!dfs1(v,p,(tmp^1)))return false;
	}
	return true;
}
inline bool dfs2(int p,int fa){
	if(is[p])low[p]=high[p]=val[p];
	for(int i=first[p];i;i=e[i].next){
		int v=e[i].v;
		if(v==fa)continue;
		if(!dfs2(v,p))return false;
		low[p]=max(low[p],low[v]-1),high[p]=min(high[p],high[v]+1);
	}
	return low[p]<=high[p];
}
inline void dfs3(int p,int fa,int w){
	ans[p]=w;
	for(int i=first[p];i;i=e[i].next){
		int v=e[i].v;
		if(v==fa)continue;
		dfs3(v,p,(low[v]<=w-1&&high[v]>=w-1?w-1:w+1));
	}
}
int main(){
	n=read();
	for(int i=1;i<n;++i){
		int a=read(),b=read();
		add(a,b),add(b,a);
	}
	for(int i=1;i<=n;++i)low[i]=-inf,high[i]=inf;
	k=read();
	for(int i=1;i<=k;++i){
		int a=read(),b=read();
		val[a]=b,is[a]=1,rt=a;
	}
	if(!dfs1(rt,0,(val[rt]&1))||!dfs2(rt,0)){puts("No");return 0;}
	puts("Yes");
	dfs3(rt,0,val[rt]);
	for(int i=1;i<=n;++i)printf("%d\n",ans[i]);
	return 0;
}

Measured memory_bytes: 6912
from collections import defaultdict

n = int(input())
al = list(map(int, input().split()))

r = defaultdict(int)
l = defaultdict(int)
for i in range(n):
    r[al[i]+i] += 1
    l[i-al[i]] += 1

res = 0
for k in r:
    res += r[k]*l[k]

print(res)

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

public class Main {
	public static void main(String[] args) throws IOException {
		
		// 入出力高速化 java.io.* とthrows IOExceptionを忘れずに
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		double LLL = Double.parseDouble(br.readLine());
		double L = LLL/3; 
		
		System.out.println(L*L*L);	
	}
}

Measured memory_bytes: 33164
#include <bits/stdc++.h>
using namespace std;
#define FIN ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

typedef vector<int> vi;

int main() {FIN
	
	string s;
            cin >> s;
    if (s[2] == s[3] and s[4] == s[5])
      	cout << "Yes\n";
            else
              cout << "No\n";
	return 0;	
}

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

int main(){
	int n, m;

	while(std::cin >> n >> m, n){
		int s1 = 0, s2 = 0;
		std::vector<int> v1, v2;
		for(int i=0;i<n;i++){
			int j;
			std::cin >> j;
			v1.push_back(j);
			s1 += j;
		}

		for(int i=0;i<m;i++){
			int j;
			std::cin >> j;
			v2.push_back(j);
			s2 += j;
		}

		std::sort(v1.begin(), v1.end());
		std::sort(v2.begin(), v2.end());

		const int INF = 1 << 24;
		int a = INF, b = INF;
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				if(s1 - v1[i] + v2[j] == s2 - v2[j] + v1[i] && v1[i] + v2[j] < a + b){
					a = v1[i];
					b = v2[j];
				}
			}
		}

		if(a == INF){
			std::cout << "-1" << std::endl;
		}else{
			std::cout << a << " " << b << std::endl;
		}
	}
}

Measured memory_bytes: 1220
n,m=map(int,input().split())
edge=[[] for i in range(n+1)]
for i in range(m):
    a,b,c=map(int,input().split())
    edge[a].append((b,-c))

renew=[0]*(n+1)
INF=float('inf')
def bellmanford(s,n):
    d = [INF for i in range(n+1)]
    d[s]=0
    q=[s]
    while q:
        x=q.pop()
        dist=d[x]
        for v,cost in edge[x]:
                if d[v]>dist+cost:
                    d[v]=dist+cost
                    q.append(v)
                    renew[v]+=1
                    if renew[v]>n:
                        d[v]=-INF
    return d
d=bellmanford(1,n)
print(-d[n])

Measured memory_bytes: 46828
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define REP(i, n) for (LL i = 0; i < (LL)(n); i++)
#define REP2(i, n) for (int i = 1; i <= (int)(n); i++)
#define FOR(i, m, n) for (LL i = m; i < n; i++)
#define SORT(x) sort(x.begin(), x.end())
#define REVE(x) reverse(x.begin(), x.end())
#define ALL(x) (x).begin(), (x).end()
#define SUM(x) accumulate(x.begin(), x.end(),0)
#define vLL(v,n) vector<LL> v(n); REP(i,n)cin>>v[i];
#define vstr(v,n) vector<string> v(n); REP(i,n)REP(i,n)cin>>v[i];
LL INF = 1e9 + 1;
LL MOD = 1e9+7;
  LL a,b,c,d,e,n,m,l,r,x,y,z,ans=0,ans2=0,count;
string s,S,t;
int main() {
ios_base::sync_with_stdio(false);
cin >> n;
vLL(A,n);
SORT(A);
REP2(i,n-1){
    ans+=A[n-i/2-1];
   
}
cout << ans <<endl;
}

Measured memory_bytes: 4768
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>

#define int long long
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) (signed)((a).size())
#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define SORT(c) sort((c).begin(), (c).end())

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;

const int MOD = 1000000007;

#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")"  << " " << __FILE__ << endl;

signed main(void) {
    ios::sync_with_stdio(false);
    cout.setf(ios::fixed, ios::floatfield);
    cout.precision(10);
    cin.tie(0);

    int n;
    cin >> n;
    VI a(n);
    REP(i, n) {
        cin >> a[i];
    }

    SORT(a);

    int ans = 0, sum = a[0];
    FOR(i, 1, n) {
        if (sum * 2 < a[i]) {
            ans = i;
        }
        sum += a[i];
    }

    cout << n-ans << endl;


    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include <algorithm> 
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
#define ll long long
#define rep(i,n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repR(i,n) for(ll i=n;i>=0;i--)
#define all(v)(v).begin(),(v).end()
#define rall(v)(v).rbegin(),(v).rend()
#define F first
#define S second
#define pb push_back
#define pu push
#define COUT(x) cout<<(x)<<"\n"
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,vector<ll>,greater<ll>>
#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define mp make_pair
#define sz(x) (ll)(x).size()
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef tuple<ll,ll,ll> tll;
const ll MOD = 1000000007LL;
const ll INF = 1LL << 60;
using vll = vector<ll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvll = vector<vll>;
using vstr = vector<string>;
using vc = vector<char>;
using vvc = vector<vc>;
template<class T> inline bool chmax(T& a, T b) { 
 if (a < b) { a = b; return true; } return false; 
}
template<class T> inline bool chmin(T& a, T b) {
 if (a > b) { a = b; return true; } return false; 
}
ll dx[4]={0,1,0,-1};
ll dy[4]={1,0,-1,0};
int main(){
  ll n;
  cin>>n;
  vvll a(n,vll(n));
  vvll t(n,vll(n));
  rep(i,n)rep(j,n){
    cin>>a[i][j];
    t[i][j]=a[i][j];
  }
  rep(k,n)rep(i,n)rep(j,n){
    chmin(t[i][j],t[i][k]+t[k][j]);
  }
  rep(i,n)rep(j,n){
    if(a[i][j]!=t[i][j]){
      COUT(-1);
      return 0;
    }
  }
  ll ans=0;
  vvb h(n,vb(n,true));
  rep(k,n){
    rep(i,n)rep(j,n){
      if(i==j||i==k||j==k) continue;
      if(h[i][j]&&a[i][j]==a[i][k]+a[k][j]){
        h[i][j]=false;
      }
    }
  }
  rep(i,n)rep(j,n){
    if(i<j&&h[i][j]) ans+=a[i][j];
  }
  COUT(ans);
}

Measured memory_bytes: 5068
object Main extends App {

  def gcd(a: Long, b: Long): Long = if (b == 0)
    a
  else
    gcd(b, a % b)

  def lcm(a: Long, b: Long): Long = a * b / gcd(a, b)

  def lcm(list: Seq[Long]): Long = list.reduceLeft(lcm)

  def countDivide2(a: Long, acc: Int): Int = if (a % 2 == 0)
    countDivide2(a / 2, acc + 1)
  else
    acc

  val Array(_, m) = io.StdIn.readLine().split(' ').map(_.toLong)
  val a = io.StdIn.readLine().split(' ').map(_.toLong).distinct

  val answer = if (a.map(countDivide2(_, 0)).distinct.size != 1)
    0
  else {
    val lcmHalf = lcm(a.map(_ / 2))
    math.ceil((m / lcmHalf).toDouble / 2.0)
  }

  println(answer.toLong)
}


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

#define FOR(i, j, n) for (int i(j); i < n; ++i)
#define FORR(v, c) for (auto &v : c)
#define F first
#define S second
#define SQ(x) (x)*(x)
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define dbg(x) cerr<<#x<<" = " << (x) << endl
#define pnl(x) cout << x << '\n'
#define pns(x) cout << x << ' '
#define read(x) cin >> x
#define read2(x,y) cin >> x >> y
#define read3(x, y, z) cin >> x >> y >> z
#define read4(a, b, c, d) cin >> a >> b >> c >> d
#define readv(v) FORR(c,v) read(c)

struct Arrete { int v, c;};
struct Point {int x, y; double distance(Point other) const {return sqrt(SQ(x-other.x)+SQ(y-other.y));}};

typedef	vector<int>	vi;
typedef pair<int,int>	ii;
typedef vector<string>	vs;
typedef vector<ii>	vii;
typedef vector<Arrete>	vg;
typedef vector<long long>	vl;
typedef	long long ll;

const int MAXN = 2e5;

int n;
ll k;
ll A[MAXN], F[MAXN];

bool can(ll m)
{
	ll need(0);
	FOR(i,0,n)
		need += max(0LL, A[i] - m/F[i]);
	return need <= k;
}


int		main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	read2(n, k);

	FOR(i,0,n)
		read(A[i]);
	FOR(i,0,n)
		read(F[i]);
	sort(A, A + n);
	sort(F, F+n);
	reverse(F, F+n);
	
	ll l=0;
	ll r = 1e18;

	while (l < r)
	{
		ll m = (l+r)/2;
		if (can(m))
			r = m;
		else
			l = m+1;
	}
	pnl(l);
}



Measured memory_bytes: 3328
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=1e9+7;
const int INF=1e9;
const ll LINF=(ll)1e18;

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

struct LargeCombination{
    vector<ll> inv,pre,comb;
    LargeCombination(int n,int mx){init(n,mx);}
    void init(int n,int mx){
        inv.resize(mx+1);
        pre.resize(mx+1);
        comb.resize(mx+1);
        inv[1]=1;
        pre[1]=n;
        comb[0]=1,comb[1]=n;
        for(int i=2;i<=mx;i++){
            inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
            pre[i]=((n-i+1)*inv[i])%MOD;
            comb[i]=(comb[i-1]*pre[i])%MOD;
        }
    }
    ll calc(int k){
        return comb[k];
    }
};

int main(){
    int n,a,b;
    cin>>n>>a>>b;
    LargeCombination c(n,max(a,b));
    ll ans=modpow(2,n)-1;
    ans-=c.calc(a)+c.calc(b);
    ans%=MOD;
    ans=(ans+MOD)%MOD;
    cout<<ans<<endl;
}


Measured memory_bytes: 4992
N, M = map(int, input().split())
H = tuple(map(int, input().split()))

visited = [False] * (N + 1)

g = [set() for _ in range(N + 1)]

for _ in range(M):
    a, b = map(int, input().split())
    g[a].add(b)
    g[b].add(a)

ans = 0
for n in range(1, N + 1):

    if visited[n]:
        continue

    visited[n] = True

    if len(g[n]) == 0:
        ans += 1
    else:
        ok = True
        for c in g[n]:
            if H[n - 1] <= H[c - 1]:
                ok = False
            else:
                visited[c] = True
        if ok:
            ans += 1

print(ans)


Measured memory_bytes: 110228
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++)
#define All(v) (v).begin(), (v).end()
#define pb push_back
#define MP(a, b) make_pair((a), (b))
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int INF = 1 << 30;
const ll LINF = 1LL << 60;
const int MOD = 1e9 + 7;

int main() {
    int H, N;
    cin >> H >> N;
    vector<int> A(N);
    int sum = 0;
    rep(i, N) {
        cin >> A[i];
        sum += A[i];
    }
    if(sum >= H)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 640
mod = 998244353

class combination():
    def __init__(self, n):
        self.fact = [1] * (n+1)
        self.ifact = [1] * (n+1)
        for i in range(1, n+1):
            self.fact[i] = self.fact[i-1]*i % mod
        self.ifact[n] = pow(self.fact[n], mod-2, mod)
        for i in range(n, 0, -1):
            self.ifact[i-1] = self.ifact[i]*i % mod
    def comb(self, n, k):
        if k < 0 or k > n: return 0
        comb = self.fact[n]*self.ifact[k]*self.ifact[n-k] %mod
        return comb
        
        
n, m, k = map(int, input().split())

comb = combination(n)

ans = 0
color = m
for i in range(k+1):
    ans += m * pow(m-1, n-1-i, mod) * comb.comb(n-1, i)
    ans %= mod
print(ans)


Measured memory_bytes: 24708
#define _USE_MATH_DEFINES
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };

ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
char hoge[4] = {'W', 'N', 'E', 'S'};

int main() {
	for (;;) {
		int H, W; ll L; cin >> H >> W >> L;
		if (H == 0) break;
		vector<string> c(H);
		int xs, ys, ds;
		for (int y = 0; y < H; y++) {
			cin >> c[y];
			for (int x = 0; x < W; x++) {
				char& z = c[y][x];
				if (z == '.' || z == '#') continue;
				xs = x; ys = y;
				if (z == 'W') ds = 0;
				if (z == 'N') ds = 1;
				if (z == 'E') ds = 2;
				if (z == 'S') ds = 3;
				z = '.';
			}
		}
		int x = xs, y = ys, d = ds;
		vector< vector< vector<int> > > a(H, vector< vector<int> >(W, vector<int>(4, -1)));
		while (L--) {
			for (;;) {
				int _x = x + dx[d], _y = y + dy[d];
				if (_x >= 0 && _x < W && _y >= 0 && _y < H && c[_y][_x] == '.') break;
				d = (d + 1) % 4;
			}
			x += dx[d]; y += dy[d];
			if (a[y][x][d] == -1) {
				a[y][x][d] = L;
				continue;
			}
			int l = a[y][x][d] - L;
			L -= (L - 1) / l * l;
		}
		cout << y + 1 << ' ' << x + 1 << ' ' << hoge[d] << endl;
	}
}

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

#ifndef LOCAL_
#define fprintf if( false ) fprintf
#endif // LOCAL_
#define dump() fprintf(stderr, "#%s.%d\n", __func__, __LINE__);
#define dumpl(x1) fprintf(stderr, "#%s.%d (%s) = (%ld)\n", __func__, __LINE__, #x1, x1);
#define dumpll(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%ld, %ld)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define dumplll(x1, x2, x3) fprintf(stderr, "#%s.%d (%s, %s, %s) = (%ld, %ld, %ld)\n", __func__, __LINE__, #x1, #x2, #x3, x1, x2, x3);
#define dumpd(x1) fprintf(stderr, "#%s.%d (%s) = (%lf)\n", __func__, __LINE__, #x1, x1);
#define dumpdd(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%lf, %lf)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define loop for(;;)
typedef int64_t Int;
typedef std::vector<Int> LI;
typedef std::queue<Int> QI;
#define rep(i,n) for(Int i = 0; i < (Int)n; ++i)
const double pi = 3.14159265358979323846264338;
const Int mod = 1000000007;

template<typename T> void scan1(T& x) { fprintf(stderr, "unknown type\n"); }
template<> void scan1(Int& x) { if( scanf("%" PRId64, &x) < 0 ) exit(0); }
template<> void scan1(std::string& x) { if( not ( std::cin >> x ) ) exit(0); }
template<> void scan1(LI& xs) { for(Int &x : xs) scan1(x); }
void scan() {}
template<typename Head, typename... Tail>
void scan(Head& x, Tail&... xs) {
  scan1(x); scan(xs...);
}

struct Solver {
   Solver() { fprintf(stderr, "--------Solver begin--------\n"); }
   ~Solver() { fprintf(stderr, "--------Solver end--------\n"); }
   void solve() {
      Int x, t; scan(x, t);
      Int res = std::max((Int)0, x - t);
      printf("%" PRId64 "\n", res);
   }
};

int main() {
   loop std::unique_ptr<Solver>(new Solver())->solve();
}



Measured memory_bytes: 256
#include<cstdio>
#include<cctype>

int main(){
	int A,B;
	scanf("%d %d", &A, &B);
	char S[12];
	scanf("%s", S);
	int i = 0;
	while(isdigit(S[i]))
		i++;
	if(i == A && S[A] == '-'){
		while(isdigit(S[i+1]))
			i++;
	}
	if(i == A + B)
		printf("Yes\n");
	else
		printf("No\n");
	return 0;
}

Measured memory_bytes: 128
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#define MN 801000

int l[MN], r[MN];
long long Min[MN], lazy[MN], f[MN];
typedef std::pair<int, int> P;
std::vector<P> v[MN];

void add(int x, long long v)
{
	lazy[x] += v; Min[x] += v;
}

void pushdown(int x)
{
	if(lazy[x])
	{
		add(x << 1, lazy[x]);
		add(x << 1 | 1, lazy[x]);
		lazy[x] = 0;
	}
}

void build(int x, int L, int R)
{
	l[x] = L; r[x] = R;
	if(L == R) return;
	build(x << 1, L, L + R >> 1);
	build(x << 1 | 1, (L + R >> 1) + 1, R);
}

void modify(int x, int L, int R, long long v)
{
	if(l[x] == L && r[x] == R) {add(x, v); return;}
	pushdown(x); int mid = l[x] + r[x] >> 1;
	if(R <= mid) modify(x << 1, L, R, v);
	else if(L > mid) modify(x << 1 | 1, L, R, v);
	else modify(x << 1, L, mid, v), modify(x << 1 | 1, mid + 1, R, v);
	Min[x] = std::min(Min[x << 1], Min[x << 1 | 1]);
}

long long query(int x, int L, int R)
{
	if(l[x] == L && r[x] == R) return Min[x];
	pushdown(x); int mid = l[x] + r[x] >> 1;
	if(R <= mid) return query(x << 1, L, R);
	else if(L > mid) return query(x << 1 | 1, L, R);
	else return std::min(query(x << 1, L, mid), query(x << 1 | 1, mid + 1, R));
}

int main()
{
	int n, m; scanf("%d%d", &n, &m);
	
	long long sum = 0;
	for(int i = 1; i <= m; i++)
	{
		int l, r, a; scanf("%d%d%d", &l, &r, &a);
		v[r].push_back(P(l, a));
		sum += a;
	}
	
	build(1, 0, n);
	
	for(int i = 1; i <= n + 1; i++)
	{
		f[i] = query(1, 0, i - 1);
		if(i != n + 1) modify(1, i, i, f[i]);
		int S = v[i].size();
		for(int j = 0; j < S; j++)
		{
			modify(1, 0, v[i][j].first - 1, v[i][j].second);
		}
	}
	
	printf("%lld\n", sum - f[n + 1]);
}

Measured memory_bytes: 45440
use proconio::{input, marker::Usize1};
fn main() {
    let info = Info::read();
    input!(ans: [Usize1; info.day]);
    for i in 0..info.day {
        println!("{}", info.score(&ans[..=i]));
    }
}
struct Info {
    day: usize,
    dec: Vec<i32>,
    inc: Vec<Vec<i32>>,
}
impl Info {
    fn read() -> Self {
        input!(d: usize, c: [i32; 26], s: [[i32; 26]; d]);
        Self {
            day: d,
            dec: c,
            inc: s,
        }
    }
    fn score(&self, ans: &[usize]) -> i32 {
        let mut last = vec![-1; 26];
        ans.iter().enumerate().fold(0, |score, (date, &contest)| {
            last[contest] = date as i32;
            (0..26).fold(score + self.inc[date][contest], |score, contest| {
                score - self.dec[contest] * (date as i32 - last[contest])
            })
        })
    }
}


Measured memory_bytes: 2184
import sys
patterns = [
	[1, 2, 1, 2, 1, 4, 1, 4],
	[1, 2, 1, 4, 1, 4, 1, 2],
	[1, 4, 1, 2, 1, 2, 1, 4],
	[1, 4, 1, 4, 1, 2, 1, 2],
	[2, 1, 2, 1, 4, 1, 4, 1],
	[2, 1, 4, 1, 4, 1, 2, 1],
	[4, 1, 2, 1, 2, 1, 4, 1],
	[4, 1, 4, 1, 2, 1, 2, 1],
]

while True:
	try:
		p = [int(x) for x in raw_input().split()]
		m = 999999999
		for ptn in patterns:
			rem = sum(max(0, v - x) for v, x in zip(ptn, p))
			if rem < m:
				m = rem
				pt = ptn
		print " ".join([str(x) for x in pt])
	except:
		break

Measured memory_bytes: 4268
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// #pragma GCC optimize("unroll-loops,no-stack-protector")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
// using namespace __gnu_pbds;
using namespace std;
 
// template <typename T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long ll;
typedef long double ld;
typedef pair<long long ,long long> ii; 	
typedef complex<long double> com;

ll n;
vector <vector<ll>> graph;
vector <ii> edge;
ll temp = 0;


bool dfs(ll u ,ll v,ll p = 0){
	if (u == v) return true;
	for (int z=0;z<graph[u].size();z++){
		if (graph[u][z] == p) continue;
		if(dfs(graph[u][z],v,u)){
			if (graph[u][z] < u) {
				auto it = lower_bound(edge.begin(),edge.end(),make_pair(graph[u][z],u));
				temp |= ll(1) << (it-edge.begin());
			}
			else {
				auto it = lower_bound(edge.begin(),edge.end(),make_pair(u,graph[u][z]));
				temp |= ll(1) << (it-edge.begin());
			}
			return true;
		}
	}
	return false;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	graph.resize(n+1);
	for (int z=0;z<n-1;z++){
		ll u,v;
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
		if (u < v) edge.push_back(make_pair(u,v));
		else edge.push_back(make_pair(v,u));
	}
	sort(edge.begin(),edge.end());
	ll m;
	cin >> m;
	vector <ii> rules(m);
	for (int z=0;z<m;z++){
		cin >> rules[z].first >> rules[z].second;
	}
	vector <ll> edges(m,0);
	for (int z=0;z<m;z++){
		temp = 0;
		dfs(rules[z].first,rules[z].second);
		edges[z] = temp;
	}
	ll i = 0;
	ll ans = ll(1) << (n-1);
	ll tt = 0;
	for (int i=0;i<(ll(1) << m);i++){
		if (__builtin_popcountll(i) < 1) continue;
		tt = 0;
		for (int z=0;z<m;z++){
			if (i & (ll(1) << z)){
				tt |= edges[z];
			}
		}
		ll hh = __builtin_popcountll(tt);
		if (__builtin_popcountll(i) & 1) ans -= ll(1) << (n-1-hh);
		else ans += ll(1) << (n-1-hh);
	}
	cout << ans << endl;
}
 

Measured memory_bytes: 256
#include <algorithm>
#include <vector>
#include <iostream>
#include <numeric>

using namespace std;

int main(){

  int N;
  cin >>N;
  vector<int> A(N),B(N),C(N-1);
  for(int i=0;i<N;i++)cin >>A[i];
   for(int i=0;i<N;i++)cin >>B[i];
   for(int i=0;i<N-1;i++)cin >>C[i];
  
  int ans = accumulate(B.begin(),B.end(),0);
   for(int i=0;i<N-1;i++){
   	if(A[i] == A[i+1] -1)ans+=C[A[i]-1];
   }
  cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.*;
import java.math.BigInteger;
import java.security.NoSuchAlgorithmException;
import java.util.ArrayList;
import java.util.HashMap;

public class Main {
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int A = sc.nextInt();
		int B = sc.nextInt();
		if(A % 3 == 0 || B % 3 == 0 || (A+B) % 3 == 0) {
			System.out.println("Possible");
		} else {
			System.out.println("Impossible");
		}
	}
}

Measured memory_bytes: 23764
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<sstream>
using namespace std;
typedef  long long int lint;
typedef pair<int, int> P;
typedef pair<lint, lint> LLP;
typedef pair<char, char>CP;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define sort(v) sort((v).begin(), (v).end())
#define reverse(v) reverse((v).begin(), (v).end())
#define upper(v,hoge) upper_bound(v.begin(),v.end(),hoge)
#define lower(v,hoge) lower_bound(v.begin(),v.end(),hoge)
#define llower(v,hoge) *lower_bound(v.begin(), v.end(), hoge)
#define lupper(v,hoge) *upper_bound(v.begin(), v.end(), hoge)

const lint MOD = pow(10, 9) + 7;

/*
vector<char>al(26);
al = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
vector<char>AL(26);
AL = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
vector<char>NUM(10);
	NUM = { '0','1','2' ,'3' ,'4' ,'5' ,'6' ,'7' ,'8' ,'9' };
*/


int main() {
	string S;
	cin >> S;
	if (S <= "2019/04/30") {
		cout << "Heisei" << endl;
	}
	else {
		cout << "TBD" << endl;
	}
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using P = pair<ll, ll>;
#define rep(i, n)  for (int i = 0; i <  (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define all(x) (x).begin(), (x).end()
const ll INF = ll(1e18)+1;

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

    ll l,r,d;
    ll result=0;
    cin >> l >> r >> d;

    rep(i,r-l+1){
        // cout << i+l << "\n";
        if((i+l) % d == 0) result++;
    }

    cout << result;
}

Measured memory_bytes: 3620
import java.util.Scanner;
 
    class Main {
      public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
       
       int a = sc.nextInt();
       int b = sc.nextInt();
       int c = sc.nextInt();
      
       int i = 0;
 
       if(a == b && b == c && a % 2 == 0 ) {
       i = -1;
       } else {
       while(a % 2 == 0 && b % 2 == 0 && c % 2 == 0) {
           int A = a;
           int B = b;
           int C = c;
          
           a = B/2 + C/2;
           b = C/2 + A/2;
           c = A/2 + B/2;
           i++;
       }
       }
      System.out.println(i);
  }
}

Measured memory_bytes: 23764