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

#define li          long long int
#define rep(i,to)   for(li i=0;i<((li)(to));i++)
#define repp(i,start,to)    for(li i=(li)(start);i<((li)(to));i++)
#define pb          push_back
#define sz(v)       ((li)(v).size())
#define bgn(v)      ((v).begin())
#define eend(v)     ((v).end())
#define allof(v)    (v).begin(), (v).end()
#define dodp(v,n)       memset(v,(li)n,sizeof(v))
#define bit(n)      (1ll<<(li)(n))
#define mp(a,b)     make_pair(a,b)
#define rin rep(i,n)
#define rjm rep(j,m)


#define DBGP 1


#define idp if(DBGP)
#define F first
#define S second
#define p2(a,b)     idp cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)       idp cout<<a<<"\t"<<b<<"\t"<<c<<endl
#define p4(a,b,c,d)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<endl
#define p5(a,b,c,d,e)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<endl
#define p6(a,b,c,d,e,f)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<endl
#define p7(a,b,c,d,e,f,g)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<endl
#define p8(a,b,c,d,e,f,g,h)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<endl
#define p9(a,b,c,d,e,f,g,h,i)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<endl
#define p10(a,b,c,d,e,f,g,h,i,j)        idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<"\t"<<j<<endl
#define foreach(it,v)   for(__typeof((v).begin()) it=(v).begin(); it!=(v).end(); ++it)
#define p2p(x)      idp p2((x).F, (x).S)
#define dump(x,n)   idp{rep(i,n){cout<<x[i]<<" ";}puts("");}
#define dump2(x,n)  idp{rep(i,n){cout<<"["<<x[i].F<<" , "<<x[i].S<<"] ";}puts("");}
#define dumpi(x)    idp{foreach(it, x){cout<<(*it)<<" ";}puts("");}
#define dumpi2(x)   idp{foreach(it, x){cout<<"["<<(it)->F<<" , "<<(it)->S<<"] ";}puts("");}

#define read2d(a,w,h)   rep(i,h)rep(j,w)cin>>a[i][j]
#define dump2d(a,w,h)   rep(i,h){rep(j,w)cout<<a[i][j]<<" ";puts("");}


#define EPS 1e-10
#define ETOL 1e-8
#define MOD 100000009

li n;
li a[100100];
li m, v, p;

inline bool check(li pos) {
    pos = upper_bound(a, a + n, a[pos]) - a - 1;
    if (pos >= n - p) {
        return true;
    }
    if (a[pos] + m < a[n - p]) {
        return false;
    }
    li cnt = 0;
    rep(i, pos + 1) {
        cnt += m;
    }
    rep(i, p - 1) {
        cnt += m;
    }
    repp(i, pos + 1, n - p + 1) {
        cnt += a[pos] + m - a[i];
    }
    return cnt >= m * v;
}

int main() {
    cin >> n >> m >> v >> p;
    rin{
        cin >> a[i];
    }
    sort(a, a + n);
    if (check(0)) {
        cout << n << endl;
        return 0;
    }
    //dump(a, n);
    li l = 0;
    li r = n - 1;
    while (l + 1 < r) {
        li med = (l + r) / 2;
        if (check(med)) {
            r = med;
        } else {
            l = med;
        }
    }
    cout << n - r << endl;

    return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){

   ll m,n;
   cin>>m>>n;
   ll w[m+1],l[m+1],dp[n+1]={0};
   for(int i=1;i<=m;i++)
   cin>>w[i]>>l[i];
   for(int i=1;i<=m;i++){
       for(int j=n;j>=w[i];j--){
           dp[j]=max(dp[j],l[i]+dp[j-w[i]]);
       }
	  /* for(int i=1;i<=8;i++)
		   cout<<dp[i]<<" ";
	   cout<<endl;
	   */
   }
   cout<<dp[n];
    return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int n,ans,s1,s2,s3;
char s[15];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s+1);
		int len=strlen(s+1);
		for(int i=1;i<len;i++)if(s[i]=='A'&&s[i+1]=='B')ans++;
		if(s[1]=='B'&&s[len]=='A')s3++;
		else if(s[1]=='B')s1++;
		else if(s[len]=='A')s2++;
	}
	if(s3)
	{
		ans+=s3-1;
		if(s1)s1--,ans++;
		if(s2)s2--,ans++;
	}
	cout<<ans+min(s1,s2)<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>

using namespace std;

int main() {
	char str[5];
	cin >> str;
	int fa = 0,fb=0,fc=0;
	for (int i = 0; i < 3; i++) {
		if (str[i] == 'a') {
			fa = 1;
		}
		if (str[i] == 'b') {
			fb = 1;
		}
		if (str[i] == 'c') {
			fc = 1;
		}
	}
	if ((fa == 1) && (fb == 1) && (fc == 1)) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	
	return 0;
}

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

#define sz(x) ((int)x.size())

using namespace std;

const int MAXN = 2000 + 23;








string s;
int k;

int main() {
    cin >> s >> k;
    for (int i = 0; i < sz(s) - 1; i++) {
        if (s[i] == 'a')
            continue;
        if ('z' - s[i] < k)
            k = k - 'z' + s[i] - 1, s[i] = 'a';
    }
    k %= 26;
    while (k--) {
        s.back()++;
        if (s.back() == 'z' + 1)
            s.back() = 'a';
    }
    cout << s;
    return 0;
}

Measured memory_bytes: 640
import math
n,m = map(int,input().split())

x = 10**9+7

ans = 0
if n == m:
    ans += math.factorial(n) * math.factorial(m) * 2
    print(ans % x)
    exit()
elif n >= m and n -m == 1:
    ans += math.factorial(n) * math.factorial(m)
    print(ans % x)
    exit()
elif m >= n and m -n== 1:
    ans += math.factorial(n) * math.factorial(m)
    print(ans % x)
    exit()
else:
    print(ans % x)

Measured memory_bytes: 10980
#include<bits/stdc++.h>
#define     ll          long long
#define     MOD         10e9+7
#define     pb          push_back
#define     vll         vector<long long>
#define     vi          vector<int>
#define     vl          vector<long>
#define     pii         pair<int, int>
#define     pll         pair<ll,ll>
#define     mp          make_pair
#define     all(a)      (a).begin(),(a).end()
#define     rep(i,a,b)  for(int i=a;i<b;i++)
#define     MAX         100002 
#define     ios          ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;


int main() {
    
    ios
    ll x1=1,x2=2,x3=3,x4=4,x5=5;
    cin >> x1 >> x2 >> x3 >> x4 >> x5;
    if(x1==0)cout <<"1\n";
    else if(x2==0)cout <<"2\n";
    else if(x3==0)cout <<"3\n";
    else if(x4==0)cout <<"4\n";
    else cout <<"5\n";


    return 0;
}



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

int main(){
  string s,t;
  cin >> s;
  cin >> t;
  int ans = 0;
  for(int i=0; i < s.size(); i++){
    if(s.at(i) != t.at(i)){
      ans++;
    }
  }
  cout << ans << endl;
}

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

int main(){
	int n;
	cin>>n;
	int temp;
	temp=0;
	for(int i=1;i<=9;i++){
		if(n%i==0 and n/i<10){
			temp=1;
		}
	}
	
	if(temp==0){
		cout<<"No"<<endl;
	}
	else if(temp==1){
		cout<<"Yes"<<endl;
	}
}

Measured memory_bytes: 256
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    s = list(map(int, input().split()))
    T = sum(s)
    ans = 100000
    for i in range(4):
        for j in range(i+1,4):
            ans = min(abs(2*(s[i]+s[j])-T), ans)
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()



Measured memory_bytes: 6068
#include <bits/stdc++.h>
#define ll long long
#define Nmax 2004
using namespace std;

int n,k,nrf[Nmax],DP[Nmax][Nmax],dif[Nmax][Nmax],a,b;
int ans = 1e9;
vector<int> v[Nmax];

void dfs(int nod, int ant){
    nrf[nod]++;
    for (int i=0;i<=k;i++) DP[nod][i] = 0;
    for (auto it : v[nod]){
        if (it == ant) continue;
        dfs(it, nod);
        nrf[nod] += nrf[it];
        for (int i=0;i<k;i++){
            DP[nod][i+1] += DP[it][i];
            if (i+i+1 > k){
                dif[nod][i+1] = min(dif[nod][i+1], -DP[it][k-i-1] + DP[it][i]);
            }
        }
    }
    DP[nod][0] = nrf[nod];
    for (int i=1;i<=k;i++){
        if (i+i-1<=k) continue;
        DP[nod][i] = DP[nod][k-i+1] + dif[nod][i];
    }
    if (nrf[nod]==1) DP[nod][1] = 0;
    for (int i=1;i<=k;i++) DP[nod][i] = min(DP[nod][i], DP[nod][i-1]);
    ans = min(ans, DP[nod][k] + n - nrf[nod]);
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> k;
    k++;
    memset(DP,0x3f,sizeof(DP));
    memset(dif,0x3f,sizeof(dif));
    for (int i=2;i<=n;i++){
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs(1,-1);

//    int ans = 1e9;
//    for (int i=0;i<=k;i++) ans = min(ans, DP[1][i]);
    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 31872
w,h,n = map(int,input().split())
xya = [list(map(int,input().split())) for _ in range(n)]
lst = [[0], [w], [0], [h]]

for i in range(len(xya)):
    if 1<=xya[i][2]<=2:
        for j in range(1,3):
            if xya[i][2]==j:
                lst[j-1].append(xya[i][0])
    else:
        for j in range(3,5):
            if xya[i][2]==j:
                lst[j-1].append(xya[i][1])

if min(lst[1])>=max(lst[0]):
    bla_width = w-min(lst[1])+max(lst[0])
else:
    bla_width = w

if min(lst[3])>=max(lst[2]):
    bla_height = h-min(lst[3])+max(lst[2])
else:
    bla_height = h

whi_area = (w-bla_width)*(h-bla_height)
print(whi_area)

Measured memory_bytes: 3064
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#define ll long long
using namespace std;
priority_queue<ll> qu;
vector<vector<ll>> vt;
vector<pair<ll,ll>> vt1;
ll p[100100];
ll check[100100];
pair<ll, ll> gap[100100];
ll n, m;
ll sz[100100];
ll find(ll u)
{
	if (p[u] == u)return u;
	return p[u] = find(p[u]);
}
void merge(ll u, ll v)
{
	u = find(u); v = find(v);
	p[u] = v;
	sz[v] += sz[u];
	sz[u] = 0;
}
int main()
{
	ll n, m;
	scanf("%lld %lld", &n, &m);
	for (int i = 0; i < n; i++)
	{
		sz[i] = 1;
		p[i] = i;
		gap[i].second = i;
		scanf("%lld", &gap[i].first);
	}
	vt.resize(n + 1);
	for (int i = 0; i < m; i++)
	{
		ll q, w;
		scanf("%lld %lld", &q, &w);
		merge(q, w);
	}
	for (int i = 0; i < n; i++)
	{
		vt[find(i)].push_back(gap[i].first);
	}
	for (int i = 0; i < n; i++)
	{
		sort(vt[i].begin(), vt[i].end());
	}
	for (int i = 0; i < n; i++)
	{
		if (sz[find(i)]) {
			if (check[find(i)])continue;
			check[find(i)] = 1;
			vt1.push_back({ sz[find(i)],find(i) });
		}
	}
	sort(vt1.begin(), vt1.end());
	reverse(vt1.begin(), vt1.end());
	for (int i = 0; i < vt[vt1[0].second].size(); i++)
	{
		qu.push(-vt[vt1[0].second][i]);
	}
	ll sum = 0;
	for (int i = 1; i < vt1.size(); i++)
	{
		if (qu.size() == 0)
		{
			puts("Impossible");
			return 0;
		}
		sum += (-qu.top() + vt[vt1[i].second][0]);
		qu.pop();
		for (int y = 1; y < vt[vt1[i].second].size(); y++)
		{
			qu.push(-vt[vt1[i].second][y]);
		}
	}
	printf("%lld\n", sum);
}

Measured memory_bytes: 11768
N, M = [int(_) for _ in input().split()]
LR = [[int(_) for _ in input().split()] for i in range(M)]

lm = 0
rm = N

for l, r in LR:
    lm = max(lm, l)
    rm = min(rm, r)

result = max(rm - lm + 1, 0)

print(result)


Measured memory_bytes: 21156
n, k = gets.chomp.split(' ').map(&:to_i)
ps = gets.chomp.split(' ').map(&:to_i)

# 期待値の累積和
a = [0]
1.upto(n) do |i|
  num = ps[i-1]
#   tmp = Rational([*1..num].inject(:+), num)
  tmp = Rational(num+1, 2)
  a << tmp + a[i-1] 
end

ans = 0
0.upto(a.size-1) do |i|
  tmp = a[i] - a[i-k]
  ans = tmp if tmp > ans
end

puts ans.to_f

Measured memory_bytes: 35204
#include<stdio.h>

int main(void){
	int N,i,max=0,sum=0;
	scanf("%d",&N);
	int L[N];
	for(i=0;i<N;i++) scanf("%d",&L[i]);
	for(i=0;i<N;i++){
		if(L[i]>max) max=L[i];
	}
	for(i=0;i<N;i++) sum+=L[i];
	if(sum>2*max) printf("Yes");
	else printf("No");
}

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

using namespace std;
using ll = long long;

template
<typename T>
T gcd(T a, T b) {
    if(a % b == 0) return b;
    if(a < b) gcd(b, a);
    return gcd(b, a % b);
}

int main() {
    ll N, K;
    cin >> N >> K;
    cout << min(N % K, K - (N % K)) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define int long long
#define float long double
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define endl '\n'
#define pii pair<int, int>
#define min3(a,b,c) min(a, min(b, c))
#define max3(a,b,c) max(a, max(b, c))
#define all(x) x.begin(), x.end()
#define fill(a,b) memset(a, b, sizeof(a))
#define sz(x) (int)x.size()
#define sp(x) setprecision(x)
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define inf 10000000000000005LL

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

    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int n,k; cin>>n>>k;
    int p[n],c[n],ans=-inf;
    for(int i=0;i<n;i++){
        cin>>p[i];
        p[i]--;
    }
    for(int i=0;i<n;i++) cin>>c[i];
    for(int i=0;i<n;i++){
        vector<int> v;
        int j=i,ans1=-inf,a=-inf,b=-inf;
        while(p[j]!=i){
            j=p[j];
            v.pb(c[j]);
        }
        v.pb(c[i]);
        for(int l=1;l<sz(v);l++) v[l]+=v[l-1];
        // for(int x : v) cout<<x<<" "; cout<<endl;
        for(int l=0;l<sz(v);l++){
            if(l<k%sz(v)) a=max(a,v[l]);
            b=max(b,v[l]);
        }
        // cout<<a<<" "<<b<<endl;
        ans1=a;
        if(k>=sz(v)) ans1=max3(ans1,a+v.back()*(k/sz(v)),b);
        if(k>=2*sz(v)) ans1=max(ans1,v.back()*((k/sz(v))-1)+b);
        ans=max(ans,ans1);
    }
    cout<<ans<<endl;

}

Measured memory_bytes: 3812
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;
using ll = long long;

int main() {

	std::cin.tie(nullptr); std::ios::sync_with_stdio(false);

	int N; cin >> N;

	int ans = INT_MIN;//答え

	int max_num = INT_MIN;

	for (int i = 1; i <= N; i++) {

		int break_num = 0;

		int tmp = i;

		while (tmp % 2 == 0) {
			tmp /= 2;
			break_num++;
		}

		if (break_num > max_num) {
			max_num = break_num;
			ans = i;
		}

	}

	cout << ans;



	return 0;

}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    S=[0]*(n+1)
    for i in range(n): S[i+1]=S[i]+A[i]
    dp=[[INF]*(n+1) for _ in range(n+1)]

    def dfs(L,R):
        if(R-L==1): return 0
        if(dp[L][R]!=INF): return dp[L][R]
        res=INF
        for h in range(L+1,R):
            res=min(res,dfs(L,h)+dfs(h,R)+S[R]-S[L])
        dp[L][R]=res
        return res

    print(dfs(0,n))
resolve()

Measured memory_bytes: 48476
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pii pair<ll, ll>
#define SZ(x) ((int)(x).size())
// #define endl "\n"
#define vvi vector<vector<int> >
#define vvl vector<vector<long long> >
ll mod = 1e9 + 7;
//const double pi = acos(-1.0);
/*
ll kmp(string x)
{
    ll n= x.length();
    //cout<<x<<endl;
    vector<ll> lcp(x.length(), 0);
    for(ll i=1;i<n;i++)
    {
        ll j=lcp[i-1];
        while(j>0 && x[j]!=x[i])
            j=lcp[j-1];
        if(x[i]==x[j])
            j++;
        lcp[i]=j;
    }
    return lcp[n-1];
}

int N = 1000002;
int ar[100002];
void sieve()
{
    for(int i=1;i<=N;i++)
        ar[i] = 1;
    ar[0] = 0;
    for(int i=2;i*i<=N;i++)
    {
        if(ar[i] && i*i<=N)
        {
            for(int j = i*i; j<=N;j+=i)
                ar[j] = 0;
        }
    }
}

ll modex(ll a,ll b){
    if(b<=0){
        return 1;
    }
    if(b%2==0)
    {
        ll x = modex(a, b/2);
        return ((x*x)%mod);
    }
    else
        return ((a%mod * modex(a, b-1))%mod);
}

ll c[1010][1010];

ll combina(ll i, ll j){
        for (int i=0;i<=1005;i++)
        for (int j=0;j<=i;j++)
        {
            if (j==i||j==0)
                c[i][j]=1;
            else
            c[i][j]=c[i-1][j-1]+c[i-1][j];
            c[i][j]%=mod;
        }
        return c[i][j];
}
void find_fac(int x){
    vector<ll> di;
    for(ll i = 2; i*i <= x; i++)
    {
        if(x%i==0){
            di.push_back(i);
            while(x%i==0)
                x/=i;
        }
    }
    if(x > 1)
        di.push_back(x);
}
*/
ll n, k;
vector<ll> a;
ll fun(ll m){
    ll c = 0;
    for(ll i=0;i<n;i++){
        if(a[i]<=m)
            continue;
        ll x = (a[i]+m-1)/m;
        c += (x-1);
    }
    return c;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cout<<fixed;
    cout.precision(12);
    cin>>n>>k;
    a.resize(n);
    for(ll i=0;i<n;i++)
        cin>>a[i];
    ll l=1, r = 1e9, an=1e9;
    while(l<=r){
        ll m = (l+r)/2;
        if(fun(m)>k)
            l = m+1;
        else{
            an = min(an, m);
            r = m-1;
        }
    }
    cout<<an<<endl;
    return 0;
}


Measured memory_bytes: 4760
import sys
import fractions

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

N = ir()
start = ir()
next = 0
for n in range(1, N):
    next = ir()
    start = lcm(start, next)

print(start)


Measured memory_bytes: 5076
// AtCoder Beginner Contest 070
// C - Multiple Clocks

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;


int N;

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

int main() {

    ll t;
    ll ans;

    cin >> N;
    ans = 1;
    for (int i = 0; i < N; i++) {
        cin >> t;
        ans = t / gcd(t, ans) * ans;
    }

    cout << ans << endl;

    return 0;

}





Measured memory_bytes: 256
s = input()
S = []
for c in s:
    S.append(int(c))
count = 0
l = len(S)
for i in range(0,l,2):
    if S[i] == 0:
        count += 1 
for i in range(1,l,2):
    if S[i] == 1:
        count += 1

print(min(count,l-count))
        

Measured memory_bytes: 3956
#include<iostream>
 #include<stdio.h>
 #include<string>
 #include<math.h>
 #include<iomanip>
 #include<algorithm>
 #include<string.h>
 #include<cctype>
 #include<map>
 #include<set>
 #include<vector>
 #include<sstream>
 #include<stack>
 #include<queue>
 
 using namespace std;
 
 int month[12]={31,29,31,30,31,30,31,31,30,31,30,31};
  
 int main()
 {
   int m,d;
   int duration;
   while(cin>>m>>d)
   {
     duration=0;
     if(m==0&&d==0) break;
     else
     {
       if(m==1) duration=d-1;
       else 
       {
         for(int i=0;i<m-1;i++) duration+=month[i];
         duration+=(d-1);     
       }    
       if(duration%7==0) cout<<"Thursday"<<endl;
       else if(duration%7==1) cout<<"Friday"<<endl;
       else if(duration%7==2) cout<<"Saturday"<<endl;
       else if(duration%7==3) cout<<"Sunday"<<endl;
       else if(duration%7==4) cout<<"Monday"<<endl;
       else if(duration%7==5) cout<<"Tuesday"<<endl;
       else cout<<"Wednesday"<<endl;
     }                
   }
   //while(1);     
   return 0;  
 }
 

Measured memory_bytes: 3084
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = s; i < (int)(n); i++)
#define chmax(a, b) a = max(a, b)
using namespace std;

int		main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	char ci;
	int N, M, si;
	string num = "";
	cin >> N >> M;
	rep(i, N) num += "x";
	rep(i, M) {
		cin >> si >> ci;
		if (num.at(si - 1) != ci && num.at(si - 1) != 'x') {
			cout << "-1\n";
			return (0);
		}
		if (si == 1 && ci == '0' && N != 1) {
			cout << "-1\n";
			return (0);
		}
		num.at(si - 1) = ci;
	}
	if (num.at(0) == 'x' && N != 1)
		num.at(0) = '1';
	rep(i, N) {
		if (num.at(i) == 'x')
			num.at(i) = '0';
	}
	cout << num << "\n";
}


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

#define REP(i, n) for(int64_t i = 0; i < n; i++)
#define REPR(i, n) for(int64_t i = n; i >= 0; i--)
#define FOR(i, m, n) for(int64_t i = m; i < n; i++)
#define FORR(i, m, n) for(int64_t i = m; i >= n; i--)
#define ALL(v) v.begin(), v.end()
typedef long long ll;
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    fill( (T*)array, (T*)(array+N), val );
}
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;}
const ll INF= 1ll << 60;
const ll MOD = 1000000007;
double EPS = 1e-10;
//----------------------------------------------------------

int k, a, b;

int main(){
    cin >> k>>a>>b;
    int n=1;
    while(k*n<=b)
    {
        if(k*n>=a)
        {
            cout << "OK" << endl;
            return 0;
        }
        n++;
    }
    cout << "NG"<<endl;
    return 0;
}

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

using ll = long long;
using P = pair<int, int>;

const int INF = 1e9;
const int MOD = 1e9 + 7;

// 4近傍、8近傍
int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

int main() {
  // 入力
  double t, x;
  cin >> t >> x;

  cout << t / x << endl;
  return 0;
}



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

#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define MIN(a) *min_element(all(a))
#define MAX(a) *max_element(all(a))
#define SUM(a) accumulate(all(a), 0LL)
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define RREP(i, n) for(int (i)=(n)-1; (i)>=0; (i)--)
#define FOR(i, m, n) for(int (i)=(m); (i)<(n); i++)
#define FORR(i, m, n) for(int (i)=(n)-1; (i)>=(m); i--)
#define debug(x) cerr << #x << " = " << x << endl
//#define int long long

typedef long long ll;
//ll const MOD = 998244353;
ll const MOD = 1e9+7;
int const inf = 1e9;
ll const INF = 1e18;

inline void ios_(){cin.tie(0); ios::sync_with_stdio(false);}
template<typename T> int size(const T& a){return (int)a.size();}
template<typename T> T Div(T a, T b){return (a + b - 1) / b;}
template<typename T> bool chmin(T& a, const T& b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, const T& b){if(a < b){a = b; return true;} return false;}



signed main(){
    string s, t;
    cin >> s >> t;
    cout << (s + t.back() == t ? "Yes" : "No") << endl;
    return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#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 sp(n) cout << fixed << setprecision(n)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long ll;
using namespace std;
int main(void){
    ll q,h,s,d,n;cin>>q>>h>>s>>d>>n;
    ll b=min(s,min(q*4,h*2));
    if(b*2>d){
        ll res=n/2*d+(n%2)*b;
        cout<<res<<endl;
    }else{
        cout<<n*b<<endl;
    }
}

Measured memory_bytes: 256
import qualified Data.ByteString.Char8 as C
import Data.Maybe ( fromJust )
import Data.Char ( digitToInt )

readInt :: IO Int
readInt = fst . fromJust . C.readInt <$> C.getLine

main :: IO ()
main = do
  n <- readInt
  putStrLn $ if isHarshad n then "Yes" else "No"

isHarshad
  :: Int -> Bool
isHarshad x 
  = let fx = sumDigits x  
    in 0 == x `rem` fx

sumDigits, sumDigits'
  :: Int -> Int
sumDigits = sum . map digitToInt . show

sumDigits' = sum . int2lst
int2lst n
  | q == 0 = [r]
  | otherwise = r : int2lst q
  where
    (q,r) = divMod n 10

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

int memo[100000][3];
// {0,1,2}={r,s,p}
int main(){
	int n,k,r,s,p;	cin>>n>>k>>r>>s>>p;
	string t;	cin>>t;

	for(int i=0; i+k<n; i++){
		if(t[i]==t[i+k]){
			t[i+k]='_';
		}
	}
	//cout<<t<<endl;
	int ans=0;
	for(int i=0;i<n;i++){
		if(t[i]=='r')ans+=p;
		else if(t[i]=='s')ans+=r;
		else if(t[i]=='p')ans+=s;
	}

	cout<<ans<<endl;

	return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define int long long // at least int64 > 9*10^18
#define ENDL '\n'
#define rep(i,n) for(int i = 0; i < (n); i++)
#define print(i) std::cout << (i) << '\n'
#define all(v) (v).begin(), (v).end()

using namespace std;

signed main (){
  int N , i ;
  cin>>N>>i;
  cout<<N-i+1<<endl;
}

Measured memory_bytes: 256
n=int(input())
d={}
for i in range(n):
     s,p=input().split()
     try:
          d[s][int(p)]=i+1
     except:
          d[s]={int(p):i+1}
k=sorted(d.keys())
for x in k:
     d_=d[x]
     k_=sorted(d_.keys())[::-1]
     for y in k_:
          print(d_[y])

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

int main()
{
	int n;
	cin >> n;
	vector<int> cls(n), vls(n);
	for (auto& v : vls)cin >> v;
	for (auto& c : cls)cin >> c;

	int i = 0;
	for (int j = 0; j < n; ++j)i += 1 << j;
	int maxNum = 0, curNum = 0;

	for (; i >= 0; --i) {
		curNum = 0;
		for (int j = 0; j < n; ++j) {
			if (i & (1 << j))
				curNum += vls[j] - cls[j];
		}
		maxNum = max(maxNum, curNum);
	}

	cout << maxNum << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef long double ld;
typedef complex<ld> Point;
const ll INF = mod * mod;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
const ld eps = 1e-6;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;

char mp[19][15];

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

int ans = mod;
void dfs(int x, int y, int k) {
	if (x >= 19||(x==18&&0<=y&&y<15)) {
		ans = min(ans, k);
		return;
	}
	if (x < 0 || y < 0 || y >= 15)return;
	rep(j, 8) {
		int nx = x + dx[j], ny = y + dy[j];
		if (nx < 0 || ny < 0 || nx >= 19 || ny >= 15)continue;
		if (mp[nx][ny] == 'X') {
			vector<P> memo;
			while (true) {
				mp[nx][ny] = '.';
				memo.push_back({ nx,ny });
				nx += dx[j]; ny += dy[j];
				if (nx < 0 || ny < 0 || nx >= 19|| ny >= 15)break;
				if (mp[nx][ny] != 'X')break;
			}
			dfs(nx, ny, k + 1);
			rep(i, memo.size()) {
				mp[memo[i].first][memo[i].second] = 'X';
			}
		}
	}
}

void solve() {
	int sx, sy;
	rep(i, 19) {
		rep(j, 15) {
			cin >> mp[i][j];
			if (mp[i][j] == 'O') {
				sx = i, sy = j;
				mp[i][j] = '.';
			}
		}
	}
	dfs(sx, sy, 0);
	if (ans == mod)ans = -1;
	cout << ans << endl;
}

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


Measured memory_bytes: 3232
// AOL Q.0560
// YAMADA Terushige 2013.1.20.

#include<iostream>
#include<vector>

using namespace std;

//int J[1001][1001],O[1001][1001],I[1001][1001];
//大きい２次元配列はグローバル変数か，ローカルならstaticで静的に確保するか ，
//あるいはvector を使う。いずれも値は0で初期化されている。

int main(){

  int M,N,K;
  cin >> M >> N;
  cin >> K;
  M++;N++;K++;

  static int J[1001][1001],O[1001][1001],I[1001][1001];

  /*
  vector<vector<int> > J(M,vector<int>(N));
  vector<vector<int> > O(M,vector<int>(N));
  vector<vector<int> > I(M,vector<int>(N));
  */

  for(int i=1;i<M;i++){
    for(int j=1;j<N;j++){
      J[i][j]=J[i-1][j]+J[i][j-1]-J[i-1][j-1];
      O[i][j]=O[i-1][j]+O[i][j-1]-O[i-1][j-1];
      I[i][j]=I[i-1][j]+I[i][j-1]-I[i-1][j-1];
      char c;
      cin>>c;
      switch (c){
      case 'J':
	J[i][j]++;break;
      case 'O':
	O[i][j]++;break;
      default:
	I[i][j]++;break;
      }
    }
  }
  
  for(int k=1;k<K;k++){
    int a,b,c,d;
    int nj,no,ni;
    cin >> a >> b >> c >> d;
    a--;b--;
    nj=J[c][d]+J[a][b]-J[a][d]-J[c][b];
    no=O[c][d]+O[a][b]-O[a][d]-O[c][b];
    ni=I[c][d]+I[a][b]-I[a][d]-I[c][b];
    cout << nj << ' ' << no << ' ' << ni << endl;
  }
  return 0;
}


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

const int MOD = 1000000007;
const int MOD2 = 1000000009;
const int MAXN = 200005;
int n, k;
int p[MAXN];
int pw[MAXN];
int pw2[MAXN];
int p1[MAXN];
int p2[MAXN];
pair<int, int> tree[4*MAXN];
int len[4*MAXN];

void upd(int i, int l, int r, int x, bool add) {
	if (l > x || r < x) return;
	if (l == r) {
		if (add) {
			tree[i] = make_pair(x, x);
			len[i] = 1;
		} else {
			tree[i] = {0, 0};
			len[i] = 0;
		}
		return;
	}
	upd(i * 2 + 1, l, (l + r) / 2, x, add);
	upd(i * 2 + 2, (l + r) / 2 + 1, r, x, add);
	len[i] = len[i*2 + 1] + len[i*2 + 2];
	tree[i].first = (tree[i*2 + 1].first + (pw[len[i*2 + 1]] * 1ll * tree[i*2 + 2].first)) % MOD;
	tree[i].second = (tree[i*2 + 1].second + (pw2[len[i*2 + 1]] * 1ll * tree[i*2 + 2].second)) % MOD2;
}

set<pair<int, int> > perms;
void solve(int i) {
	if (i + k > n) return;
	long long ans2 = p2[n-1];
	long long ans1 = p1[n-1];
	ans1 -= p1[i+k-1];
	ans2 -= p2[i+k - 1];
	if (i) {
		ans1 += p1[i-1];
		ans2 += p2[i-1];
		upd(0, 1, n, p[i + k - 1], true);
		upd(0, 1, n, p[i-1], false);
	} else {
		for (int j = 0; j < k; j++) {
			upd(0, 1, n, p[j], true);
		}
	}
	while (ans1 < 0) ans1 += MOD;
	while (ans2 < 0) ans2 += MOD2;
	pair<int, int> res;
	res.first = (ans1 + tree[0].first * 1ll * pw[i]) % MOD;
	res.second = (ans2 + tree[0].second * 1ll * pw2[i]) % MOD2;
	perms.insert(res);
}
int main() {
	pw[0] = 1;
	pw2[0] = 1;
	for (int i = 1; i < MAXN; i++) {
		pw[i] = (MAXN * 1ll * pw[i-1]) % MOD;
		pw2[i] = (MAXN * 1ll * pw2[i-1]) % MOD2;
	}
	scanf("%d %d", &n, &k);
	for (int i = 0; i < n; i++) {
		scanf("%d", p + i);
		p[i]++;
		p1[i] = (p[i] * 1ll * pw[i] + p1[i-1]) % MOD;
		p2[i] = (p[i] * 1ll * pw2[i] + p2[i-1]) % MOD2;
	}
	for (int i = 0; i < n; i++) solve(i);
	printf("%d\n", perms.size());
}


Measured memory_bytes: 22912
//#include"cpp_kyopro.h"
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include<stdio.h>

using namespace std;

int main(void)
{
	int n; cin >> n;
	vector<int> b(n - 1),a;
	int ans = 0;
	for (int i = 0; i < n - 1; i++)cin >> b[i];
	for (int i = 1; i < n - 1; ++i)ans += min(b[i - 1], b[i]);
	cout << ans + b[0] + b[n - 2] << endl;
		// << accumulate(b.begin()+1, b.end()-1, b[0]);
	return 0;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ss second
#define ff first
#define all(x) x.begin(), x.end()
 
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
 
const int oo = 1e9 + 7;
const int mod = 1e9 + 7, maxn = (1 * 1e5) + 10;
const long double PI = acos(-1);


int main (){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll x, d, k, mul;
    cin >> x >> k >> d;
    mul = min(k, abs(x)/d);
    k -= mul;
    x = abs(x);
    x -= mul*d;

    if (k&1) x = abs(x - d);

    cout<< x << endl;
    return 0;
}

Measured memory_bytes: 3644
#include <iostream>
#include <cmath>

int main()
{
    int N;
    double T, A;
    std::cin >> N;
    std::cin >> T >> A;

    int ans;
    double X = 10000000.0;

    double H;
    for (int i = 0; i < N; i++) {
        std::cin >> H;
        double a = std::fabs(A - (T - H * 0.006));
        if (a < X) {
            X = a;
            ans = i+1;
        }
    }

    std::cout << ans << std::endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
char a[2001][2001];
int sum3[2001][2001],sum2[2001][2001],sum[2001][2001],sum1[2001][2001];
int n,m;
/*int check1(int x,int y)
{
	int i,ans=0;
	for(i=x-1;i>=1&&a[i][y]=='.';i--)
		ans++;
	for(i=y-1;i>=1&&a[x][i]=='.';i--)
		ans++;
	return ans;
}
int check(int x,int y)
{
	int i,ans=0;
	for(i=x+1;i<=n&&a[i][y]=='.';i++)
		ans++;
	for(i=y+1;i<=m&&a[x][i]=='.';i++)
		ans++;
	return ans+1;
}*/
int main()
{
	int i,j,maxx=0;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	{
		getchar();
		for(j=1;j<=m;j++)
			scanf("%c",&a[i][j]);
	}
	for(i=1;i<=n;i++)
	{
		if(a[i][m]=='.')
			sum[i][m]=1;
		for(j=m-1;j>=1;j--)
			sum[i][j]=(a[i][j]=='.'?sum[i][j+1]+1:0);
	}
	for(j=1;j<=m;j++)
	{
		if(a[n][j]=='.')
			sum1[n][j]=1;
		for(i=n-1;i>=1;i--)
			sum1[i][j]=(a[i][j]=='.'?sum1[i+1][j]+1:0);
	}
	for(i=1;i<=n;i++)
	{
		if(a[i][1]=='.')
			sum2[i][1]=1;
		for(j=2;j<=m;j++)
			sum2[i][j]=(a[i][j]=='.'?sum2[i][j-1]+1:0);
	}
	for(j=1;j<=m;j++)
	{
		if(a[1][j]=='.')
			sum3[1][j]=1;
		for(i=2;i<=n;i++)
			sum3[i][j]=(a[i][j]=='.'?sum3[i-1][j]+1:0);
	}
	/*for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
			printf("%d ",sum[i][j]);
		printf("\n");
	}*/
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			if(a[i][j]=='.')
				maxx=max(maxx,sum[i][j]+sum1[i][j]+sum2[i][j]+sum3[i][j]);
	printf("%d",maxx-3);
    return 0;
}

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


int main()
{
	ll n,ans=0;
	cin>>n;
	ans+=n-1;
	for(ll i=2;i<n;i++)
	{
		if(n%i==0)
			ans+=(n/i - 1);
		else
			ans+=(n/i);
	}
	cout<<ans<<endl;


}


Measured memory_bytes: 3620
#include<bits/stdc++.h>
#define mid (l+r>>1)
using namespace std;
long long n,q;
long long sum[800010];
long long add[800010];
void pushdown(long long k,long long l,long long r){
	add[k<<1]+=add[k];
	add[k<<1|1]+=add[k];
	sum[k<<1]+=add[k]*(mid-l+1);
	sum[k<<1|1]+=add[k]*(r-mid);
	add[k]=0;
}
void update(long long k,long long l,long long r,long long x,long long y,long long v){
	if(l>y||r<x){
		return;
	}
	if(l>=x&&r<=y){
		sum[k]+=v*(r-l+1);
		add[k]+=v;
		return;
	}
	pushdown(k,l,r);
	update(k<<1,l,mid,x,y,v);
	update(k<<1|1,mid+1,r,x,y,v);
	sum[k]=sum[k<<1]+sum[k<<1|1];
}
long long query(long long k,long long l,long long r,long long x,long long y){
	if(l>y||r<x){
		return 0;
	}
	pushdown(k,l,r);
	if(l>=x&&r<=y){
		return sum[k];
	}
	return query(k<<1,l,mid,x,y)+query(k<<1|1,mid+1,r,x,y);
}
long long ans;
int main(){
	cin>>n;
	for(long long i=1;i<=n;i++){
		long long u;
		cin>>u;
		ans+=u;
		update(1,1,100000,u,u,1);
	}
	cin>>q;
	while(q--){
		long long u,v;
		cin>>u>>v;
		long long num=query(1,1,100000,u,u);
		ans+=num*(v-u);
		update(1,1,100000,u,u,-num);
		update(1,1,100000,v,v,num);
		cout<<ans<<'\n';
	}
	return 0;
}

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

using namespace std;

int main()
{
    long long n;
    cin >> n;
    int res=0;
    map<long long,int> m;
    for(long long i=2;i*i<=n;i++)
    {
        while((n%i)==0)
        {
            m[i]++;
            n/=i;
        }
    }
    if(n>1) m[n]=1;
    for(pair<long long,int> to:m)
    {
        int a=to.second;
        for(int i=1;i<=a;i++)
        {
            a-=i;
            res++;
        }
    }
    cout << res;
    return 0;
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int maxn = 300 + 5;
const int mod = 1e9 + 7;
int dp[maxn][maxn][maxn];
void add(int & x , int y){
    x += y;
    if(x >= mod)x -= mod;
}
int n, m;
ii a[maxn];
vector<ii> adj[maxn];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w  ",stdout);
    }
    cin >> n >> m;
    for(int i = 1 ; i <= m ; ++i){
        int x , y , z;cin >> x >> y >> z;
        adj[y].pb(mp(x,z));
    }
    dp[1][0][0] = dp[0][1][0] = dp[0][0][1] = 1;
    int res = 0;
    for(int i = 0 ; i <= n ; ++i){
        for(int j = 0 ; j <= n ; ++j){
            for(int t = 0 ; t <= n ; ++t){
                if(dp[i][j][t] == 0)continue;
                int k = max({i,j,t});
                for(ii & c : adj[k]){
                    int cnt = 0;
                    cnt += (i >= c.first);
                    cnt += (j >= c.first);
                    cnt += (t >= c.first);
                    if(cnt != c.second)dp[i][j][t] = 0;
                }
                add(dp[k + 1][j][t] , dp[i][j][t]);
                add(dp[i][k + 1][t] , dp[i][j][t]);
                add(dp[i][j][k + 1] , dp[i][j][t]);
                if(k == n)add(res,dp[i][j][t]);
            }
        }
    }
    cout << res;
}


Measured memory_bytes: 110848
#include<iostream>
using namespace std;
int main(){
char c;
long n,m,a,b,d,e,f,i,j,k,p[20][20],x1,x2,y1,y2,q[20];
cin>>n>>m;
for(i=0;i<m;i++){
q[i]=-1;
for(j=0;j<n;j++)p[i][j]=-1;
}
for(i=0;i<m;i++){
cin>>a>>c>>b>>c>>d>>c>>e;
p[a-1][b-1]=d;
p[b-1][a-1]=e;
}
cin>>x1>>c>>x2>>c>>y1>>c>>y2;
q[x1-1]=0;
for(k=0;k<n;k++){
f=0;
for(i=0;i<n;i++){
if(q[i]<0){f=1;continue;}
for(j=0;j<n;j++){
if(p[i][j]<0)continue;
if(q[j]<0||q[j]>q[i]+p[i][j])q[j]=q[i]+p[i][j];
}
}
if(f==0)break;
}
y1-=(q[x2-1]+y2);
for(i=0;i<m;i++)q[i]=-1;
q[x2-1]=0;
for(k=0;k<n;k++){
f=0;
for(i=0;i<n;i++){
if(q[i]<0){f=1;continue;}
for(j=0;j<n;j++){
if(p[i][j]<0)continue;
if(q[j]<0||q[j]>q[i]+p[i][j])q[j]=q[i]+p[i][j];
}
}
if(f==0)break;
}
y1-=q[x1-1];
cout<<y1<<endl;
return 0;
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
//const double pi=acos(-1.0);
#define mod 1000000007
#define forn(i,k,n) for(ll i=k;i<n;i++)
#define fornr(i,k,k1) for(ll i=k;i>=k1;i--)
#define v(ll) vector<ll>
#define vl(a,n,ll,k) vector<ll> a(n,k)
#define vli(a,n) vector<ll> a(n)
#define init(a,n) vector<ll> a(n);forn(i,0,n)cin>>a[i]
#define vll(a,n,m,ll,k) vector<vector<ll>> a(n,vector<ll>(m,k))
#define mp(a,ll,ll1) map<ll,ll1> a
#define st(a,ll) set<ll> a
#define mpa make_pair
#define pr pair<ll,ll>
#define pb push_back
#define MAX 1000000
#define ed '\n'
#define fileTake ifstream cin("input.txt");ofstream cout("output.txt");
#define sortv(a) sort(a.begin(),a.end())
#define sorta(a,n) sort(a,a+n)
#define yeah "YES"
#define nil "NO"
#define All(x) x.begin(),x.end()
#define remDup(a) a.erase(unique(All(a)),a.end())
#define N 100
 
void swap(ll &x,ll &y) 
{ 
	x=x^y;
	y=x^y;
	x=x^y;
} 

template<typename T>
void print(T a){for(auto i=a.begin();i!=a.end();i++)cout<<*i<<" ";cout<<endl;}
bool isVowel(char c)
{
	if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u')return true;
	return false;
}

void sync(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}

int main(){
	sync();
	ll k;
	cin>>k;
	bool ck[k]={false};
	ll flag=1;
	ll num=0;
	ll ans=0;
	while(true)
	{
		ans++;
		num=(num*10+7)%k;
		if(num==0)break;
		if(ck[num])
		{
			flag=0;
			break;
		}
		ck[num]=true;
	}
	if(flag)cout<<ans<<endl;
	else cout<<-1<<endl;
}


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

int main() {
	string a;
	cin >> a;
	//cout << re(a);
	int len = a.size();
	//int i = 0, j = len - 1;
	int res=0;
	for (int i = 0, j = len - 1; i < len / 2; i++, j--) {
		if (a[i] != a[j]) res++;
	}

	cout << res << endl;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
A = list(map(int, input().split()))
sortA = sorted(A, reverse=True)
sumA = sum(A)
flag = True
for i in range(M):
    if sortA[i] < sumA / (4 * M):
        flag = False
        break
if flag:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 38256
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 6;
int a[maxn], cnt[maxn];

int main(){
    int n, k; scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) 
        scanf("%d", &a[i]), cnt[a[i]]++;
    sort(cnt + 1, cnt + 1 + n);
    int ans = 0, res = 0;
    for (int i = 1; i <= n; ++i)
        if(cnt[i]) res++;
    int cntt = res - k;
    for (int i = 1; i <= n; ++i){
        if(cntt <= 0) break;
        ans += cnt[i];
        if(cnt[i])cntt--;
    }
    cout << ans << endl; 
    return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 1000000;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

///////////////////////////

int N;

ll v(int i, int j) {
	if (i > j) { return v(j, i); }
	return N * i + j;
}





int main() {
	cin >> N;

	ll n[1100000]={};//入次数
	ll day[1100000];
	vector<ll> g[1100000];

	int a[1100][1100];

	repn(i, N) {
		repn(j, N - 1) {
			cin >> a[i][j];
		}
	}

	repn(i, N) {
		repn(j, N - 2) {
			g[v(i, a[i][j])].push_back(v(i, a[i][j + 1]));
			n[v(i, a[i][j + 1])]++;
		}
	}

	queue<ll> q;

	repn(i,N){
		for(int j=1; j<i; j++) {
			ll u = j * N + i;

			day[u] = INF;

			if (n[u] == 0) {
				q.push(u);
				day[u] = 1;
			}
		}
	}

	while (!q.empty()) {
		ll u = q.front();
		rep(i, g[u].size()) {
			ll w = g[u][i];
			n[w]--;
			if (n[w] == 0) {
				day[w] = day[u] + 1;
				q.push(w);
			}
		}

		q.pop();
	}

	ll ans = 0;

	repn(i, N) {
		for (int j = 1; j < i; j++) {
			ll u = j * N + i;
			
			ans = max(ans, day[u]);

		
		}
	}

	
	if (ans == INF) { cout << -1; }
	else {cout << ans;}

	system("PAUSE");
}


Measured memory_bytes: 63744
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <string>
#include <sstream>
#include <vector>
#include <list>
#include <map>
#include <stdlib.h>
#include <stdint.h>

using namespace std;

typedef long long	    ll;
typedef  intmax_t     intt;
typedef uintmax_t    uintt;
#define MAXX INTMAX_MAX

#define PI M_PI

//デバッグ、数値確認用
#define DBG(X) cout<< X <<endl

//繰り返し構文
#define REP(i, n)		for(intt i = 0;i < (n);i++)
#define FORL(i,m,a,n)	for(intt i = m;i <= (n);i+=a)	//CMDのfor/l
//#define FORL(i,m,a,n)	for(intt i = m;i <  (n);i+=a)	//CMDのfor/l
#define FORRL(i,m,a,n)	for(intt i = m;i >= (n);i+=a)
//#define FORRL(i,m,a,n)	for(intt i = m;i <  (n);i+=a)
#define ITEFOR(i,list)    for (auto i = list.begin();i != list.end();i++)

#define IN(a,n,b) ((a)<=(n)&&(n)<=(b))



int main()
{
    intt sn,tn;
    //uintt ;
    //double ;
    string s,t,u;
    //vector<> ;
    //map<,> ;

    cin >> s >> t >> sn >> tn >> u;

    if (s == u) {
        sn--;
    } else {
        tn--;
    }
    cout << sn << " " << tn << endl;

    return 0;
}


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

typedef long long ll;

vector<vector<ll>> graph(100);
vector<bool> visit(100,false);
vector<ll> d(100);
vector<ll> f(100);
ll tmp = 0;

void dfs(ll v)
{
    ll i;
    visit.at(v) = true;
    d.at(v) = ++tmp;
    for(i = 0;i < graph.at(v).size();++i){
        ll g = graph.at(v).at(i);
        if(visit.at(g)){
            continue;
        }
        dfs(g);
    }
    f.at(v) = ++tmp;
    return;
}

int main()
{
    ll i,j;
    ll n;
    cin >> n;
    for(i = 0;i < n;++i){
        ll u,k;
        cin >> u >> k;
        for(j = 0;j < k;++j){
            ll v;
            cin >> v;
            graph.at(u-1).push_back(v-1);
        }
    }
    for(i = 0;i < n;++i){
        if(!visit.at(i)){
            dfs(i);
        }
    }
    for(i = 0;i < n;++i){
        cout << i+1 << " " << d.at(i) << " " << f.at(i) << endl;
    }
    return 0;
}


Measured memory_bytes: 3124
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
long long mymin(long long x,long long y)
{
	if(x==-1)
		return y;
	return min(x,y);
}
long long x[202020];
long long sum[202020];
int h[202020];
int main()
{
	int n;
	long long xx;
	long long ans=-1,now=0;
	scanf("%d%lld",&n,&xx);
	sum[0]=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&x[i]);
		sum[i]=sum[i-1]+x[i];
	}
	h[1]=5;
	h[2]=5;
	for(int i=3;i<=n;i++)
		h[i]=h[i-1]+2;
	for(int i=1;i<=n;i++)
	{
		now=(long long)xx*(i+n);
		for(int j=n,cnt=1;j>=1;j-=i,cnt++)
		{
			now+=(sum[j]-sum[max(j-i,0)])*h[cnt];
			if(now>ans&&ans!=-1)
				break;
		}
		ans=mymin(ans,now);
	}
	printf("%lld",ans);
	return 0;
}

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

int main(){
  int x, a, b;
  cin >> x >> a >> b;
  
  if(a >= b) cout << "delicious" << endl;
  else if(a + x >= b) cout << "safe" << endl;
  else cout << "dangerous" << endl;
  return 0;
}

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

int main(){
  int n;
  cin >> n;
  vector<pair<int,int>>ba;
  for(int i = 0; i < n; i++){
    int a, b;
    cin >> a >> b;
    ba.push_back(make_pair(b,a));
  }
  sort(ba.begin(),ba.end());
  int sumai = 0;
  for(int i = 0; i < n; i++){
    sumai += ba.at(i).second;
    if(sumai > ba.at(i).first) {
      cout << "No" << endl;
      break;
    }
    else if(i == n-1) cout << "Yes" << endl;
  }
}

Measured memory_bytes: 2420
#if 0
????????£????????????1.5h
????????????????????¨????????§?????????????????§?°??????????????¨?????????????????????????????????????????¨?????????????
????????????????????????????????????????????????????????????????????????????????´??????(????????¨?????????????????¢??????)???

#endif

#include <utility>
#include <algorithm>
#include <iostream>
using namespace std;

int N,M;
pair<int,int> PD[10010];
int main(){
	while (cin>>N>>M && N!=0){ //N!=0??§?????????N=0,M=0??????????????????????????????????????????
		int d,p;
		int S=0; //????¨??????????
		for(int i=0; i<N; ++i){
			cin >> d >> p;
			PD[i]=make_pair(p,d);
		}
		sort(PD,PD+N);
		reverse(PD,PD+N); //PD.first??????????????±??????????????????
		for(int i=0; i<N; ++i)
			S+=PD[i].first*PD[i].second; //??????0?????´????????????S?????????
		for(int i=0; i<N; ++i){
			if(M<=0) break; //??????????¶???????????????£???????????????????????????
			int guarded = min(M,PD[i].second); //????????¨??¨????????????????????????????????¨?????¨???????????????????¶????
			S-=PD[i].first*guarded;
			M-=guarded; //????????????
		}
		cout << S << endl;
	}
}

/*for(int i=0; i<N; ++i){
			totd+=PD[i].second; //???????????§???????¨??????¢=????????£???????¨???????(1?????¢=1?????????)
			if(totd+PD[i+1].second>=M){
				last =i; //??????????????£??¨???????????????????????????????????????
				break; 
			}
		}
		for(int i=last+2; i<N; ++i){//?\???????????????????????¨??????????(????????????????????¨??????????????????)
			tote += PD[i].first*PD[i].second;
		}
		tote += (PD[last+1].second-(M-totd))*PD[last+1].first; //?????¨???????????????????????????????????????????¶????
		cout << tote <<endl;*/

Measured memory_bytes: 3088
/////////////////////////////////////////////

//
//	FileName	:	First.cpp
//	Creator		:	Fm
//	Date		:	2019-11-3 17:36
//	Comment		:	OJ(P2049)
//
///////////////////////////////////////////

//#include "pch.h"
#include <iostream>
#include <cstdio>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stack>
#include <string>
#include <string.h>
#include <set>
#include <queue>
#include <list>
#include <map>

using namespace std;
#define	MAXNUM		100000000
#define	EPS         0.0001
#define MODNUM		100003


typedef unsigned char       BYTE;
typedef int                 BOOL;
typedef unsigned long       DWORD;



int main(int argc, char* argv[])
{
	int				nInputN;
	int				nMax = 0;
	string			szInput;

	cin >> nInputN >> szInput;
	nInputN = 0;
	for (int i = 0; i < szInput.length(); i++)
	{
		if (szInput[i] == 'I')
			nInputN++;
		else
			nInputN--;
		nMax = max(nMax, nInputN);
	}


	cout << nMax;

Exit0:
	return 0;
}

Measured memory_bytes: 256