akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#define ll long long
#define N 200005
using namespace std;
int n,x,y;
struct pi{
	ll a,b;
	pi(){};
	pi(ll _a,ll _b){
		a=_a;b=_b;
	}
}tmp[N];
vector<pi>h[N];
struct pl{int l,r,lv,rv;}s[N];
void add(int a,int b,int c){
	if(s[a].l==0) s[a].l=b,s[a].lv=c;
	else s[a].r=b,s[a].rv=c;
}
bool cmp(const pi &A,const pi &B){return A.a<B.a||A.a==B.a&&A.b<B.b;} 
void dfs(int a,int fa,ll v,int w){
	if(s[a].l==0){h[a].push_back(pi(w,w));return;}
	else dfs(s[a].l,a,v,s[a].lv),dfs(s[a].r,a,v,s[a].rv);
	if(h[s[a].l].size()>h[s[a].r].size()) swap(s[a].l,s[a].r),swap(s[a].lv,s[a].rv);
	int l=0,top=0;
	for(int i=0;i<h[s[a].l].size();i++){
		while(l<h[s[a].r].size()&&h[s[a].r][l].a+h[s[a].l][i].b<=v) l++;
		if(l!=0) top++,tmp[top]=pi(h[s[a].l][i].a+w,h[s[a].r][l-1].b+w);
	}
	int tip=top;
	for(int i=1;i<=tip;i++)
		if(tmp[i].a!=tmp[i].b) top++,tmp[top]=pi(tmp[i].b,tmp[i].a);
	sort(tmp+1,tmp+1+top,cmp);
	if(top!=0) h[a].push_back(tmp[1]);
	for(int i=2;i<=top;i++)
		if(tmp[i].b<h[a][h[a].size()-1].b) h[a].push_back(tmp[i]);
}
int main()
{
	//freopen("cc.in","r",stdin);
	//freopen("cc.out","w",stdout);
	scanf("%d",&n);
	for(int i=2;i<=n;i++) scanf("%d%d",&x,&y),add(x,i,y);
	ll l=0,r=1e11;
	while(l+1<r){
		ll mid=(l+r)/2;
		for(int i=1;i<=n;i++) h[i].clear();
		dfs(1,0,mid,0);
		if(h[1].size()!=0) r=mid;else l=mid;
	}
	for(int i=1;i<=n;i++) h[i].clear();
	dfs(1,0,l,0);if(h[1].size()!=0) r--;else l++;
	printf("%lld\n",l);
	return 0;
}

Measured memory_bytes: 31864
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAXN = 200000 + 10;

int n;
int a[MAXN];
string s;


int cnt[200];
int32_t main() {
    ios_base::sync_with_stdio(0);
    cin >> s;

    for (int i = 0; i < s.length(); i++) {
        cnt[s[i]]++;
    }

    int res = 0;
    for (int i = 'a'; i <= 'z'; i++) {
        for (int j = i+1; j <= 'z'; j++) {
            res += cnt[i]*cnt[j];
        }
    }

    cout << res + 1 << "\n";
    return 0;
}


Measured memory_bytes: 720
#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) REP(i, 0, n)
#define rrep(i, n) for (int i = (int)(n-1); i >= 0; i--)
#define sz(x) int(x.size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define INF 2e9
#define LINF 1e18
template<class T> inline bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> P;
 
int main() {
    int a, b; cin >> a >> b;
    cout << (b%a==0 ? a+b : b-a) << endl;
}

Measured memory_bytes: 256
/*B - ATCoder*/
#include <iostream>
#include <string>
using namespace std;

int main() 
{
  int flag = 0;  
  string s,result="";
  cin >> s;

  for(int i=1; i<=s.size(); i++)
  {
    for(int j=0; j+i-1<s.size(); j++)
    {
      string tmp = s.substr(j,i);
//      cout << tmp << endl;
      for(int k=0; k<tmp.size();k++)
      {
        if( tmp[k] == 'A' or tmp[k] == 'C' or tmp[k] == 'G' or tmp[k] == 'T' )
          flag = 1;
        else
        {
          flag = 0;
          break;
        }
      }
      if(flag) result = tmp; 
      flag = 0;
    }
  }

  int num = result.size();
  cout << num << endl;
  return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    string s;
    cin >> s;
    int len = s.size();
    int count0 = 0, count1 = 0;
    for (int i = 0; i < len; i++)
    {
        if (s[i] == '0')
        {
            count0++;
        }
        else
        {
            count1++;
        }
    }
    cout << min(count0, count1) * 2 << endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using intl = long long;
using ld = long double;
using namespace std;
#define rep(i, n) for(intl i = 0; i < (intl)(n); i++)
#define repd(i, n) for(intl i = (intl)(n); i >= 0; i--)
#define repi(i, a, b) for(intl i = (intl)(a); i < (intl)(b); i++)
#define repid(i, a, b) for(intl i = (intl)(a); i >= (intl)(b); i--)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define all(x) (x).begin,(x).end()
#define m0(x) memset(x,0,sizeof(x))
#define m1(x) memset(x,1,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))
#define alength(a) (sizeof(a) / sizeof(a[0]))
#define cin(i, a) rep(i, alength(a))cin >> a[i]
#define ccin(i, j, a) rep(i, alength(a))rep(j, alength(a[i]))cin >> a[i][j]
#define debug(x) cout << #x << ":" << x << endl
#define rdebug(i,x) rep(i, alength(x))cout << #x << "[" << i << "]:" << x[i] << endl
#define sqrt sqrtl
#define int intl
#define itn intl
#define double ld
#define pb push_back
#define mp make_pair
const intl INF = 1e9;
const intl MOD = 1e9+7;
const ld eps = 1.0e-14;//-9
void fp(bool flag){
    if(flag)cout << "Yes" << endl;
    else cout << "No" << endl;
}
void fp(bool flag, string s, string t){
    if(flag)cout << s << endl;
    else cout << t << endl;
}
intl kai(intl k){
    intl a = 1;
    for(int i = 2; i <= k; i++){
        a *= i;
    }
    return a;
}
intl gcd(intl a, intl b){
    if(!b)return a;
    return gcd(b, a % b);
}
intl digit10(intl a){
    if(!a)return 1;
    intl b = 0;
    while(a){
        a /= 10;
        b++;
    }
    return b;
}
signed main(){
    cout << fixed << setprecision(10);
    intl n,m;
    cin >> n >> m;
    intl s[m],c[m];
    rep(i,m){
        cin >> s[i] >> c[i];
    }
    intl ans = -1;
    rep(i,1000){
        bool flag = true;
        intl d = digit10(i);
        if(n != d)continue;
        intl a[3];
        fill(a,-1);
        intl b = i;
        rep(j,d){
            a[n - 1 - j] = (b % 10);
            b /= 10;
        }
        //cout << "a0:" << a[0] << " a1:" << a[1] << " a2:" <<  a[2] << endl;
        rep(j,m){
            if(a[s[j] - 1] != c[j])flag = false;
        }
        if(flag){
            ans = i;
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
char a[105];
int main()
{
	ios::sync_with_stdio(false);
	gets(a);
	int len=strlen(a);
	cout<<a[0];
	for(int i=1; i<len; i++)
		if(a[i]==' ')
			cout<<a[i+1];
	cout<<endl;
	return 0;
}

Measured memory_bytes: 256
# coding: utf-8

# In[ ]:

import sys
input = sys.stdin.readline
N, K = map(int, input().split())
S = input()


# In[5]:

ks = S[K-1].lower()
#ks = ks.lower()
#start_i = i-1 if i>0 else 0
S = S[:K-1] + ks + S[K:]
print(S)


# In[ ]:





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

using namespace std;

typedef long long ll;
typedef pair<int, int> PII;
typedef double db;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pct __builtin_popcount

#define N 15

struct P {
  int x, y;
  P(){}
  P(int _x, int _y):x(_x), y(_y) {}
  P operator + (const P&a) const {return P(x+a.x, y+a.y);}
  P operator - (const P&a) const {return P(x-a.x, y-a.y);}
  ll dot (const P&a) const {return (ll)x*a.x + (ll)y*a.y;}
  ll crs (const P&a) const {return (ll)x*a.y - (ll)y*a.x;}
  db dis (const P&a) const {return sqrt((ll)(x-a.x)*(x-a.x) + (ll)(y-a.y)*(y-a.y));}
} a[N];

int n, c[N];
db f[1<<N];
db g[1<<N];

int fn[N];
int fa(int x) {
	if (x == fn[x]) return x;
	return fn[x] = fa(fn[x]);
}

bool cmp(PII x, PII y) {
	return a[x.fi].dis(a[x.se]) < a[y.fi].dis(a[y.se]);
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i ++)
		cin >> a[i].x >> a[i].y >> c[i];
	for (int p = 1; p < (1<<n); p ++) {
		vector<PII> b;
		for (int i = 0; i < n; i ++)
			for (int j = i+1; j < n; j ++)
				if (((p>>i)&1) && ((p>>j)&1))
					b.pb(mp(i, j));
		sort(b.begin(), b.end(), cmp);
		for (int i = 0; i < n; i ++) fn[i] = i;
		db dd = 0;
		for (int i = 0; i < (int) b.size(); i ++)
			if (fa(b[i].fi) != fa(b[i].se)) {
				dd += a[b[i].fi].dis(a[b[i].se]);
				fn[fa(b[i].fi)] = fa(b[i].se);
			}
		for (int i = 0; i < n; i ++)
			if ((p>>i)&1) g[p] += c[i];
		(g[p] -= dd) /= pct(p);
	}
	memset(f, 0, sizeof f);
	f[0] = 1e10;
	for (int p = 0; p < (1<<n); p ++) {
		vector<int> b;
		for (int i = 0; i < n; i ++)
			if (~(p>>i)&1) b.pb(i);
		int bs = (int) b.size();
		for (int q = 1; q < (1<<bs); q ++) {
			int c = 0;
			for (int j = 0; j < bs; j ++)
				if ((q>>j)&1) c |= (1<<b[j]);
			f[p|c] = max(f[p|c], min(f[p], g[c]));
		}
	}
	printf ("%.9lf\n", f[(1<<n)-1]);
	return 0;
}

Measured memory_bytes: 768
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define rrep(i,n) for (int i = n-1; i >= 0; i--)
#define rep2(i,s,n) for (int i = s; i < n; ++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define tmax(a,b,c) max(a,max(b,c))
#define tmin(a,b,c) min(a,min(b,c))
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<P>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using LP = pair<ll,ll>;
template<class T> istream& operator>>(istream& is,vector<T>& v) { for(T& t:v){is>>t;} return is; }
template<class T> ostream& operator<<(ostream& os,const vector<T>& v) { for(T t:v){os<<t<<" ";} os<<"\n"; return os; }
void Yes(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YES(bool b) { cout << (b ? "YES" : "NO") << endl; }
template<class T> inline bool chmin(T& a,T b) {if(a > b){a = b; return true;} return false;}
template<class T> inline bool chmax(T& a,T b) {if(a < b){a = b; return true;} return false;}
const int inf = 1001001001;
const ll linf = 1001001001001001001;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int n,a,b,c;
    cin >> n >> a >> b >> c;
    vs S(n);
    cin >> S;
    vc ans;
    rep(i,n) {
        string s = S[i];
        if(s == "AB") {
            if(a == 0 && b == 0) {
                Yes(0);
                return 0;
            }
            if(a == 1 && b == 1 && i < n-1) {
                if(S[i+1] == "BC") {
                    a--; b++;
                    ans.pb('B');
                } else {
                    a++; b--;
                    ans.pb('A');
                }
            } else if(a >= b) {
                a--; b++;
                ans.pb('B');
            } else {
                a++; b--;
                ans.pb('A');
            }
        } else if(s == "BC") {
            if(b == 0 && c == 0) {
                Yes(0);
                return 0;
            }
            if(b == 1 && c == 1 && i < n-1) {
                if(S[i+1] == "AC") {
                    b--; c++;
                    ans.pb('C');
                } else {
                    b++; c--;
                    ans.pb('B');
                }
            } else if(b >= c) {
                b--; c++;
                ans.pb('C');
            } else {
                b++; c--;
                ans.pb('B');
            }
        } else {
            if(c == 0 && a == 0) {
                Yes(0);
                return 0;
            }
            if(c == 1 && a == 1 && i < n-1) {
                if(S[i+1] == "AB") {
                    c--; a++;
                    ans.pb('A');
                } else {
                    c++; a--;
                    ans.pb('C');
                }
            } else if(c >= a) {
                c--; a++;
                ans.pb('A');
            } else {
                c++; a--;
                ans.pb('C');
            }
        }
    }
    Yes(1);
    rep(i,n) cout << ans[i] << endl;
}

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

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    int ans = 0;
    for(int i=0;i<n;i++){
        cin >> a[i];
        if(i%2 == 0 && a[i]%2 == 1) ans++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3596
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
a = LIST()

xor = lambda x, y: x^y
ret = reduce(xor, a)
print("No" if ret else "Yes")


Measured memory_bytes: 16236
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
const ll MOD = 1000000007;

int main() {
    int n, k;
    string s;
    cin >> n >> k >> s;
    int cnt = 0;
    rep(i, n-1) {
        if (s[i] == s[i+1])
            cnt++;
    }
    int ans = cnt + 2 * k;
    cout << min(ans, n-1) << endl;
}

Measured memory_bytes: 512
#include <stdio.h>

int main(void) {

  long n;
  scanf("%ld", &n);
  long a[n];
  for (long i = 0; i < n; i++) {
    scanf("%ld", &a[i]);
  }
  long count = 0;
  long number;
  for (long i = 0; i < n; i++) {
    number = a[i];
    while (number%2 == 0) {
      number /= 2;
      count++;
    }
  }
  printf("%ld\n", count);

  return 0;
}

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

H = W = 100
ans = [['.#'[i//50]]*W for i in range(H)]

A -= 1
B -= 1

i = j = 0
while B:
    ans[i][j] = '#'
    j += 2
    if j >= W:
        j = 0
        i += 2
    B -= 1

i = 52
j = 0
while A:
    ans[i][j] = '.'
    j += 2
    if j >= W:
        j = 0
        i += 2
    A -= 1

print(H,W)
for row in ans:
    print(''.join(row))

Measured memory_bytes: 3064
//的場梨沙★担当
//結城晴★副担当
//日野茜★副担当
#include <vector>
#include <list>
#include <map>
#include <climits>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string.h>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <random>
#include <cctype>
#include <complex>
#include <regex>
#include <unordered_map>
#include <string>
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <stdio.h>


using namespace std;

int main(void) {
    long long int N;
    cin>>N;

    long long int A=N/500;
    long long int B=(N-500*A)/5;

    long long int ans=A*1000+B*5;

    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdbool.h>

int main(void)
{
    int n, a[200];
    int i, j;
    int ans = 0;
    bool flag = false;
    scanf("%d", &n);
    for (i=0; i<n; i++)
    {
        scanf("%d", &a[i]);
    }

    while (flag == false) {
        for (i=0; i<n; i++)
        {
            if (a[i]%2 != 0) {
                flag = true;
                break;
            }
        }
        if (flag == false) {
            for (i=0; i<n; i++)
            {
                a[i] = a[i]/2;
            }
            ans ++;
        }
    }

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


Measured memory_bytes: 128
A, B, C, X, Y = map(int, input().split())

cost_temp = float('inf')

for i in range(max(X,Y)+1):
    cost = i * 2 * C + A * max(0, X-i) + B * max(0, Y-i)
    if cost < cost_temp:
        cost_temp = cost

print(cost_temp)

Measured memory_bytes: 3060
def sign(x1, y1, x2, y2, xp, yp)
  return x1 <=> xp if x1 == x2
  yp <=> (y2 - y1)/(x2 - x1) * (xp - x1) + y1
end

while line = gets
  x1, y1, x2, y2, x3, y3, xp, yp = line.split.map(&:to_f)
  
  xg = (x1 + x2 + x3) / 3.0
  yg = (y1 + y2 + y3) / 3.0

  sign_equal = sign(x1, y1, x2, y2, xg, yg) == sign(x1, y1, x2, y2, xp, yp) &&
               sign(x1, y1, x3, y3, xg, yg) == sign(x1, y1, x3, y3, xp, yp) &&
               sign(x2, y2, x3, y3, xg, yg) == sign(x2, y2, x3, y3, xp, yp)
  
  puts sign_equal ? 'YES' : 'NO'
end

Measured memory_bytes: 8656
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<time.h>
#include<tuple>
#include<set>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define vint vector<int> 
#define vvint vector<vint>
#define ct(a) cout<<a<<endl
#define tget(a,b) get<a>(b)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const int MOD = 1e9 + 7;


int N;
int main(void) {
	set<int> st;
	cin >> N;
	FOR(i, 0, N) {
		int a = 0;
		cin >> a;
		st.insert(a);
	}
	cout << st.size() << endl;
	
	return 0;
}

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

int main() {
  int N;
  cin >> N;
  
  for (int i = 0; i < N; i++) {
    string s;
    cin >> s;
    
    if (s == "Y") {
      cout << "Four" << endl;
      break;
    }
    else if (i == N - 1) {
      cout << "Three" << endl;
    }
  }
}

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

int main(){
  int x = 0, y = 0;
  string s;
  cin >> s;
  rep(i, s.size(), 0){
    if(2*i >= s.size()) break;
    else{
      if(s[2*i] == '0') x++;
      else y++;
    }
    if(2*i+1 >= s.size()) break;
    else{
      if(s[2*i+1] == '1') x++;
      else y++;
    }
  }
  cout << min(x, y) << endl;
}

Measured memory_bytes: 512
#include<stdio.h>

int main()
{
	int a,b,x,y,o,p;
	scanf("%d %d",&a,&b);
	if(a>b)
	{x=a;y=b;}
	if(a<=b)
	{x=b;y=a;}
	
	while(y>0)
	{o=x%y;
	x=y;
	y=o;}
	
	printf("%d\n",x);
	
	return 0;
}

Measured memory_bytes: 592
N,A,B,C,D = map(int, input().split())

ans = "NO"
B -= A
for i in range(N):
    num = i*D - (N-1-i)*D
    if num-i*(D-C) <= B <= num+(N-i-1)*(D-C):
        ans = "YES"
        break

print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h> 
#define rep(i,n) for(long long i = 0; i < (long long)(n); i++)
#define per(i,n) for(long long i = (long long)(n-1);i >= 0;--i)
#define REP(i,s,t) for(long long i=s;i<t;i++)
#define PER(i,s,t) for(long long i=s;i>t;--i)
#define all(x) x.begin(),x.end()
#define sp(n) setprecision(n)
typedef long long ll;
using namespace std;
int main(){
  int a,b;
  cin>>a>>b;
  int c=a*b;
  cout<<c<<endl;
}

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

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

const int INF = 1e9 + 7;

using namespace std;

vector<vector<int>> c(10, vector<int>(10));

int dfs(int i, int sum, int ed, vector<int> memo) {

	memo[i] = 1;
	int tmp = sum + c[i][1];
	rep (j, 0, 10) {
		if (j == 1)
			continue;

		if (memo[j] != 1) {
			tmp = min(tmp, dfs(j, sum + c[i][j], ed, memo));
		}
	}

	return tmp;
}

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

	int h, w;
	cin >> h >> w;

	rep (i, 0, 10)
		rep (j, 0, 10)
		cin >> c[i][j];

	vector<vector<int>> a(h, vector<int>(w));
	rep (i, 0, h)
		rep (j, 0, w)
		cin >> a[i][j];

	vector<int> route(10, INF);
	rep (i, 0, 10) {
		vector<int> memo(10, 0);
		if (i == 1)
			continue;
		route[i] = dfs(i, 0, c[i][1], memo);
	}

	int res = 0;
	rep (i, 0, h) {
		rep (j, 0, w) {
			if (a[i][j] != -1 && a[i][j] != 1)
				res += route[a[i][j]];
		}
	}

	cout << res << endl;
	return 0;
}


Measured memory_bytes: 384
//R<3S
#include <bits/stdc++.h>
#define hell 1000000007
#define PI 3.14159265358979323844
#define mp make_pair
#define pb push_back
#define fi first 
#define se second
#define ALL(v) v.begin(), v.end()
#define SORT(v) sort(ALL(v))  
#define REVERSE(v) reverse(ALL(v))
#define endl "\n"
#define vecmax(v) max_element(all(v))
#define vecmin(v) min_element(all(v))
#define GCD(m,n) __gcd(m,n)
#define LCM(m,n) m*(n/GCD(m,n))
#define rep(i, n)    for(int i = 0; i < (n); ++i)
#define repA(i, a, n)  for(int i = a; i <= (n); ++i)
#define repD(i, a, n)  for(int i = a; i >= (n); --i)
#define trav(x) for(auto i : x)
#define sz(a) (int)a.size()
#define sl(a) (int)a.length()
#define int long long
#define ld long double 
#define pii std::pair<int, int> 
#define pll std::pair<ll, ll>  
#define vi vector<int>  
#define vl vector<ll>
#define vvi vector<vi > 
#define vii vector<pii >
#define mii map<int,int>
#define mll map<ll,ll>


using namespace std;
int dp[101][100005];
int pre[101][100005];
void solve()
  {
  	int n,k;
  	cin>>n>>k;
  	int a[n+1];
  	rep(i,n)cin>>a[i+1];
	
	rep(i,k+1) pre[0][i]=1;
	dp[0][0]=1;
	
	// dp[i][j] is the number of ways of distribute j candies among first i children
	repA(i,1,n)
	{
		
		
		repA(j,0,k)
		{
			
			
			
				dp[i][j]=(pre[i-1][j]-(j-a[i]-1>=0?pre[i-1][j-a[i]-1]:0)+hell)%hell;
				pre[i][j]=(dp[i][j]+(j?pre[i][j-1]:0))%hell;
			
		}
	}
	cout<<dp[n][k];

  }



signed main()
{
   std::ios_base::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);
   int t;
   t=1;
   //cin>>t;
   while(t--)
    {
        solve();
    }


   return 0;
}


Measured memory_bytes: 160660
/*
    飲んだ魔剤で家が建つ。
    created at: 2020-03-28 21:01:14
*/

#include <bits/stdc++.h>
using namespace std;

#define all(x) (x).begin(),(x).end()
#define rep(x, y) for (int x = 0; x < y; x++)
#define MOD 1000000007

typedef long long LL;
typedef long double LD;

bool compare_by_b(pair<int, int> a, pair<int, int> b)
{
    if (a.second != b.second) {
        return a.second < b.second;
    } else {
        return a.first < b.first;
    }
}

LL modpower(LL n, LL m, LL mod) {
    if (m == 0) {
        return 1;
    } else if (m % 2 == 0) {
        LL p = modpower(n, m/2, mod);
        return p*p % mod;
    } else {
        return n*modpower(n, m-1, mod) % mod;
    }
}

LL modinv(LL n, LL mod) {
    return modpower(n, mod-2, mod);
}

LL modcombination(LL n, LL r, LL mod) {
    LL ret = 1;

    for (int i = 0; i < r; i++) {
        ret *= (n-i);
        ret %= mod;
        ret *= modinv(i+1, mod);
        ret % mod;
    }

    return ret % mod;
}

ostringstream oss_global;
string s_global = oss_global.str();

int main()
{
    LL x;
    cin >> x;

    LL a, b;
    a = x / 500;
    x -= 500*a;
    b = x / 5;

    // cout << a << " " << b << endl;

    LL ans = 1000*a + 5*b;
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
def main():
    n = int(input().strip())

    for i in range(100//4+1):
        m = i * 4
        if n < m:
            break
        for j in range(0, n//7+1):
            #print(i, j)
            m = i * 4 + j * 7
            if n == m:
                print('Yes')
                return
            if n < m:
                break


    print('No')

if __name__ == '__main__':
    main()


Measured memory_bytes: 38384
#include <stdio.h>

int main(void)
{
	int a,b,c;
	char str[16];
	
	fgets(str,sizeof(str),stdin);
	sscanf(str,"%d %d %d",&a,&b,&c);
	
	if((b-a) == (c-b))
	{
		puts("YES");
	}
	else
	{
		puts("NO");
	}
	return 0;
}

Measured memory_bytes: 128
S=input()
a=int(S[:2])
b=int(S[2:])
if((0<a and a<=12)and(0<b and b<=12)):
  print("AMBIGUOUS")
elif(not(0<a and a<=12)and(0<b and b<=12)):
  print("YYMM")
elif((0<a and a<=12)and not(0<b and b<=12)):
  print("MMYY")
else:
  print("NA")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

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

    string num="0123456789";

    bool can=true;
    for (int i=0;i<a;i++){
	bool ch=false;
	for (int j=0;j<10;j++){
	    if (s[i] == num[j]){
		ch=true;
		break;
	    }
	}
	if (!ch) can=false;
    }
    if (s[a] != '-') can=false;
    for (int i=a+1;i<=a+b;i++){
	bool ch=false;
	for (int j=0;j<10;j++){
	    if (s[i] == num[j]){
		ch=true;
		break;
	    }
	}
	if (!ch) can=false;
    }

    if (can){
	cout << "Yes" << endl;
    } else cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 768
using System;
class program{
  static void Main(){
    int k = int.Parse(Console.ReadLine());
    if(k%2 == 0){
      Console.Write(-1);
      Environment.Exit(0);
    }else if(k%5 == 0){
      Console.Write(-1);
      Environment.Exit(0);
    }else if(k%7 == 0){
      k = k/7;
    }
    int ans = 1,i=1;
    i %= k;
    while(i != 0){
      i = 10*i+1;
      i %= k;
      ans++;
    }
    Console.Write(ans);
  }
}

Measured memory_bytes: 27700
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <complex>
#include <algorithm>
#include <numeric>
#include <utility>
#include <tuple>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <random>
#include <iterator>

using namespace std;
using i64 = int64_t;
using i32 = int32_t;

i64 n, m;
vector<vector<int>> g;

vector<int> col;
bool dfs(int u, int p, int c) {
    if (col[u] == -c) return false;
    if (col[u] == c) return true;
    col[u] = c;
    bool res = true;
    for (int v : g[u]) {
        if (v == p) continue;
        res = dfs(v, u, -c) & res;
    }
    return res;
}

int main() {
    cin >> n >> m;
    g.resize(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    col.resize(n + 1);
    i64 cnt[2] = {};
    i64 iso = 0;
    for (int u = 1; u <= n; ++u) {
        if (g[u].size() == 0) {
            ++iso;
        } else if (col[u] == 0) {
            cnt[dfs(u, 0, 1)]++;
        }
    }
    cerr << "isolated: " << iso << endl;
    cerr << "cnt[0]: " << cnt[0] << endl;
    cerr << "cnt[1]: " << cnt[1] << endl;
    i64 ans = n * n - (n - iso) * (n - iso) + cnt[1] * cnt[1] + (cnt[0] + cnt[1]) * (cnt[0] + cnt[1]);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 10880
#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<b;i++)
using namespace std;
char to(char c)
{
    return c - 'a' + 'A';
}
int main()
{
    string a, b, c;
    cin >> a >> b >> c;
    cout << to(a[0]) << to(b[0]) << to(c[0]) << endl;
}

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

int main(){
  int N;
  cin>>N;
  long long ans=0;
  long long A[N+1];
  long long temp=0;
  
  if(N==1){
    cin>>temp;
    cout<<temp/2<<endl;
    return 0;
  }
  
  for(int i=1;i<=N;i++){
    cin>>A[i];
  }
  
  for(int i=1;i<N;i++){
    temp=(A[i]+A[i+1])/2;
    //cout<<i<<" "<<temp<<" "<<A[i]<<" "<<A[i+1]<<endl;
    ans+=temp;
    if(temp>0){
      A[i+1]=A[i]+A[i+1]-temp*2;
    }
  }
  
  cout<<setprecision(20)<<ans<<endl;
  return 0;
}

 

Measured memory_bytes: 4416
x,k,d=map(int,input().split())

x=abs(x)
if x>=k*d:
    print(x-k*d)
else:
    xpd=x//d
    k3=k-xpd
    if k3%2==0:
        print(x-xpd*d)
    else:
        print(abs(x-xpd*d-d))
        

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

void count(int n, vector<unordered_set<int>> &friends, vector<bool> &done, unordered_set<int> &s){
  if(done[n]) return;
  done[n]=true;
  s.insert(n);
  for(int i: friends[n]) count(i,friends,done,s);    
}

int main(){
  int n,m;
  cin>> n >> m;
  vector<unordered_set<int>> friends(n);
  vector<bool> done(n,false);
  for(int i=0; i<m; i++){
    int a,b;
    cin>>a>>b;
    a--; b--;
    friends[a].insert(b); friends[b].insert(a);
  }
  
  int ans=1;
  for(int i=0; i<n; i++){
    unordered_set<int> s;
    count(i,friends, done,s);
    int temp=s.size();
    if(ans<temp) ans=temp;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 56760
#include <stdio.h>
 
int main(void)
 
{
  int a , b;
 
  scanf("%d %d",&a,&b);
  
  if(a + b >= 10){
  printf("error");
  } else {
  a = a + b;
  printf("%d\n",a);
  }
  return 0;
}

Measured memory_bytes: 128
#include<iostream>
using namespace std;
int main(void){
  int a,b;
  cin>>a>>b;
  int count = 0;
  for(int i = a; i<=b; i++){
      int x,y,t,s;
      x = i%10; y = i/10000%10;
      t = i/1000%10; s = i/10%10;
      if(x==y&&t==s){
          count++;
      }
  }
cout<<count<<endl;
return 0;
}

Measured memory_bytes: 256
H, W = tuple(map(int, input().split()))
A = []
for h in range(H):
    A.append([c for c in input()])
res = [["#" for _ in range(W+2)] for _ in range(H+2)]
for i in range(1, H+1):
    for j in range(1, W+1):
        res[i][j] = A[i-1][j-1]
res = ["".join(x) for x in res]
res = "\n".join(res)
print(res)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
 
using namespace std;
 
#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define eb emplece_back
#define mp make_pair
#define i_i pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< i_i >
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; scanf("%lld", &x);
#define int2(x, y) int x, y; scanf("%lld %lld", &x, &y);
typedef struct edge { int f, t, c; } edge;
 
//int dxy[5] = {0, 1, 0, -1, 0};
// assign
 
int bellman_ford(int st, int en, int n, vector<edge> &es);
int bellman_ford(int st, int en, int n, vector<edge> &es)
{
    vi d(n, INF);
    d[st] = 0;
    Rep(i, n) {
        bool update = false;
        rep(i, es.size()) {
            edge e = es[i];
            if (d[e.f] != INF && d[e.t] > d[e.f] + e.c) {
                d[e.t] = d[e.f] + e.c;
                update = true;
            }
        }
        if (!update) {
 //   rep(i, n) cout << d[i] << endl;
            return d[en];
        }
    }
//    cout << "ok" << endl;
    int bef = d[en];
    Rep(i, n) {
        bool update = false;
        rep(i, es.size()) {
            edge e = es[i];
            if (d[e.f] != INF && d[e.t] > d[e.f] + e.c) {
                d[e.t] = d[e.f] + e.c;
                update = true;
            }
        }
        if (!update) {
            return d[en];
        }
    }
    if (bef == d[en]) {
        return bef;
    } else {
        return INF;
    }
}


bool find_negative_loop(int n, vector<edge> &es);
bool find_negative_loop(int n, vector<edge> &es)
{
    vi d(n, 0);

    rep(i, n) {
        rep(j, es.size()) {
            edge e = es[j];
            if (d[e.t] > d[e.f] + e.c) {
                d[e.t] = d[e.f] + e.c;
                if (i == n - 1) return true;
            }
        }
    }
    return false;
}
 
 
signed main()
{
    int2(n, m);
    vector<edge> es(m);
 
    rep(i, m) {
        cin >> es[i].f >> es[i].t >> es[i].c;
        es[i].f--;
        es[i].t--;
        es[i].c *= -1;
    }

    int ret = bellman_ford(0, n-1, n, es);
    if (ret == INF) {
        cout << "inf" << endl;
    } else {
        cout << -ret << endl;
    }
 
    return 0;
}



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

using namespace std;

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

#define MAX_N 100000

ll dp[MAX_N], h[MAX_N], N;

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

    cin >> N;

    for (int i = 0; i < N; i++)
        cin >> h[i];

    dp[1] = abs(h[1] - h[0]), dp[0] = 0;

    for (int i = 2; i < N; i++) {
        dp[i] = min(dp[i - 2] + abs(h[i] - h[i - 2]), dp[i - 1] + abs(h[i] - h[i - 1]));
    }

    cout << dp[N - 1] << "\n";

    // --------------------
    return 0;
}

Measured memory_bytes: 1792
<?php
// 入力受付
$n = fgets(STDIN);
$a = explode(" ",fgets(STDIN));
// 最小値保持用変数、初期値は比較用
$result= 1000;
// 整数配列から各整数を変数dに取得、2で割れる回数の最小値を計算
foreach($a as $tmp){
    // 回数の初期化
    $count = 0;
    // 変数dが2で割り切れる場合、変数cをインクリメント、変数dを更新する
    while($tmp%2 == 0){
        $count = $count + 1;
        $tmp = $tmp / 2;
    }
    // 最小回数の比較
    $result = min($count ,$result);
}
// 結果出力
echo($result)
?>


Measured memory_bytes: 4728
#
import itertools
from collections import Counter
from collections import defaultdict
import bisect
from heapq import heappush, heappop

def main():
    n = int(input())
    p = list(map(int, input().split()))

    ans = 0
    for i in range(1, n - 1):
        if p[i+1] < p[i] < p[i-1] or p[i-1] < p[i] < p[i+1]:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 38448
#include <cstdio>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <stack>
#include <algorithm>
#include <random>
#include <iomanip>
#include <unordered_map>
#include <map>
#include <queue>
#include <functional>
#include <numeric>
#include <chrono>
#include <cstdlib>
using ll = long long;
using namespace std;

const ll MOD = 1e9 + 7;
//const double EPS = 1e(-12);
const double pi = acos(-1);
typedef pair<int, int> P;
#define REP(i, n) for (int(i) = 0; (i) < (n); ++(i))
#define repi(i, a, b) for (int i = int(a); i < int(b); ++i)
#define EPS 1e-4
#define OUTPUT(i) (cout << (ll)i << endl)
#define ALL(a) ((a).begin(), (a).end())

bool operator<(const pair<int, int> &a, const pair<int, int> &b)
{
    if (a.first == b.first)
    {
        return a.second < b.second;
    }
    return a.first < b.first;
}
struct UnionFind
{
    vector<int> rnk, par;

    UnionFind(int N) : par(N), rnk(N)
    {
        for (int i = 0; i < N; ++i)
        {
            rnk[i] = 1;
            par[i] = i;
        }
    }
    int root(int x)
    {
        if (par[x] == x)
            return x;
        return par[x] = root(par[x]);
    }
    void unite(int x, int y)
    {
        x = root(x);
        y = root(y);

        if (x == y)
            return;

        if (rnk[x] > rnk[y])
            par[y] = x;
        else
        {
            par[x] = y;
            if (rnk[x] == rnk[y])
                rnk[y]++;
        }
    }
    bool same(int x, int y)
    {
        x = root(x);
        y = root(y);
        return x == y;
    }
};

int ans[200010];
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    //cout << fixed << setprecision(7);

    int N, K, L;

    cin >> N >> K >> L;

    UnionFind road(N);
    set<pair<int, int>> st;
    for (int i = 0; i < K; ++i)
    {
        int p, q;
        cin >> p >> q;
        p--;
        q--;
        road.unite(p, q);
        if (p < q)
            swap(p, q);
        st.insert({p, q});
    }

    UnionFind rail(N);

    for (int i = 0; i < L; ++i)
    {
        int r, s;
        cin >> r >> s;
        r--;
        s--;
        rail.unite(r, s);
        if (r < s)
            swap(r, s);
        st.insert({r, s});
    }

    map<pair<int, int>, int> mp;
    for (int i = 0; i < N; ++i)
        mp[make_pair(road.root(i), rail.root(i))]++;

    for (int i = 0; i < N; ++i)
    {
        if (i)
            cout << " ";
        cout << mp[make_pair(road.root(i), rail.root(i))];
    }
    cout << endl;
    return 0;
}

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

constexpr long INF = 1e10;

int main() {
  long L, R;
  cin >> L >> R;

  R = min(R, L + 2019);

  long ans{2019};
  for (long i{L}; i < R; ++i) {
    for (long j{i+1}; j <= R; ++j) {
      long val = (i*j % 2019);
      if (ans > val)
        ans = val;
    }
  }

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


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 123 
typedef long long ll;
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    return x*f;
}
char s[N];
ll k,ans,l,r;
int main(){
	scanf("%s",s+1);
	int n=strlen(s+1);
	k=read();
	l=1,r=n;
	int tmp=0;
	while(s[l]==s[l+1])++l;
	while(s[r]==s[r-1])r--;
	if(l==n){
		cout<<1LL*n*k/2<<endl;
		return 0;
	}
	if(s[1]!=s[n]){
		for(int i=1;i<=n;i++){
			if(s[i]==s[i-1]){
				++tmp;
			}
			else{
				ans+=tmp/2;
				tmp=1;
			}
		}
		ans+=tmp/2;
		ans*=k;
	}
	else{
		for(int i=l+1;i<=r-1;i++){
			if(s[i]==s[i-1]){
				++tmp;
			}
			else{
				ans+=tmp/2;
				tmp=1;
			}
		}
		ans+=tmp/2;
		ans*=k;
		ans+=l/2+(n-r+1)/2+(l+(n-r+1))/2*(k-1); 
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <cassert>
#include <list>

struct Proc{
	std::string name;
	int time;
};

typedef std::list<Proc> PList;

int input(PList& vec);
int output(PList& vec);
PList calc(PList vec, int q);


int main()
{
	PList ivec;
	int q = input(ivec);
	PList ovec = calc(ivec,q);

	output(ovec);

	return 0;
}
///--------------------------------------------
int input(PList& vec)
{
	int n;
	std::cin >> n;
	//vec.resize(n);
	int q;
	std::cin >> q;
    for(int i = 0; i < n; i++){
		Proc proc;
		std::cin >> proc.name;
		std::cin >> proc.time;
		vec.push_back(proc);
	}
	return q;
}
///--------------------------------------------
int output(PList& vec)
{
	for(PList::iterator itr = vec.begin(); itr != vec.end(); itr++){
  //	for(int i = 0; i < (vec.size()); i++){
		std::cout << itr->name << " " << itr->time << std::endl;
	}
	return 0;
}
///--------------------------------------------
///@func    calc
///@brif    ??¨????
///in       ??????
///in       ???????????????
///out      ??????
///--------------------------------------------
PList calc(PList queue, int q)
{

	PList vec;
	int i = 0;
	int time = 0;
	while(true){

		if(queue.front().time > q){
			time += q;
			queue.front().time = (queue.front().time - q);
			queue.push_back(queue.front());

		}else{
			time = time + (queue.front().time );
			vec.push_back(queue.front());
			vec.back().time = time;
		}
		queue.pop_front();
		//queue.erase(queue.begin());
		if(queue.empty()){
			break;
		}
//		i++;
	}

	return vec;

}

Measured memory_bytes: 10080
n = gets.to_i
a = gets.split.map{|e|e.to_i-1}
b = gets.split.map &:to_i
c = gets.split.map &:to_i

manzoku = 0
n.times{|i|
	manzoku += b[a[i]]
	manzoku += c[a[i]] if i<=n-2 && a[i+1]==a[i]+1
}
p manzoku

Measured memory_bytes: 1788
//最短経路長が短い経路に流せるだけ流す。
//ただし、順辺のコストをcとしたときに逆辺のコストは-cにする (フローを押し戻すとき、コストも押し戻すため）。
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

const int VMAX = 100;
struct Edge {
	int from, to, flow, cost, rev;
	Edge(int from, int to, int flow, int cost, int rev) {
		this->from = from;
		this->to   = to;
		this->flow = flow;
		this->cost = cost;
		this->rev  = rev;
	}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void add_edge(Graph &g, int from, int to, int flow, int cost) {
	g[from].push_back(Edge(from, to, flow, cost, g[to].size()));
	g[to].push_back(Edge(to, from, 0, -cost, g[from].size() - 1));
}

int dfs(Graph &g, int s, int t, int flow, bool yet[], int level[]) {
	yet[s] = false;
	if (s == t) return flow;
	for (int i = 0; i < g[s].size(); i++) {
		int v = g[s][i].to;
		if (g[s][i].flow > 0 && yet[v] && level[v] == level[s] + g[s][i].cost) {
			int res = dfs(g, v, t, min(flow, g[s][i].flow), yet, level);
			if (res > 0) {
				int r = g[s][i].rev;
				g[s][i].flow -= res;
				g[v][r].flow += res;
				return res;
			}
		}
	}
	return 0;
}

int minCostflow(Graph &g, int s, int t, int flow) {
	const int INF_DIST = 11451419;
	const int INF_FLOW = 11451419;
	const int ERROR_RETURN = -1;
	int level[VMAX];
	bool yet[VMAX];
	queue<int> que;
	int i;
	int ret = 0;
	
	while (true) {
		for (i = 0; i < g.size(); i++) level[i] = INF_DIST;
		que.push(s); level[s] = 0;
		while (!que.empty()) {
			int v = que.front(); que.pop();
			for (i = 0; i < g[v].size(); i++) {
				int nv = g[v][i].to;
				if (g[v][i].flow > 0 && level[nv] > level[v] + g[v][i].cost) {
					level[nv] = level[v] + g[v][i].cost;
					que.push(nv);
				}
			}
		}
		if (level[t] >= INF_DIST) break;

		while (true) {
			for (i = 0; i < g.size(); i++) yet[i] = true;
			int f = dfs(g, s, t, INF_FLOW, yet, level);
			if (f == 0) break;
			flow -= f;
			ret += f * level[t];
			if (flow <= 0) {
				ret += flow * level[t];
				return ret;
			}
		}
	}
	return -1;
}

int n, m, f;
int u, v, c, d;
Graph g;

int main() {
	cin >> n >> m >> f;
	g.resize(n);
	for (int i = 0; i < m; i++) {
		cin >> u >> v >> c >> d;
		add_edge(g, u, v, c, d);
	}
	cout << minCostflow(g, 0, n - 1, f) << endl;
	return 0;
}


Measured memory_bytes: 3240
#反転ではない
#孤立点の有無
h,w=map(int, input().split( ))
s= ["."*(w+2)]+["."+input()+"." for _ in range(h)]+["."*(w+2)]
od=0
ev=0
nb=[(1,0),(-1,0),(0,1),(0,-1)]
for i in range(1,h+1):
    for j in range(1,w+1):
        flag=False
        for x,y in nb:
            if s[i+x][j+y]=="#":
                flag=True
                break
        if not flag and s[i][j]=="#":
            print("No")
            exit()
        
        
print("Yes")


Measured memory_bytes: 39408
#include <iostream>
#include <numeric>
#include <queue>
#include <cstring>
#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef long long ll;
typedef vector<ll> vll;
const int inf=1000000005;
typedef pair<int,int> P;
typedef pair<int,pair<int,int> > PP;
int a[100005];
int dp[100005];

int main(int argc,char const* argv[])
{
  int n;
  int ans=0;
  cin >> n;
  for(int i=0;i<n;i++)
    {
      cin >> a[i];
    }
  fill(dp,dp+100000,inf);
  for(int i=0;i<n;i++)
    {
      *lower_bound(dp,dp+n,a[i])=a[i];
    }
  cout << lower_bound(dp,dp+n,inf)-dp << endl;
  return 0;
}



Measured memory_bytes: 3864
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define BR "\n"
#define SP " "
#define SHOW(x) for(int i = 0; i < x.size(); i++) { cout << x[i] << SP; } cout << BR;
#define SHOW2(x) for(int j = 0; j < x.size(); j++) { SHOW(x[j]); } cout << BR;

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

  vector<vector<ll>> A(N, vector<ll>(M, 0));
  vector<vector<ll>> B(M, vector<ll>(L, 0));
  vector<vector<ll>> C(N, vector<ll>(L));

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      cin >> A[i][j];
    }
  }

  for (int i = 0; i < M; i++) {
    for (int j = 0; j < L; j++) {
      cin >> B[i][j];
    }
  }

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < L; j++) {
      for (int k = 0; k < M; k++) {
        C[i][j] += A[i][k] * B[k][j];
      }
      if (j) cout << SP;
      cout << C[i][j];
    }
    cout << BR;
  }

  return 0;
}


Measured memory_bytes: 3232
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int gi(){
    int x=0,w=1;char ch=getchar();
    while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if (ch=='-') w=0,ch=getchar();
    while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return w?x:-x;
}
const int N = 2e5+5;
const int mod = 1e9+7;
int n,a[N],cnt[N],S=1,z[N],st[N],D[N],ID[N],c1[N],c2[N];
int fastpow(int a,int b){
    int res=1;
    while (b) {if (b&1) res=1ll*res*a%mod;a=1ll*a*a%mod;b>>=1;}
    return res;
}
void mdf(int k,int v){while(k<=n)c1[k]=(c1[k]+v)%mod,++c2[k],k+=k&-k;}
int qry1(int k){int s=0;while(k)s=(s+c1[k])%mod,k^=k&-k;return s;}
int qry2(int k){int s=0;while(k)s+=c2[k],k^=k&-k;return s;}
int main(){
    n=gi();
    for (int i=1;i<=n;++i) ++cnt[a[i]=gi()];
    for (int i=n;i>=1;--i) cnt[i]+=cnt[i+1];
    for (int i=1;i<=n;++i){
        cnt[i]-=n-i;
        if (cnt[i]<=0) return puts("0"),0;
        S=1ll*S*cnt[i]%mod;
    }
    st[0]=D[0]=1;
    for (int i=1;i<=n;++i){
        int x=1ll*(cnt[i]-1)*fastpow(cnt[i],mod-2)%mod;
        if (!x) st[z[i]=z[i-1]+1]=i,D[i]=D[i-1];
        else z[i]=z[i-1],D[i]=1ll*D[i-1]*x%mod;
        ID[i]=fastpow(D[i],mod-2);
    }
    int inv2=(mod+1)>>1,ans=0;
    for (int i=1;i<=n;++i){
        ans=(ans+1ll*(qry1(a[i])-qry1(st[z[a[i]]]-1)+mod)*D[a[i]]%mod*S%mod*inv2)%mod;
        mdf(a[i],ID[a[i]]);
    }
    memset(c1,0,sizeof(c1)),memset(c2,0,sizeof(c2));
    for (int i=n;i;--i){
        ans=(ans-1ll*(qry1(a[i]-1)-qry1(st[z[a[i]]]-1)+mod)*D[a[i]]%mod*S%mod*inv2%mod+mod)%mod;
        ans=(ans+1ll*qry2(a[i]-1)*S)%mod;
        mdf(a[i],ID[a[i]]);
    }
    printf("%d\n",ans);
    return 0;
}

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

int main(){
long long int before=0,now,i,j,n,ret=0;
cin >> n;
for(i=0;i<n;i++){
cin >> now;
if(before==1 && now>0){ret++;now--;}
before = now%2;
ret+=now/2;
}
cout << ret << endl;
return 0;
}

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

#define fast_cin() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX 1000000
#define ll long long
#define db double
#define pb push_back
#define For(i,s,e) for (ll i=(s); i<(e); i++)
#define Debug_array(a,n) for (ll i=(0); i<(n); i++) cout<<a[i]<<" "
#define Foe(i,s,e) for (ll i=(s); i<=(e); i++)
#define Fod(i,s,e) for (ll i=(s)-1; i>=(e); i--)
#define str string
#define vl vector<ll>
#define vs vector<string>

#define mapll map<ll,ll>
#define mapss map<string,string>
#define mapsl map<string,ll>
#define mapls map<ll,string>

#define pll pair<ll,ll>
#define pss pair<string,string>
#define psl pair<ll,string>
#define pls pair<string,ll>

#define minheap priority_queue<ll>
#define maxheap priority_queue<ll,vector<ll> ,greater<ll>>

#define fi first
#define se second
#define endl "\n"
#define mp make_pair
#define big_prime 15486277
#define bigger_prime 179424697
#define biggest_prime 32416188691
const ll mod=1e9 + 7;


ll takemod(ll a) {
    return ((a%mod)+mod)%mod;
}

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

ll fast_exp(ll base, ll expo) {
    ll res=1;
    while(expo>0) {
        if(expo&1) res=(res*base)%mod;
        base=(base*base)%mod;
        expo>>=1;}
    return res;
}

ll modinv(ll a) {
    return takemod(fast_exp(takemod(a), mod-2));
}



signed main() 
{
    fast_cin();
    str s1;
    cin>>s1;
    str s2="keyence";
    ll index1=s2.length()-1;
    Fod(i,s1.length(),0)
    {
        //cout<<s1[i]<<s2[index1];
        if(s1[i]==s2[index1])
            index1-=1;
        else
            break;
        if(index1==-1)
            break;
    }
    ll index2=0;
    For(i,0,s1.length())
    {
        if(s1[i]==s2[index2])
            index2+=1;
        else
            break;
        if(index2==s2.length())
            break;
    } 
    //cout<<index1<<index2<<endl;
    if(index1<index2)
    {
        cout<<"YES"<<endl;
    }
    else
        cout<<"NO"<<endl;
}

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

const ll INF=1e18;

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n;
	cin>>n;
	vector<ll> a(n),pf(n);
	for(int i=0;i<n;++i){
		cin>>a[i];
		pf[i]=a[i];
		if(i) pf[i]+=pf[i-1];
	}
	vector<int> f(n),g(n);
	ll sum=a[0];
	for(int i=1,j=0;i<n;++i){
		ll prevv=abs(2*sum-pf[i]);
		while(j+1<i&&abs(2*(sum+a[j+1])-pf[i])<=prevv) sum+=a[++j],prevv=abs(2*sum-pf[i]);
		f[i]=j;
	}
	sum=a[n-1];
	for(int i=n-2,j=n-1;i>0;--i){
		ll prevv=abs(2*sum-pf[n-1]+pf[i-1]);
		while(j-1>i&&abs(2*(sum+a[j-1])-pf[n-1]+pf[i-1])<=prevv) sum+=a[--j],prevv=abs(2*sum-pf[n-1]+pf[i-1]);
		g[i]=j;
	}
	ll res=INF;
	for(int i=1;i<n-2;++i){
		ll P=pf[f[i]];
		ll Q=pf[i]-P;
		ll S=pf[n-1]-pf[g[i+1]-1];
		ll R=pf[n-1]-P-Q-S;
		res=min(res,abs(min({P,Q,S,R})-max({P,Q,S,R})));
	}
	cout<<res<<'\n';
}




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

int a,b,c;
int number = 0;

int main() {
  cin >> a >> b >> c;
  for (int x = a; x <= b ; x++) {
    if (c % x == 0) {
      ++number;
    }
  }
  cout << number << endl;
}

Measured memory_bytes: 3100
#include <iostream>
#include <vector>
#include <string>

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

using namespace std;

int main(){
    string station;
    cin >> station;
    //string company = station[0];
    string out = "No";
    for (int i = 1; i < 3; ++i)
    {
        if(station[i] != station[0])
            out = "Yes";
    }
    cout << out << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <climits>
#include <vector>
#include <utility>
#include <functional>
#include <map>
#include <string>
#include <set>
#include <math.h>

using namespace std;

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

  int dist[5];
  for (int i = 0; i < 5; i++) {
    cin >> dist[i];
  }

  int k;
  cin >> k;

  bool isConnection = true;
  for (int i = 0; i < 5; i++) {
    for (int j = i + 1; j < 5; j++) {
      if ((dist[j] - dist[i]) > k) {
        isConnection = false;
        break;
      }
    }
  }

  if (isConnection) {
    cout << "Yay!" << endl;
  }
  else {
    cout << ":(" << endl;
  }
}

Measured memory_bytes: 256