akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <stdio.h>
#include <functional>
#include <cfloat>
#include <math.h>


#define fs first
#define sc second

using namespace std;


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

const ll mod = 1000000007;
ll fact[200200];
ll invfact[200200];

inline ll take_mod(ll a){
    return (a % mod + mod) % mod;
}

inline ll add(ll a, ll b){
    return take_mod(a+b);
}

inline ll sub(ll a, ll b){
    return take_mod(a-b);
}


inline ll mul(ll a, ll b){
    return take_mod(a * b);
}

inline ll pow(ll x, ll n){
    ll res = 1LL;
    while(n > 0){
        if(n & 1) res = mul(res, x);
        x = mul(x, x);
        n >>= 1;
    }
    return res;
}

ll mod_inv(ll x){
    return pow(x, mod-2);
}

// nは上限
void make_fact(ll n){
    fact[0] = 1;
    ll res = 1;
    for(int i = 1; i <= n; i++){
        fact[i] = res;
        res = mul(res, i+1);
    }
}

// nは上限
void make_invfact(ll n){
    invfact[0] = 1;
    invfact[n] = mod_inv(fact[n]);
    for(int i = n-1; i >= 1; i--){
        invfact[i] = mul(invfact[i + 1], i + 1);
    }
}

ll perm(ll n, ll k){
    return mul(fact[n], invfact[n-k]);
}

ll comb(ll n, ll k){
    return mul(mul(fact[n], invfact[n-k]), invfact[k]);
}



int main(){
    ll N, M;
    ll a[110000];
    bool d[110000];
    cin >> N >> M;
    fill(d, d+N+10, false);
    for(int i = 0; i < M; i++){
        cin >> a[i];
        d[a[i]] = true;
    }

    ll dp[110000];
    dp[0] = 1;
    if(d[1]){
        dp[1] = 0;
    }
    else{
        dp[1] = 1;
    }

    for(int i = 2; i <= N; i++){
        if(d[i]){
            dp[i] = 0;
        }
        else{
            dp[i] = add(dp[i-1], dp[i-2]);
        }
    }

    cout << dp[N] << endl;



    return 0;
}


Measured memory_bytes: 1920
// Example program
#include <iostream>
#include <string>
#include <stdio.h>

int main()
{
    char a,b,c;
    scanf("%c%c%c",&a,&b,&c);
    if(a==b && b==c && c==a){
        printf("No");
    }
    else{
        printf("Yes");
    }
}


Measured memory_bytes: 256
def inputting():
    n=int(input())
    S=sorted(map(int,input().split()))
    q=int(input())
    T=list(map(int,input().split()))
    return n,S,q,T


def binarysearch( s, e, S, t):
    if s>=e:
        return 0
    elif S[(s+e)//2]==t:
        return 1
    elif S[(s+e)//2]>t:
        return binarysearch( s, (s+e)//2, S, t)
    elif S[(s+e)//2]<t:
        return binarysearch((s+e)//2+1, e, S, t)

    
def main():
    n,S,q,T=inputting()
    count=0
    for t in T:
        flag=binarysearch(0,n,S,t)
        if flag==1:
            count+=1
    print(count)

if __name__=='__main__':
    main()



Measured memory_bytes: 16708
# @author 

import sys

class CVacation:
    class Activity:
        def __init__(self, a, b, c):
            self.a = a
            self.b = b
            self.c = c

    def solve(self):
        n = int(input())
        a = []
        for i in range(n):
            a.append([int(_) for _ in input().split()])

        dp = [[0] * 3 for _ in range(n)]
        dp[0][0] = a[0][0]
        dp[0][1] = a[0][1]
        dp[0][2] = a[0][2]
        for i in range(1, n):
            for j in range(3):
                for k in range(3):
                    if k != j:
                        dp[i][j] = max(dp[i - 1][k] + a[i][j], dp[i][j])

        print(max(dp[n - 1]))

solver = CVacation()
input = sys.stdin.readline

solver.solve()


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

using namespace std;

const int mod = 1e9 + 7;

int expr();

string S;
int idx;

int number()
{
  int ret = 0;
  while(idx < S.size() && isdigit(S[idx])) {
    ret = ret * 10 + S[idx++] - '0';
  }
  return (ret);
}

int term()
{
  if(isdigit(S[idx])) return (number());
  idx += 2;
  auto ret = expr();
  ret = 1LL * ret * ret % mod;
  idx++;
  return (ret);
}

int expr()
{
  auto ret = term();
  int buff = idx;
  while(buff + 1 < S.size() && S[buff] == '>' && S[buff + 1] == '>') {
    buff += 2;
    if(buff >= S.size() || S[buff] == '>') break;
    idx += 2;
    auto get = term();
    for(int i = 0; i < get && ret > 0; i++) ret >>= 1;
    buff = idx;
  }
  return (ret);
}

int main()
{
  string T;
  while(getline(cin, T), T != "#") {
    idx = 0;
    S = "";
    for(int i = 0; i < T.size(); i++) if(T[i] != ' ') S += T[i];
    cout << expr() << endl;
  }
}

Measured memory_bytes: 5380
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    A = [int(x) for x in input().split()]

    x = 2 ** N
    c = 1

    past = [0]
    for i, a in enumerate(A):
        if a > c:
            print(-1)
            return
        elif a == 0:
            past.append(c)
            c *= 2
        else:
            past.append(c)
            c = (c - a) * 2

    ans = 0
    c = 0
    # print(*past)
    for i, p in enumerate(past[::-1]):
        if i == N + 1:
            continue
        ans += min(c + A[-1 -i], p)
        c += A[-i - 1]


    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 675344
import math
n=input()
a=map(int, raw_input().split())
a.sort()
a.reverse()


c=a[0]

b=[0 for i in range(n)]
for i in range(1,n):
	b[i]=abs(a[i]-c/2)

min_b=min(b[1:])

d=[]
for i in range(1,n):
	if b[i]==min_b:
		d.append(a[i])

d.sort()
d.reverse()

print c,d[0]


Measured memory_bytes: 12228
#include <bits/stdc++.h>
        using namespace std;
         
        int main() {
          int a, b, c;
          1<=a,b<=100;
          cin >> a >> b;
          c=a+b;
          if(c%2!=0){
           c=c+1;
          }
          cout << c/2 << endl;
        }

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

int main(void){
	int i, j;
	int lenstr;
    char str[100];

    while(fgets(str, 100, stdin) != NULL){
		lenstr = strlen(str);
		j = 0;
		while(j<26){
			for(i = 0; i < lenstr; i++){
				if(str[i]>='a' && str[i] <'z'){
					str[i] = 'a' + (str[i]-'a')+1;
				}else if(str[i] == 'z'){
					str[i] = 'a';
				}
			}
			if(strstr(str,"the") != NULL || strstr(str,"this") != NULL || strstr(str,"that") != NULL) {
				printf("%s", str);
				break;
			}
			j++;
		}
	}
	return 0;
}

Measured memory_bytes: 524
#include<iostream>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<limits>
#include<sstream> 
#include<unordered_map>      

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;
typedef vector<int> vi;
typedef vector<ll> vl;

const int inf = numeric_limits<int>::max() >> 2;
const ll linf = numeric_limits<ll>::max() >> 2;
const ull ulinf = numeric_limits<ull>::max() >> 2;
const double pi = acos(-1);
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const int dx8[8]={-1,0,1,-1,1,-1,0,1};
const int dy8[8]={-1,-1,-1,0,0,1,1,1};

#define p_queue(i) priority_queue<i> 
#define rp_queue(i) priority_queue<i, vector<i>, greater<i>> 
#define umap(i,j) unordered_map<i,j>
#define P(p) cout<<(p)<<endl
#define PS(p) cout<<(p)<< " "
#define IN cin >> 
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define rrep(i,m,n) for(int i = (m-1); i >= (int)(n); i--)
#define inrep(n,a) for(int i = 0; i < (int)(n); i++)cin >> a[i];
#define mod(i) ((i)%(ll)(1e9 + 7))
#define divm(a,b) (mod(a * modpow((ll)b,(ll)(1e9+5))))
#define rsort(a,b,c) sort(a, b, greater<c>())
#define vsort(v) sort(v.begin(), v.end())
#define rvsort(v,c) sort(v.begin(), v.end(), greater<c>()) 
#define ft first
#define sd second
#define pb push_back
#define it insert
#define sz(x) ((int)(x).size())
#define lb(a,n,k) (lower_bound(a,a+n,k) - a) 
#define vlb(a,k)  (lower_bound(a.begin(),a.end(),k) - a.begin())
#define ub(a,n,k) (upper_bound(a,a+n,k) - a) 
#define vub(a,k)  (upper_bound(a.begin(),a.end(),k) - a.begin())
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return

ll modpow(ll i,ll j){ ll tmp=1; while(j){ if(j%2)tmp=mod(tmp*i);i=mod(i*i);j/=2;}return tmp;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

vector<string> split(const string &str, char sep){
    vector<string> v;
    stringstream ss(str);
    string buffer;
    while( getline(ss, buffer, sep) ) {
        v.push_back(buffer);
    }
    return v;
}

//ll ncr[100][100];
//ll nCr(int n, int r){if(n==r) ret ncr[n][r] = 1; if(r==0) ret ncr[n][r] = 1; if(r==1) ret ncr[n][r] = n;if(ncr[n][r]) ret ncr[n][r]; ret ncr[n][r] = nCr(n-1,r) + nCr(n-1,r-1);}

//ll npr[100][100]={};
//ll nPr(int n,int r){if(npr[n][r])ret npr[n][r];if(r==0)ret npr[n][r] = 1;if(r==1)ret npr[n][r] = n;ret npr[n][r] = n * nPr(n-1,r-1);}

//ll nHr(int n,int r){ret nCr(n+r-1,r);}

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


int main(){
    
    string s,t = "";
    cin >> s;

    ll ans = 0;

    rep(i,0,sz(s)){
	if(i < sz(s)-1 && s[i] == 'B' && s[i+1] == 'C'){
	    t = t + "D";
	    i++;
	}else t = t + s[i];
    }
    // P(t);

    int d = 0;
    rrep(i,sz(t),0){
	if(t[i] == 'A')ans += d;
	else if(t[i] == 'D')d++;
	else d = 0;
    }
    P(ans);
  
    return  0;
}


Measured memory_bytes: 1436
#!/usr/bin/env python3


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N = int(input())
    C = input()

    left = 0
    right = 1

    ans = 0

    while (left+right<N):
        if C[left]=='W':
            if C[-right]=='R':
                ans += 1
                left += 1
                right += 1
            else:
                right += 1
        else:
            left += 1
    print(ans)

if __name__ == '__main__':
    main()


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

#ifdef LOCAL
#include "../dump.hpp"
#else
#define dump(...)
#define showvv(v)
#endif

using namespace std;

#define rep(i,n) for(int i=0,i##_len=(n);i<i##_len;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define ROF(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend() //sortで大きい順
#define UNIQUE(v) v.erase(unique(all(v)),v.end())
#define SUM(a) accumulate(all(a),0)
#define sz(x) ((int)(x).size())
#define pb push_back
#define fst first
#define snd second

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

int main(){
  int n; cin >> n;
  vector<ll> a(n); rep(i,n) cin >> a[i];
  a.pb(0); n++;
  ll ans = 0;
  ll tmp = 0;
  rep(i,n){
    ans += abs(a[i] - tmp);
    tmp = a[i];
  }

  tmp = 0;
  rep(i,n-1){ // i個目を飛ばした時
    ll x = ans;
    ans -= abs(a[i+1]-a[i]) + abs(a[i]-tmp);
    ans += abs(a[i+1]-tmp);
    cout << ans << endl;
    ans = x;
    tmp = a[i];
  }
}


Measured memory_bytes: 2032
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
int main(){
    long long n,m,p[100001],WA_count[100001]={},AC_count[100001]={},AC_locate[100001],ans=0,penalty=0;
    rep(i,100001){
        AC_locate[i] = -1;
    }
    string s[100001];
    cin >> n >> m;
    rep(i,m){
        cin >> p[i] >> s[i];
        if(s[i] == "AC" && AC_count[p[i]] == 0){
            AC_count[p[i]]++;
            AC_locate[p[i]] = i;
        }else if(s[i] == "WA" && AC_count[p[i]] == 0){
            WA_count[p[i]]++;
        }
    }
    
    for(int i=1;i<=n;i++){
        if(AC_locate[i] >= 0){
            ans++;
            penalty += WA_count[i];
        }
    }
    
    cout << ans << " " << penalty << endl;
} 


Measured memory_bytes: 8832
#include<stdio.h>

int main(){
    int n,i,j,ans;
    int h[100];

    scanf("%d",&n);

    for(i=0;i<n;i++){
        scanf("%d",&h[i]);
    }
    ans = h[0];
    for(j=0;j<n-1;j++){
        if(h[j]<h[j+1]){
            ans += h[j+1]-h[j];
        }
    }
    printf("%d",ans);
    return 0;
}

Measured memory_bytes: 128
#include<stdio.h>


int f(int X){
	
	int sum=0;
	while(X>0){
		
		sum+=X%10;
		X/=10;
	}
	
	return sum;
}



int main(){
	
	int N;
	scanf("%d",&N);
	
	if(N%f(N)==0){
		
		printf("\nYes\n\n");
	}else {
		printf("\nNo\n\n");
	}
		
	
	
	return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
#define N 200002
#define M 1000000007
typedef long long LL;

LL qpow(LL x, int y)
{
	if(!y) return 1;
	LL t = qpow(x, y >> 1);
	t = t * t % M;
	if(y & 1) t = t * x % M;
	return t;
}

LL f[N], invf[N];

int main() 
{
	int n, k, i, t, j, tn;
	LL ans, tf, s;
	
	scanf("%d%d", &n, &k);
	if(k >= n - 1){
		t = n + n - 1;
		for(tf = 1, i = 2; i < n; i++){
			tf = tf * (LL)i % M;
		}
		ans = qpow(tf, M - 2);
		tf = tf * (LL)i % M;
		ans = ans * qpow(tf, M - 2) % M;
		for(i++; i <= t; i++){
			tf = tf * (LL)i % M;
		}
		ans = ans * tf % M;
	}
	else{
		for(f[j = 0] = 1, i = 1; i <= n; j = i++){
			f[i] = f[j] * (LL)i % M;
		}
		invf[j = n] = qpow(f[n], M - 2);
		for(i = j - 1; i >= 0; j = i--){
			invf[i] = invf[j] * (LL)j % M;
		}
		ans = f[n] * f[tn = n - 1] % M;
		for(i = 0, s = 0; i <= k; i++){
			tf = invf[i];
			tf = tf * tf % M;
			tf = tf * invf[n - i] % M;
			tf = tf * invf[tn - i] % M;
			s += tf;
		}
		ans = ans * (s % M) % M;
	}
	printf("%lld\n", ans);
			
	return 0;
}

Measured memory_bytes: 3328
#%%
import sys
def input():
    return sys.stdin.readline().rstrip()

def main():
    W, H, x, y = map(int, input().split())

    print(float(W*H/2))
    if x == W/2 and y == H/2:
        print(1)
    else:
        print(0)

# %%
if __name__ == '__main__':
    main()

# %%
# from atcoder_test import doTest
# doTest("abc130","c",main)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
struct robots{
	int start;
	int finish;
};
bool operatorX(robots r1, robots r2){
	return (r1.finish < r2.finish);
}
int main(){
	int N;
	cin >> N;
	vector<robots> robs;
	for(int x = 0; x<N; x++){
		int y;
		int l;
		cin >> y;
		cin >> l;
		robots r;
		r.start = y-l;
		r.finish = y+l;
		robs.push_back(r);
	}
	sort(robs.begin(), robs.end(), operatorX);
	int temp = robs[0].finish;
	int count = 1;
	for(int x = 1 ; x<N; x++){
		if(robs[x].start >=temp){
			count++;
			temp = robs[x].finish;
		}
	}
	cout << count;

}
	



Measured memory_bytes: 1400
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define printVec(v) printf("{"); for (const auto& i : v) { std::cout << i << ", "; } printf("}\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; }
using namespace std;
using P = pair<int,int>;
using ll = long long;
const ll INF = 1LL<<60;

//cin.tie(0);ios::sync_with_stdio(false);
int main() {
  int n; 
  cin >> n;
  vector<int> a(n);
  rep (i, n) cin >> a[i];

  int limit = *max_element(a.begin(), a.end());
  vector<int> div(limit + 1);
  for (int i = 0; i < n; i++) {
    int tmp = a[i];
    while (tmp <= limit) {
      ++div[tmp];
      tmp += a[i];
    }
  }

  int ans = 0;
  for (int i = 0; i < n; i++) {
    if (div[a[i]] <= 1) ++ans;
  }

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


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

using ll = long long;

const int INF = 1001001001;
const ll INF_LL = 1001001001001001001LL;

int main(void){
  int n; cin >> n;
  vector<pair<int,int>> a(n);
  rep(i,n){
    int p;
    cin >> p;
    a[i] = make_pair(p,i);
  }

  sort(a.begin(),a.end());
  rep(i,n){
    if(a[n-1].second == i){
      cout << a[n-2].first << endl;
    }
    else{
      cout << a[n-1].first << endl;
    }
  }
  
  return 0;
}


Measured memory_bytes: 4732
while True:
    nums = raw_input().strip()
    if nums == '0':
        break

    nums = list(nums)
    nums.reverse()

    plus = True
    try:
        nums.remove('-')
        plus = False
    except:
        pass

    nums = map(int, nums)

    for i in range(len(nums)):
        if plus:
            if i % 2 != 0:
                nums[i] = -nums[i]
        else:
            if i % 2 == 0:
                nums[i] = -nums[i]

    for i in range(len(nums) + 1):
        try:
            if nums[i] < 0:
                nums[i] += 10
                if i == len(nums) - 1:
                    nums = nums + [0]
                nums[i + 1] += 1
            elif nums[i] == 10:
                nums[i] = 0
                if i == len(nums) - 1:
                    nums = nums + [0]
                nums[i + 1] -= 1
        except IndexError:
            pass

    print ''.join(map(str, reversed(nums)))

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

void put(string s) {
  cout << s;
}

int main() {
  int sx, sy, tx, ty;
  cin >> sx >> sy >> tx >> ty;

  int dx = tx - sx;
  int dy = ty - sy;

  rep(i, dx) put("R");
  rep(i, dy) put("U");
  put("R");
  rep(i, dy) put("D");
  put("D");
  put("L");
  rep(i, dx) put("L");
  put("U");

  rep(i, dy) put("U");
  rep(i, dx) put("R");
  put("U");
  rep(i, dx) put("L");
  put("L");
  put("D");
  rep(i, dy) put("D");
  put("R");
}

Measured memory_bytes: 256
//بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيمِ
//لا إله إلا الله محمد رسول الله

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")

#define ll long long
#define pb push_back
#define fr first
#define sc second
#define in freopen("input.txt", "r" , stdin)
#define out freopen("snakes.out", "w", stdout)
using namespace std;

ll n, W;
ll dp[105][100005];
ll w[100005], v[100005];
int main(){
    //in;
    //out;
    ios_base::sync_with_stdio(false);
    cin >> n >> W;

    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= W; j++) {
            dp[i][j] = dp[i-1][j];
            if (j >= w[i])dp[i][j] = max (dp[i][j], dp[i-1][j - w[i]] + v[i]);
        }
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= W; j++) {
            ans = max (ans, dp[i][j]);
        }
    }

    cout << ans;
}




Measured memory_bytes: 80128
#include <iostream>
#include <iosfwd>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cassert>
#include <cctype>
#include <climits>
#include <vector>
#include <bitset>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <deque>
#include <string>
#include <list>
#include <iterator>
#include <sstream>
#include <complex>
#include <fstream>
#include <functional>
#include <numeric>
#include <utility>
#include <algorithm>
#include <assert.h>
#include <unordered_map>

using namespace std;
const int N = 1e6 + 500;
const long long mod = 1e9 + 7;
const long long INF = 1LL << 57;
const int LN = 22;
const int SN = 320;

long long n, m, u, v, k, t, q, x, d, p, a, b, c, s;

string sa, sb;
int arr[N], cnt[N];
int main() {
   ios::sync_with_stdio(false);cin.tie(0);
   int best = 0;
   cin >> n;
   for (int i = 1; i <= n; ++i) cin >> arr[i];
   
   for (int i = 2; i <= n; ++i) {
      if (arr[i] <= arr[i - 1]) cnt[i] = cnt[i - 1] + 1;
      else cnt[i] = 0;
      best = max(best, cnt[i]);
   }
   cout << best << endl;
}



Measured memory_bytes: 4736
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e3 + 10;
int a[N], b[N], dp[2][3001][2];
int main() {
    int n, t;
    cin >> n >> t;
    for(int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
        int now = (i&1);
        int nxt = !now;
        memset(dp[nxt], 0, sizeof dp[nxt]);
        for(int j = t; j >= 1; j--) {
            dp[nxt][j][1] = dp[now][j-1][0] + b[i];
        }
        for(int j = t; j >= 1; j--) {
            for(int k = 0; k < 2; k++) {
                dp[nxt][j][k] = max(dp[nxt][j][k], dp[now][j][k]);
                dp[nxt][j][k] = max(dp[nxt][j][k], dp[nxt][j-1][k]);
                if(j >= a[i]) dp[nxt][j][k] = max(dp[nxt][j][k], dp[now][j-a[i]][k] + b[i]);
            }
        }
    }
    cout << dp[n&1][t][1] << endl;
    return 0;
}
/*
2 60
100 100
10 10
*/

Measured memory_bytes: 256
#include <iostream>
  #include <vector>
  #include <algorithm>
  
  using namespace std;
  
  int main() {
      int N, K;
      cin >> N >> K;
      vector<int> l(N);
      for(int i = 0; i < N; i++)
          cin >> l[i];
  
      sort(l.begin(), l.end(), greater<int>());
  
      int sum = 0;
  
      for(int i = 0; i < K; i++)
          sum += l[i];
  
      cout << sum << endl;
 }

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define br cout << "\n";
#define pb push_back
#define ll long long 
#define ff first 
#define ss second
#define all(x) x.begin(),x.end()
#define in(a , idx , n ) for (int i = idx ; i < n ; ++i)cin >>a[i];
#define fix() cout <<fixed <<  std::setprecision(10)
	
using namespace std;
const int MOD = 1000*1000*1000 + 7 ; 
const int MAXN = 1000*100 +10 ;
const ll INF = 1e18 ;

void solve(){
	string s ;
	cin >> s ;
	int l = s.length();
	if ( s[l-1] =='s')
		cout << s<<"es";
	else
		cout << s << "s" ;
		
}
	
int main (){
	
	int t = 1  ;
	// cin >> t ;
	while (t--){
		solve() ; 
	}
    
return 0 ; 
}


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

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

  int count = 0;
  bool flag = false;
  while(!flag)
  {
    if(b - a >= 2 || c - a >= 2) a += 2;
    else if(a - b >= 2 || c - b >= 2) b += 2;
    else if(a - c >= 2 || b - c >= 2) c += 2;
    else if(a - b >= 1 && a - c >= 1)
    {
      b += 1;
      c += 1;
    }
    else if(b - a >= 1 && b - c >= 1)
    {
      a += 1;
      c += 1;
    }
    else if(c - a >= 1 && c - b >= 1)
    {
      a += 1;
      b += 1;
    }
    else if((a==b&&a-c==1)||(a==c&&a-b==1)||(b==c&&b-a==1))
    {
      count += 2;
      flag = true;
    }
    else if(a == b && b == c) flag = true;
    if(!flag) count++;
  }

  cout << count << endl;
  return 0;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"io"
	"math"
	"os"
	"strconv"
	"strings"

)


func main() {
	solve(os.Stdin, os.Stdout)
}

type ReaderEx struct {
	baseScanner *bufio.Scanner
	words       []string
	nextWordIdx func() int
	initWordIdx func(int)
}

func NewScannerEx(stdin io.Reader) *ReaderEx {
	var this ReaderEx
	var idx int
	var wordsCnt int
	this.baseScanner = bufio.NewScanner(stdin)
	this.baseScanner.Buffer(make([]byte, 0), 1E+11)
	this.nextWordIdx = func() int {
		cur := idx
		idx = (idx + 1) % wordsCnt
		return cur
	}
	this.initWordIdx = func(wc int) {
		idx = 0
		wordsCnt = wc
	}
	return &this
}

func (me *ReaderEx) Scan(doSplit bool) (isScanned bool) {
	isScanned = me.baseScanner.Scan()
	if doSplit {
		me.words = strings.Fields(me.baseScanner.Text())
	} else {
		me.words = []string{me.baseScanner.Text()}
	}
	me.initWordIdx(len(me.words))
	return
}

func (me *ReaderEx) nextBytes() []byte {
	return []byte(me.words[me.nextWordIdx()])
}
func (me *ReaderEx) nextString() string {
	return me.words[me.nextWordIdx()]
}

type StringArray []string

func (me *ReaderEx) nextStringArray() StringArray {
	return me.words[me.nextWordIdx():]
}

func (me StringArray) toStrings() []string {
	return me
}

func (me StringArray) toInts() []int {
	strValues := me.toStrings()
	values := make([]int, len(strValues))
	for i, v := range strValues {
		n, err := strconv.Atoi(v)
		if err != nil {
			panic(err)
		}
		values[i] = n
	}
	return values
}
func (me *ReaderEx) nextInt() int {
	n, err := strconv.Atoi(me.words[me.nextWordIdx()])

	defer func() {
		if err != nil {
			panic(fmt.Sprintf("getInt(%d)", n))
		}
	}()
	return n
}

func pow(x, y, mod int) (ans int) {

	ans = 1
	for bit := 1 << uint(math.Floor(math.Log2(float64(y)))); ; bit >>= 1 {
		if y&bit != 0 {
			ans *= x
			if mod > 0 {
				ans %= mod
			}
		}
		if bit <= 1 {
			return
		}
		ans *= ans
		if mod > 0 {
			ans %= mod
		}
	}
}

type factType struct {
	prime int
	count int
}

func fact(n int) (facts []*factType) {

	for i := 2; i*i <= n; i++ {
		if n%i == 0 {
			fa := factType{prime: i}
			for n%fa.prime == 0 {
				n /= fa.prime
				fa.count++
			}
			facts = append(facts, &fa)
		}
	}
	if n > 1 {
		facts = append(facts, &factType{prime: n, count: 1})
	}
	return facts
}
func dec2bin(n int) (ret []bool) {
	for bit := 1 << uint(math.Floor(math.Log2(float64(n)))); ; bit >>= 1 {
		ret = append(ret, n&bit != 0)

		if bit <= 1 {
			return
		}
	}

}

func abs(v int) int {
	if v < 0 {
		v = -v
	}
	return v
}

func b2i(b bool) (i int) {
	if b {
		i = 1
	} else {
		i = 0
	}
	return
}

func solve(stdin io.Reader, stdout io.Writer) {

	r := NewScannerEx(stdin)
	r.Scan(true)
	a, b, c, k := r.nextInt(), r.nextInt(), r.nextInt(), r.nextInt()

	minInt := func(a int, vs ...int) int {
		for i := range vs {
			v := &vs[i]
			if a > *v {
				a = *v
			}
		}
		return a
	}
	w := minInt(a, k)
	ans := w
	k -= w
	k -= b
	if k > 0 {
		w = minInt(c, k)
		ans -= w
	}
	fmt.Fprintln(stdout, ans)
}


Measured memory_bytes: 1744
#include <bits/stdc++.h>
#define ll long long
#define pi pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define mod 1000000007
// #define mod 998244353
using namespace std;

vector<bool> bad(10);

int fun(int n)
{
	while (n)
	{
		if (bad[n % 10])
		{
			return 0;
		}
		n /= 10;
	}
	return 1;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < k; i++)
	{
		int d;
		cin >> d;
		bad[d] = 1;
	}
	while (!fun(n))
	{
		n++;
	}
	cout << n << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N = 105;
int n, trap[N][N], sign[N], used[N];
pair<int, int> edge[N];
bool match(int x) {
	for (int i = 1; i <= n; i++) {
		if (trap[x][i] && !used[i]) {
			used[i] = 1;
			if (!sign[i] || match(sign[i])) {
				sign[i] = x;
				return true;
			}
		}
	}
	return false;
}
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d %d", &edge[i].first, &edge[i].second);
	for (int i = 1; i <= n; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		for (int j = 1; j <= n; j++) {
			if (edge[j].first < x && edge[j].second < y)
				trap[i][j] = 1;
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		memset(used, 0, sizeof(used));
		if (match(i))
			ans++;
	}
	printf("%d", ans);
}

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

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    string s, t; cin >> s >> t;
    int ans = 0;
    for (int i = 0; i < s.size(); i++) if (s[i] != t[i]) ans++;
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 3780
#include<algorithm>
#include<iostream>
#include<stdio.h>
#include<string>
#include<memory.h>
#include<vector>
using namespace std;
string tostring(string s){
  int ch[30];
  memset(ch,0,sizeof(ch));
  for(int i=0;i<s.length();i++)
        ch[s[i]-'a']++;
  string res;
  for(int i=0;i<26;i++){
    if(ch[i]>0){
        res.append(1,'a'+i);
        res.append(1,ch[i]+'a');
    }
  }
  return res;
}
int main(){
  int n;
  cin>>n;
  vector<string>s;
  string in,key;
  for(int i=0;i<n;i++){
    cin>>in;
    key=tostring(in);
    s.push_back(key);
  }
  long long sum=0;
  sort(s.begin(),s.end());
  for(int i=0;i<n-1;i++)
  {
      long long num=1;
      while(s[i]==s[i+1]){
        num++;
        i++;
        if(i>=n-1) break;
      }
      if(num>1)
      {
          sum+=num*(num-1)/2;
      }
  }
  cout<<sum<<endl;
}


Measured memory_bytes: 8052
import numpy as np
W,H,N=map(int,input().split())
MAP=[[0 for i in range(W)] for j in range(H)]
command=[list(map(int,input().split())) for i in range(N)]
for x,y,a in command:
    if a==1:
        for i in range(H):
            for j in range(x):
                MAP[i][j]=1
    elif a==2:
        for i in range(H):
            for j in range(x,W):
                MAP[i][j]=1
    elif a==3:
        for i in range(y):
            for j in range(W):
                MAP[i][j]=1
    else:
        for i in range(y,H):
            for j in range(W):
                MAP[i][j]=1
#print(np.array(MAP))
cnt=0
for i in range(H):
    cnt +=MAP[i].count(0)
print(cnt)

Measured memory_bytes: 21008
#include <stdio.h>
#include <string.h>
#define N 256
#define M 1000000007
typedef long long LL;

char s[N][9] = {0}, a[4] = {'A', 'C', 'G', 'T'}, t[9] = {0};
int f[N] = {0};
LL d[101][N] = {0}, ans = 0;

int ju(char *a)
{
	return a[0] == 'A' && a[1] == 'G' && a[2] == 'C' || a[1] == 'A' && a[2] == 'G' && a[3] == 'C';
}

int judge(char *a)
{
	int i, j;
	char t;
	if(ju(a)) return 0;
	for(i = 1, j = 0; i < 4; j = i++){
		t = a[i], a[i] = a[j], a[j] = t;
		if(ju(a)) return 0;
		t = a[i], a[i] = a[j], a[j] = t;
	}
	return 1;	
}

int main()
{		
	int i, j, n, x;
	int i1, i2, i3, i4;
	
	scanf("%d", &n);
	if(n == 3){
		puts("61");
		return 0;
	}	
	for(i1 = 0, i = 0; i1 < 4; i1++){
		t[0] = a[i1];
		for(i2 = 0; i2 < 4; i2++){
			t[1] = a[i2];
			for(i3 = 0; i3 < 4; i3++){
				t[2] = a[i3];
				for(i4 = 0; i4 < 4; i4++, i++){
					t[3] = a[i4];
					strcpy(s[i], t);
					if(judge(s[i])) f[i] = 1, d[4][i] = 1;
				}
			}
		}
	}
	for(i = 5, i1 = 4; i <= n; i1 = i++){
		for(j = 0; j < N; j++){
			if(!f[j]) continue;
			x = j >> 2;
			d[i][j] = (d[i1][x] + d[i1][x + 64] + d[i1][x + 128] + d[i1][x + 192]) % M;
		}
	}
	for(i = 0; i < N; i++) ans += d[n][i];
	printf("%lld\n", ans %= M);
		
	return 0;
}

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

#define LL long long
#define Dl double
#define Pb push_back
#define Po pop_back
#define Mp make_pair
#define Ub upper_bound
#define Lb lower_bound
#define In insert
#define All(x) x.begin(), x.end()
#define mem(a, b) memset(a, b, sizeof(a))
#define fast ios_base::sync_with_stdio(0);cin.tie(0)

using namespace std;

typedef vector<LL> Vl;
typedef vector<Vl> VVl;
typedef pair<LL, LL> Pll;
typedef vector<Pll> Vpl;
typedef queue<LL> Ql;
typedef stack<LL> Sl;
#define X first
#define Y second
#define mx3 1010
#define mx4 10010
#define mx5 100010
#define mx6 1000010

LL N[60][60], M[60][60];

int main()
{
    //freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);

    LL n, m;
    cin >> n >> m;

    for(LL i = 1; i <= n; i++){
        for(LL j = 1; j <= n; j++){
            char ch;
            cin >> ch;

            if(ch == '#')
                N[i][j] = 1;
        }
    }

    for(LL i = 1; i <= m; i++){
        for(LL j = 1; j <= m; j++){
            char ch;
            cin >> ch;

            if(ch == '#')
                M[i][j] = 1;
        }
    }

    for(LL i = 1; i <= n - m + 1; i++){
        for(LL j = 1; j <= n - m + 1; j++){
            LL f = 0;
            for(LL k = 0; k < m; k++){
                for(LL l = 0; l < m; l++){
                    if(N[i + k][j + l] != M[k + 1][l + 1])
                        f = 1;
                }
            }
            if(!f)
                return cout << "Yes\n", 0;
        }
    }

    cout << "No\n";
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <queue>

#define rep(i,n) for(int i=0;i<n;i++)
#define dup(x,y) (((x)+(y)-1)/(y)) // dup * y >= x なる最小のdup.
using namespace std;
typedef long long ll;
using Graph = vector<vector<int>>;
//	std::cout<<std::fixed<<std::setprecision(10);

int main() {
	string A, B, C;
	cin >> A >> B >> C;
	if(B[0]==A.back() && C[0]==B.back()) {
		cout << "YES" << endl;
	} else cout << "NO" << endl;

	return 0;
}

Measured memory_bytes: 256
#include"bits/stdc++.h"
#define int long long
#define rep(i,n) for(int i=0,i##_len=(n);i<i##_len;++i)
#define itr(i,x) for(auto i=(x).begin();i!=(x).end();++i)
#define All(x) (x).begin(),(x).end()
using namespace std;
typedef pair<int,int> P;
const int mod=1000000007;


int mpow(int a,int x);
int m_inv(int n){return mpow(n,mod-2);}

int gcd(int x,int y){return y?gcd(y,x%y):x;}
int lcm(int x,int y){return x*y/gcd(x,y);}

signed main(){
    int N;cin>>N;
    vector<int> a(N);
    rep(i,N) cin>>a[i];
    int left=-100,right=100;
    int ans=0;
    while(left!=right){
    	int lcost=0,mcost=0,rcost=0;
    	int mid=(left+right)/2;
    	rep(i,N){
    		lcost+=mpow(left-a[i],2);
    		rcost+=mpow(right-a[i],2);
    	}
    	if(lcost>rcost){ 
    		if(left!=mid) left=mid;
    		else left=right;
    	}
    	else if(lcost<rcost){ 
    		if(right!=mid) right=mid;
    		else right=left;
    	}
    	else left=right=mid;
    }
    rep(i,N) ans+=mpow(right-a[i],2);
    cout<<ans<<endl;
}

int mpow(int a,int x){
	int ans=1;
	while(x>0){
		if(x%2==1) (ans*=a)%=mod;
		(a*=a)%=mod;
		x>>=1;
	}
	return ans;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using p = pair<int, int>;
#define INF 1001001001
#define PI 3.14159265359
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define repX(i, n ,x) for (int i = x; i < (int)(n); ++i)
#define repB(i, n) for (int i = n; i >= 0; --i)
#define repBX(i, n) for (int i = n; i >= 0; --i)
#define dup(x,y) (((x)+(y)-1)/(y))

int main() {
    int N;
    cin >> N;
    string S,T;
    cin >> S >> T;
    string A = "";
    rep(i,N){
        A = A + S[i] + T[i];
    }
    cout << A << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main()
{
	
	int b, r, g, c, s, t;
	for(;;){
		int b_cont = 0;
		bool is_bonus = false;
		int coin = 100;
		
		cin >> b >> r >> g >> c >> s >> t;
		if(t == 0){
			break;
		}
		
		//Q[ñÉX^[Íl¶µÈ¢
		for(int i = t-s; i > 0; i--)
		{
			if(b_cont == 0){
				is_bonus = false;
			}
			
			//1Q[²ÆÉ¸¤RC
			if(is_bonus == false){
				coin -= 3;
				//íÉ{[iXQ[
				if(b > 0 || r > 0){
					if(b > 0){
						b--;
						b_cont = 5;
					}
					else{
						b_cont = 3;
						r--;
					}
					coin += 15;
					is_bonus = true;
				}
				else if(c > 0 || g > 0)
				{
					//áÁ½ç`F[oruhEª½éæ
					if(c > 0){
						c--;
						coin += 2;
					}
					else{
						g--;
						coin += 7;
					}
				}
			}
			else{
				//{[iXQ[
				coin -= 2;
				coin += 15;
				b_cont--;
			}
		}
		
		cout << coin << endl;
	}
}
		

Measured memory_bytes: 0
// AtCoder template
// sabaより胡蝶しのぶさんの方が可愛いのではないか？
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i = 0; i < n; ++i)

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

    ll x; cin >> x;
    cout << x/500*1000 + (x%500)/5*5 << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define INF ((1LL<<62)-(1LL<<31))
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define bit(n,m)(((n)>>(m))&1)
int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}
ll pom(ll a,ll n,int m){ll x=1;for(a%=m;n;n/=2)n&1?x=x*a%m:0,a=a*a%m;return x;}
//#define MOD 998244353
#define MOD 998244353
#define invp(a,p)pom(a,p-2,p)
#define add(x,y)(x=(x+y)%MOD)

ll dp[3010][3010];
ll ppow[3010][3010];

int main(){
	int a,b,c,d;
	scanf("%d%d%d%d",&a,&b,&c,&d);
	
	rep(i,a,c+1){
		ppow[i][0]=1;
		rep(j,1,d+1)ppow[i][j]=ppow[i][j-1]*i%MOD;
	}
	
	dp[a][b]=1;
	rep(i,a+1,c+1)rep(j,b,d+1){
		ll hoge=(dp[i][j-1]-dp[i-1][j-1]*(j-1))%MOD;
		dp[i][j]=(dp[i-1][j]*j+hoge*(i-1)+dp[i-1][j-1]*(i-1))%MOD;
	}
	//rep(i,0,c+1){rep(j,0,d+1)printf("%lld ",dp[i][j]);puts("");}puts("");
	
	ll ans=0;
	rep(j,b,d+1)add(ans,dp[c][j]*ppow[c][d-j]);
	printf("%lld",(ans+MOD)%MOD);
}

Measured memory_bytes: 142720
H, W = map(int, input().split())
S = [input() for _ in range(H)]

L = [[0] * W for _ in range(H)]
R = [[0] * W for _ in range(H)]
U = [[0] * W for _ in range(H)]
D = [[0] * W for _ in range(H)]

for h in range(H):
    for w in range(W):
        if S[h][w] == ".":
            L[h][w] = L[h][w-1] + 1
            U[h][w] = U[h-1][w] + 1
        if S[h][W-w-1] == ".":
            R[h][-w-1] = R[h][-w] + 1
        if S[H-h-1][w] == ".":
            D[-h-1][w] = D[-h][w] + 1
ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, R[h][w] + L[h][w] + U[h][w] + D[h][w] - 3)
print(ans)


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

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

signed main(){
    string S;
    int n,w,s,e;
    n=w=s=e=0;
    cin>>S;
    rep(i,S.size()){
        if(S[i]=='N')n++;
        if(S[i]=='W')w++;
        if(S[i]=='S')s++;
        if(S[i]=='E')e++;
    }

    bool ok=true;
    if(n+s&&(n==0||s==0))ok=false;
    if(w+e&&(w==0||e==0))ok=false;

    if(ok)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<algorithm>
#include<array>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<iso646.h>
#include<queue>
#include<stack>
#include<string>
#include<vector>

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

#define FOR(counter,initial_value,condition) for(int counter = initial_value; counter < condition;counter++)

int digitSum(int n,int digit=8) {
	// digit > 2
	int x = 1;
	FOR(i,0,digit){
		x *= 10;
	}
	int sum = 0;
	FOR(i, 0, digit) {
		sum += n / x;
		n %= x;
		x /= 10;
	}
	sum += n;
	return sum;
}

int main()
{
	char S[52][52] = {};
	int height, width;
	cin >> height >> width;
	FOR(i, 1, height+1) {
		FOR(j, 1, width+1) {
			cin >> S[i][j];
		}
	}
	int count = 8;
	FOR(i, 1, height+1) {
		FOR(j, 1, width+1) {
			if (S[i][j] == '.') {
				if (S[i - 1][j - 1] != '#')		count--;
				if (S[i - 1][j]     != '#')		count--;
				if (S[i - 1][j + 1] != '#')		count--;
				if (S[i][j - 1]		!= '#')		count--;
				if (S[i][j + 1]		!= '#')		count--;
				if (S[i + 1][j - 1] != '#')		count--;
				if (S[i + 1][j]		!= '#')		count--;
				if (S[i + 1][j + 1] != '#')		count--;
				S[i][j] = (char)(count+0x30);
				count = 8;
			}
		}
	}
	FOR(i, 1, height + 1) {
		FOR(j, 1, width + 1) {
			cout << S[i][j];
		}
		cout << endl;
	}
	
}


Measured memory_bytes: 256
import sys

sys.setrecursionlimit(100000)


def check(i, xs, checked):
    xi = xs[i]
    children = set()
    for j, d in links[i]:
        if checked[j]:
            continue
        if j not in xs:
            xs[j] = xi + d
        elif xi + d != xs[j]:
            return False
        children.add(j)
    checked[i] = True
    for j in children:
        if not check(j, xs, checked):
            return False
    return True


def solve():
    checked = [False] * n
    for i in range(n):
        if not checked[i]:
            xs = {}
            xs[i] = 0
            res = check(i, xs, checked)
            if not res:
                return False
            mn, mx = min(xs.values()), max(xs.values())
            if mx - mn > 1e9:
                return False
    return True


n, m = map(int, input().split())
links = [set() for _ in range(n)]
for _ in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    links[l].add((r, d))
    links[r].add((l, -d))
print('Yes' if solve() else 'No')


Measured memory_bytes: 169176
import sys

# B - Substring
def count(substring):
  global T
  global t
  c = 0

  for i in range(t):
    if T[i] != substring[i]:
      c += 1

  return c


S = input()
T = input()

s = len(S)
t = len(T)
ans = t

for i in range(s-t+ 1):
  substring = S[i:i+t]
  ans = min(ans, count(substring))

print(ans)

Measured memory_bytes: 9160
#include <iostream>
#include <string>
using namespace std;
int main() {
	int x = 0;
	string W, T;
	cin >> W;
	while (cin >> T, T != "END_OF_TEXT") {
		for (int i = 0; i < T.size(); i++) T[i] = tolower(T[i]);
		if (W == T) x++;
	}
	cout << x << endl;
}

Measured memory_bytes: 1192
#include<stdio.h>

int main(void)
{
    int n,a;
    scanf("%d%d",&n,&a);
    while((1>n||n>100)||(0>a||a>n*n))
    {
        scanf("%d%d",&n,&a);
    }
    printf("%d\n",n*n-a);
    return 0;
}

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

int main(){
  int N;
  cin>>N;
  set<int> A;
  for(int i=0;i<N;i++){
    int j;
    cin>>j;
    if(A.count(j)){
      cout<<"NO"<<endl;
      return 0;
    }
    A.insert(j);
  }
  cout<<"YES"<<endl;
}

Measured memory_bytes: 9600
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;


public class Main 
{
	public static void main(String[] args)
	{
		Scanner scanner = new Scanner(System.in);
		
		for(int count=0; ; count++)
		{
			int a = scanner.nextInt();
			int b = scanner.nextInt();
			if(a==0 && b==0)
			{
				break;
			}
			
			if(count > 0)
			{
				System.out.println("");
			}
			
			List<Integer> list = new ArrayList<>();
			for(int i=a; i<=b; i++)
			{
				if((i%4==0 && i%100>0) || i%400==0)
				{
					list.add(i);
				}
			}
			
			if(list.size() > 0)
			{
				for(int y : list)
				{
					System.out.println(y);
				}
			}
			else
			{
				System.out.println("NA");
			}
		}
	}
}

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

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

int n;
int dp[111][111];

int main()
{
  cin >> n;
  rrep(i, 1, n + 1) rrep(j, 1, n + 1) cin >> dp[i][j];

  rrep(i, 1, n + 1) rrep(j, 1, n) dp[i][j + 1] += dp[i][j];
  rrep(i, 1, n) rrep(j, 1, n + 1) dp[i + 1][j] += dp[i][j];

  int res = -11111;
  rrep(tx, 1, n + 1) rrep(ty, 1, n + 1) rep(sx, tx) rep(sy, ty) res = max(res, dp[tx][ty] - dp[tx][sy] - dp[sx][ty] + dp[sx][sy]);

  cout << res << endl;

  return 0;
}

Measured memory_bytes: 1208
function yesNoRange(){
    var Arr = x.split(" ");
    var a = Arr[0] -0;
    var b = Arr[1] -0;
    var c = Arr[2] -0;

    if (a < b && b < c) {
        console.log("Yes");
    } 
    else {
        console.log("No");
    } 
}

var x = require('fs').readFileSync('/dev/stdin', 'utf8');

yesNoRange(x)


Measured memory_bytes: 15096
s = input()[::-1]

res = 0
cnt = {0: 1}
now = 0
p = 1
for i in range(len(s)):
    now = (now + (10 * p) * int(s[i])) % 2019
    cnt[now] = cnt.get(now, 0) + 1
    p = (p * 10) % 2019

print(sum(cnt[k] * (cnt[k] - 1) // 2 for k in cnt))


Measured memory_bytes: 9384
from itertools import permutations

n, m = map(int, input().split())
ab = []
for i in range(m):
    ai, bi = map(int, input().split())
    ab.append([ai, bi])
ab = sorted(ab)

per_origin = []
for i in range(2, n+1):
    per_origin.append(i)

res = 0
for per in permutations(per_origin, len(per_origin)):
    root = [1] + list(per)
    flag = 0
    for i in range(n-1):
        if [root[i], root[i+1]] not in ab and [root[i+1], root[i]] not in ab:
            flag = 1
            break
    if not flag:
        res += 1

print(res)


Measured memory_bytes: 3064
#[allow(dead_code)]
fn main() {
    let mut bb = i::str();
    if (bb == "ABC".to_string()) {
        println!("ARC");
    }else{
        println!("ABC");
    }


}


#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::{HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::io::*;
#[allow(unused_imports)]
use std::num::*;
#[allow(unused_imports)]
use std::str::*;

#[allow(dead_code)]
mod i {
    use super::*;

    pub fn read<T: FromStr>() -> T {
        stdin()
            .bytes()
            .map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>()
            .parse::<T>()
            .ok()
            .unwrap()
    }

    pub fn str() -> String {
        read()
    }

    pub fn s() -> Vec<char> {
        str().chars().collect()
    }

    pub fn i() -> i64 {
        read()
    }

    pub fn u() -> usize {
        read()
    }

    pub fn u2() -> (usize, usize) {
        (read(), read())
    }

    pub fn u3() -> (usize, usize, usize) {
        (read(), read(), read())
    }

    pub fn f() -> f64 {
        read()
    }

    pub fn c() -> char {
        read::<String>().pop().unwrap()
    }

    pub fn iv(n: usize) -> Vec<i64> {
        (0..n).map(|_| i()).collect()
    }
    pub fn strv(n: usize) -> Vec<String> {
        (0..n).map(|_| str()).collect()
    }

    pub fn iv2(n: usize) -> Vec<(i64, i64)> {
        (0..n).map(|_| iv(2)).map(|a| (a[0], a[1])).collect()
    }

    pub fn uv(n: usize) -> Vec<usize> {
        (0..n).map(|_| u()).collect()
    }

    pub fn uv2(n: usize) -> Vec<(usize, usize)> {
        (0..n).map(|_| uv(2)).map(|a| (a[0], a[1])).collect()
    }

    pub fn uv3(n: usize) -> Vec<(usize, usize, usize)> {
        (0..n).map(|_| uv(3)).map(|a| (a[0], a[1], a[2])).collect()
    }

    pub fn fv(n: usize) -> Vec<f64> {
        (0..n).map(|_| f()).collect()
    }

    pub fn cmap(h: usize) -> Vec<Vec<char>> {
        (0..h).map(|_| s()).collect()
    }
}


Measured memory_bytes: 2076
from pprint import pprint
import sys

def solve(n):
    for i in range(n // 100 + 1):
        if 100 * i <= n <= 105 * i:
            print(1)
            return
    
    print(0)
    

if __name__ == "__main__":
    n = int(sys.stdin.readline().strip())
    solve(n)

Measured memory_bytes: 38384
#include <iostream>
#include <stack>

int main(){
	std::stack<int> railroad;
	
	int incar;
	while(std::cin >> incar){
		if(incar != 0){
			railroad.push(incar);
		}else{
			std::cout << railroad.top() << std::endl;
			railroad.pop();
		}
	}
	return 0;
}

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

struct edge{int s,t,n;}e[100010];
int n,k,a[100010],h[100010],ans;

int dfs(int x)
{
	int d=0;
	for (int i=h[x],y; y=e[i].t,i; i=e[i].n)
		d=max(d,dfs(y)+1);
	if (d==k-1)  return ans+=(a[x]!=1),-1;  else  return d;
}

void work()
{
	scanf("%d %d %d",&n,&k,&a[1]);
	if (a[1]!=1)  ans++,a[1]=1;
	for (int i=2; i<=n; i++)
		scanf("%d",&a[i]),e[i]=(edge){a[i],i,h[a[i]]},h[a[i]]=i;
	dfs(1);
	printf("%d",ans);
}

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


Measured memory_bytes: 5376
#include <numeric>
#include<iostream>
#include<set>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include <cstdio>
#include<algorithm>
#include <sstream>
#include<string>
#include <cmath>
#include <iomanip>
#include <string>
#include<list>
using namespace std;
#define inf 1000000007
#define int long long
#define rep(i,j,n) for(int i=j;i<n;i++)
typedef pair<int,int>  P;
struct edge{int to,cost;};
double pi = 3.141592653589793;
//使うやつはここから下に置こうな
const int mxn = 100005;

int n, m;
struct data {
    int x, y, w;
    
    data(int a = 0, int b = 0, int c = 0) : x(a), y(b), w(c) {} ;
    
    bool operator < (const data &d) const {
        return w < d.w;
    }
} a[mxn], b[mxn], c[mxn << 1];

int fa[mxn];

int find(int u) {
    return u == fa[u] ? u : fa[u] = find(fa[u]);
}

signed main() {
    cin>>n;
    
    for (int i = 1; i <= n; ++i) {
        cin>>a[i].w, a[i].x = i;
        cin>>b[i].w, b[i].x = i;
    }
    
    sort(a + 1, a + n + 1);
    sort(b + 1, b + n + 1);
    
    for (int i = 1; i < n; ++i) {
        c[m++] = data(a[i].x, a[i + 1].x, a[i + 1].w - a[i].w);
        c[m++] = data(b[i].x, b[i + 1].x, b[i + 1].w - b[i].w);
    }
    
    sort(c, c + m);
    
    long long ans = 0;
    
    for (int i = 1; i <= n; ++i)fa[i] = i;
    
    for (int i = 0; i < m; ++i) {
        int x = find(c[i].x);
        int y = find(c[i].y);
        
        if (x != y) {
            ans += c[i].w, fa[x] = y;
        }
    }
    
    printf("%lld\n", ans);
}

Measured memory_bytes: 10368