akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define mod 1000000007

int main()
{
    int n;
    cin>>n;
    string s;
    cin>>s;
    int count=0;
    for(int i=0;i<n-2;i++)
    {
        if(s[i]=='A' && s[i+1]=='B'&& s[i+2]=='C')
            count++;
    }
    cout<<count;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
#include <functional>
#include <algorithm>
#include <stack>

using namespace std;

typedef pair<int, int> P;
typedef pair<int, P> Q;
typedef pair<double, int> R;

struct edge {
	int to;
	double cost;
};

vector<edge> G[1005];
double d[1005];

#define INF 1000000000.0

void dijkstra(int s) {
	priority_queue<R, vector<R>, greater<R> > que;
	fill(d, d+1005, INF);
	d[s] = 0.0;
	que.push(R(0.0, s));

	while (!que.empty()) {
		R p = que.top();
		que.pop();
		int v = p.second;
		if (d[v] < p.first) continue;
		for (int i = 0; i < G[v].size(); i++) {
			edge e = G[v][i];
			if (d[e.to] > d[v] + e.cost) {
				d[e.to] = d[v] + e.cost;
				que.push(R(d[e.to], e.to));
			}
		}
	}
}

int main() {
	int n;
	while (cin >> n) {
		if (n == 0) {
			break;
		}
		for (int i = 0; i < 1005; i++) {
			G[i].clear();
		}
		vector<Q> data;
		for (int j = 0; j < n; j++) {
		int b, x, y;
		cin >> b >> x >> y;
		data.push_back(Q(b, P(x, y)));
		for (int i = 0; i < data.size()-1; i++) {
			P p = data[i].second;
			edge e;
			e.to = data[i].first;
			e.cost = sqrt((p.first-x)*(p.first-x)+(p.second-y)*(p.second-y));
			if (e.cost > 50.0) {
				continue;
			}
			G[b].push_back(e);
			e.to = b;
			G[data[i].first].push_back(e);
		}
		}
		int m;
		cin >> m;
		int s, g;
		for (int i = 0; i < m; i++) {
			cin >> s >> g;
			dijkstra(s);
			if (d[g] == INF) {
				cout << "NA" << endl;
			} else {
				stack<int> stk;
				stk.push(g);
				while (stk.top() != s) {
					int k = stk.top();
					for (int j = 0; j < G[k].size(); j++) {
						edge e = G[k][j];
						if (d[k] == d[e.to]+e.cost) {
							stk.push(e.to);
							break;
						}
					}
				}
				cout << stk.top();
				stk.pop();
				while (!stk.empty()) {
					cout << ' ' << stk.top();
					stk.pop();
				}
				cout << endl;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 1264
S = input()
zenhan = int(S[:2])
kouhan = int(S[2:])
if zenhan == 0 and kouhan != 0:
    if kouhan <= 12:
        print('YYMM')
    else:
        print('NA')
elif kouhan == 0 and zenhan != 0:
    if zenhan <= 12:
        print('MMYY')
    else:
        print('NA')
elif zenhan == 0 and kouhan == 0:
    print('NA')
elif zenhan > 12 and kouhan > 12:
    print('NA')
elif zenhan <= 12 and kouhan <= 12:
    print('AMBIGUOUS')
elif zenhan <= 12 and kouhan > 12:
    print('MMYY')
elif zenhan > 12 and kouhan <= 12:
    print('YYMM')

Measured memory_bytes: 3064
#include <stdio.h>
int main(void){
	int a,b,c,d;
	scanf("%d %d %d %d",&a,&b,&c,&d);
	if((a==b&&c==d)||(a==d&&b==c)||(a==c&&b==d)){
	printf("yes\n");
	}
	else{
		printf("no\n");
	}
	return 0;
}


Measured memory_bytes: 2140
#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 = (1<<30)-1;
const long long LINF = (1LL<<62)-1;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
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; }

vector<vector<int>> to;
vector<int> a, res;
void dfs(int now, int prev, vector<int> &lis) {
  auto it = lower_bound(lis.begin(), lis.end(), a[now]);
  int past = *it;
  *it = a[now];
  res[now] = lower_bound(lis.begin(), lis.end(), INF)-lis.begin();
  for (auto next : to[now]) {
    if (next == prev)
      continue;
    dfs(next, now, lis);
  }
  *it = past;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  a.resize(n);
  rep(i, n)
    cin >> a[i];
  to.resize(n);
  rep(i, n-1) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    to[u].push_back(v);
    to[v].push_back(u);
  }
  res.resize(n);
  vector<int> lis(n, INF);
  dfs(0, -1, lis);
  rep(i, n)
    cout << res[i] << '\n';
  return 0;
}

Measured memory_bytes: 30760
#include<iostream>
using namespace std;
int main()
{
  int n,m,i;
  cin >> n >> m;
  if(n<=m){
    for(i=0;i<m;i++)
      cout << n;
    cout << endl;
  }else{
    for(i=0;i<n;i++)
      cout << m;
    cout << endl;
  }
  return 0;
}

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


int main() {
  int n;
  cin >> n;
  int ans = 1000-n%1000;
  if(ans == 1000) ans = 0;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3628
n, m, q = map(int, input().split())
M = [[0] * 500 for _ in range(500)]
for _ in range(m):
    l, r = map(int, input().split())
    M[l - 1][r - 1] += 1
S = [[0] * 500 for _ in range(500)]
S[0][0] = M[0][0]
for r in range(1, 500):
    S[0][r] = S[0][r - 1] + M[0][r]
for l in range(1, 500):
    S[l][0] = S[l - 1][0] + M[l][0]
    for r in range(1, 500):
        S[l][r] = S[l][r - 1] + S[l - 1][r] + M[l][r] - S[l - 1][r - 1]
for _ in range(q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    ans = S[r][r]
    if l > 0:
        ans -= S[l - 1][r] + S[r][l - 1]
        ans += S[l - 1][l - 1]
    print(ans)


Measured memory_bytes: 15300
from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))
b=[]
c=[]
d=defaultdict(int)
for i in range(n):
    d[a[i]]+=1

for i,j in d.items():
    if j>=2:
        b.append(i)
    if j>=4:
        c.append(i)

if len(b)<2 and len(c)<1:
    print(0)
elif len(c)==1 and len(b)<2:
    print(c[0]**2)
else:
    b.sort(reverse=True)
    rec=b[0]*b[1]
    if len(c)>=1:
        c.sort(reverse=True)
        cube=c[0]**2
    else:
        cube=0
    print(max(rec,cube))

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

int main() {
  ll a,b,c,d; cin >> a >> b >> c >> d;
   cout << max(a*c, max(a*d, max(b*c, b*d))) << endl;
}

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

#define int long long
#define otp(n) cout << n;
#define ct(n) cout << n << endl;
#define cts(n) cout << n << " ";
#define cte cout << endl;
#define ctv(v) rep(i,(v).size()) otp(v[i]) cte
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define repo(i,o,n) for(int i=o;i<n;i++)
#define repm(i,n) for(int i=n-1;i>=0;i--)
#define repv(i,v) for(int i=0;i<(v).size();i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define sperase(v,n) (v).erase(remove(all(v), n), (v).end());
#define vdelete(v) (v).erase(unique(all(v)), (v).end());
#define vcopy(v1,v2) copy((v1).begin(), (v1).end(), back_inserter((v2)));
#define pb(n) push_back(n);

string s[3];

main() {
    rep(i,3) cin >> s[i];
    rep(i,3) reverse(all(s[i]));
    int z=0;
    while (1) {
        if(s[z].empty()) {
            ct((char)(z+'A'))
            return 0;
        }
        int tmp=(int)(s[z].back()-'a');
        s[z].pop_back();
        z=tmp;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  string S;
  cin >> S;
  
  if(S == "Sunny") {
    cout << "Cloudy" << endl;
  }
  if(S == "Cloudy") {
    cout << "Rainy" << endl;
  }
  if (S == "Rainy") {
    cout << "Sunny" << endl;
  }
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
const double PI = acos(-1);
const double EPS = 1e-9;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }
int merge(vector<int>&a, int l, int mid, int r) {
	int n1 = mid - l;
	int n2 = r - mid;
	vector<int>L(n1 + 1), R(n2 + 1);
	rep(i, 0, n1)L[i] = a[l + i];
	L[n1] = INF;
	rep(i, 0, n2)R[i] = a[mid + i];
	R[n2] = INF;
	int ret(0), i(0), j(0);
	rep(k, l, r) {
		if (L[i] <= R[j]) {
			ret += n2 - j;
			a[k] = L[i++];
		}
		else {
			a[k] = R[j++];
		}
	}
	return ret;
}
int mergeSort(vector<int>&a, int l, int r) {
	if (r - l > 1) {
		int mid = (l + r) / 2;
		return mergeSort(a, l, mid) + mergeSort(a, mid, r) + merge(a, l, mid, r);
	}
	else return 0;
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, K; cin >> N >> K;
	vector<int> a(N + 1); rep(i, 1, N + 1) { cin >> a[i]; }
	a[0] = 0;
	rep(i, 1, N + 1)a[i] += a[i - 1];
	rep(i, 1, N + 1) {
		a[i] -= i*K;
	}
	cout << mergeSort(a, 0, N + 1) << endl;
	return 0;
}

Measured memory_bytes: 3528
#include<iostream>
#include<iomanip>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
 
using namespace std;
 
#define P(p) cout<<(p)<<endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define rrep(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.begin(), v.end(),greater<int>());
#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
#define C(i) cin>>i
#define C2(i,j) cin>>i>>j
#define C3(i,j,k) cin>>i>>j>>k
#define C4(i,j,k,m) cin>>i>>j>>k>>m
////////////////////////////////////////////////////////////

struct p{
	int f;
	int s;
	int t;
};

int dore( int p , vector<int> &a ){
	rep(i,0,a.size()){
		if( a[i] == 0 ){
			if( p == 0 ) p = 1;
			else if( p == 1 ) p = 0;
			else continue;
		}
		else if( a[i] == 1 ){
			if( p == 1 ) p = 2;
			else if( p == 2 ) p = 1;
			else continue;
		}
	}

	ret p;
}

int main(){
	int n;
	cin >> n;
	
	vector<int> mp(6);

	rep(i,0,n){
		int w;
		cin >> w;
		vector<int> a(w);
		rep(j,0,w) cin >> a[j];
		
		int g0 = dore(0,a);
		int g1 = dore(1,a);

		if( g0 == 0 && g1 == 1 )
			mp[0]++;
		else if( g0 == 1 && g1 == 0)
			mp[1]++;
		else if( g0 == 0 && g1 == 2)
			mp[2]++;
		else if( g0 == 1 && g1 == 2)
			mp[3]++;
		else if( g0 == 2 && g1 == 0)
			mp[4]++;
		else if( g0 == 2 && g1 == 1)
			mp[5]++;
	}

	if( mp[0] > 0 || mp[1] > 1 || mp[2] > 1 || mp[3] > 2 || mp[4] > 2 || mp[5] > 1 ){
		yes;
		ret 0;
	}
	
	vector<int> v;
	rep(i,1,6){
		rep(j,0,mp[i])
			v.push_back(i);
	}
	
	vsort(v);
	do{
		vector<int> ami={0,1,2};
		rep(i,0,v.size()){
			switch(v[i]){
				case 1:
					swap(ami[0],ami[1]);
					break;
				case 2:
					swap(ami[1],ami[2]);
					break;
				case 3:{
					vector<int> tmp{ami[2],ami[0],ami[1]};
					ami = tmp;
					break;}
				case 4:{
					vector<int> tmp{ami[1],ami[2],ami[0]};
					ami = tmp;
					break;}
				case 5:
					swap(ami[0],ami[2]);
					break;
				default:
					break;
			}
		}
		if(ami[0] == 0 && ami[1] == 1 ){
			yes;
			ret 0;
		}
		
	}while(next_permutation(v.begin(),v.end()));
	
	no;
	ret 0;
}


Measured memory_bytes: 3152
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
#define REP(var, a, b) for (int var = (a); var < (b); var++)
#define rep(var, n) for (int var = 0; var < (n); ++var)
#define ALL(c) (c).begin(), (c).end()
#define rALL(c) (c).rbegin(), (c).rend()
ll MOD = 1000000007;

void dfs(ll u, vvl& edges, vl& result, vl& add, vector<bool>& flag) {
  result[u] = add[u];
  flag[u] = true;
  for (auto& v : edges[u]) {
    // cout << u << "->" << v << endl;
    if (flag[v]) continue;
    add[v] += add[u];
    dfs(v, edges, result, add, flag);
  }
}

int main() {
  //
  ll n, q;
  cin >> n >> q;
  vvl edges(n);
  vl add(n, 0);
  vl result(n, 0);
  vl a(n - 1), b(n - 1);
  rep(i, n - 1) {
    cin >> a[i] >> b[i];
    a[i]--, b[i]--;
    edges[a[i]].push_back(b[i]);
    edges[b[i]].push_back(a[i]);
  }

  rep(i, q) {
    ll p, x;
    cin >> p >> x;
    p--;
    add[p] += x;
  }
  vector<bool> flag(n, false);
  dfs(0, edges, result, add, flag);
  rep(i, n) {
    cout << result[i];
    if (i < n - 1)
      cout << " ";
    else
      cout << endl;
  }
  return 0;
}


Measured memory_bytes: 32128
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<unordered_map>
#include<set>
#include<string>
#include<algorithm>
#include<math.h>
#include<numeric>
#include<iomanip>
#include<queue>
#include<functional>
#include<iso646.h>
#include<bitset>

using namespace std;

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

const ll INF = 1e16;
//const ll MOD = 1e9 + 7;
const ll MOD = 998244353;

ll gcd(ll n, ll m){
	if (n > m){
		ll l = n;
		n = m;
		m = l;
	}
	while (1){
		ll l = n;
		n = m%n;
		m = l;
		if (n == 0){
			break;
		}
	}
	return m;
}

int main(){
	ll N, M;
	cin >> N >> M;
	string S, T;
	cin >> S >> T;

	ll d = gcd(N, M);

	for (ll i = 0; i < d; i++){
		ll ds = N / d;
		ll dt = M / d;
		if (S[ds*i] != T[dt*i]){
			cout << -1 << endl;
			return 0;
		}
	}
	cout << N * (M / d) << endl;
	return 0;

}

Measured memory_bytes: 512
import sys
#from collections import defaultdict, deque, Counter
#import bisect
#import heapq
#import math
#from itertools import accumulate
#from itertools import permutations as perm
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as combr
#from fractions import gcd
#import numpy as np

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

#n = int(stdin.readline().rstrip())
#l = list(map(int, stdin.readline().rstrip().split()))

#numbers = [[int(c) for c in l.strip().split()] for l in sys.stdin]
#word = [stdin.readline().rstrip() for _ in range(n)]
#number = [[int(c) for c in stdin.readline().rstrip()] for _ in range(n)]
#zeros = [[0] * w for i in range(h)]


def main():
    R,G,B,N = map(int, stdin.readline().rstrip().split())
    ans = 0
    for r in range(N//R+1):
        for g in range((N-(r*R))//G + 1):
            b = (N - R*r - G*g) / B
            if b%1==0 and b>=0:
                ans += 1
    print(ans)

main()


Measured memory_bytes: 3064
#include<stdio.h>
main() {
	int i, n, m;
	for (i = 1;; i++) {
		scanf("%d %d", &n, &m);
		if (n == 0 && m == 0)break;
		if (n>m)printf("%d %d\n", m, n);
		else printf("%d %d\n", n, m);
	}
	return 0;
}


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

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

template<class T> inline T sqr(T x) {return x*x;}

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef long long ll;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const long long INF = 1000000007;

#define CLR(a) memset((a), 0 ,sizeof(a))

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

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; }

int main(void){
    ll H; cin >> H;
    ll ans = 0, i=0;
    while(H){
        ans += pow(2,i++);
        H >>= 1;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 384
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <ctime>
#include <cstring>
#include <functional>
#include <iostream>
#include <iomanip>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define fix(n)          cout<<fixed<<setprecision(n);
#define rep(i,n)        for (int i = 0; i < (n); ++i)
#define sort(a)         sort((a).begin(), (a).end());
#define uniq(a)         SORT(a);(a).erase(unique((a).begin(), (a).end()), (a).end());
#define reverse(a)      reverse((a).begin(), (a).end());
#define ctos(c)         string(1, (c))
#define out(d)          cout << (d);
#define outl(d)         std::cout<<(d)<<"\n";
#define Yes()           printf("Yes\n");
#define No()            printf("No\n");
#define YES()           printf("YES\n");
#define NO()            printf("NO\n");
#define ceil(x, y)      ((x + y - 1) / (y))
#define debug(x)        cerr << #x << ": " << (x) << '\n'
#define debug2(x, y)    cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << '\n'
#define debug3(x, y, z) cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << ", " << #z << ": " << (z) << '\n'
#define dbg(v)          for (size_t _ = 0; _ < v.size(); ++_){ cerr << #v << "[" << _ << "] : " << v[_] << '\n'; }

using namespace std;
using ll = long long;
using P = pair<ll,ll>;

const ll MOD = 1000000007; // 10^9 + 7

void solve() {
  int a, b, c; cin >> a >> b >> c;
  if (b-a == c-b){
    YES()
  } else {
    NO()
  }
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  srand((unsigned)time(NULL));
  fix(12)

  solve();
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <deque>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <bitset>

using namespace std;
using ll = long long;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int & v : a) {
        cin >> v;
    }
    ll x = a[0];
    ll sum = a[0];
    int start = 0;
    ll res = n;
    for (int i = 1; i < n; ++i) {
        x ^= a[i];
        sum += a[i];
        if (x != sum) {
            for (int j = start; j < i; ++j) {
                x ^= a[j];
                sum -= a[j];
                if (x == sum) {
                    start = j + 1;
                    break;
                }
            }
        }
        res += i - start;
    }
    cout << res << "\n";
    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <iomanip>
#include <string>
#include <stack>
#include <vector>
#include <complex>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <iterator>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <regex>
#include <limits>
#include <time.h>
#include <cstdint>
using namespace std;
using pii  = pair<int,int>;
using ll=long long;
using ld=long double;
#define pb push_back
#define mp make_pair
#define sc second
#define fr first
#define stpr setprecision
#define cYES cout<<"YES"<<endl
#define cNO cout<<"NO"<<endl
#define cYes cout<<"Yes"<<endl
#define cNo cout<<"No"<<endl
#define rep(i,n) for(ll i=0;i<(n);++i)
#define Rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,n) for(ll i=n-1;i>=0;i--)
#define rRep(i,a,b) for(ll i=a;i>=b;i--)
#define crep(i) for(char i='a';i<='z';++i)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define ALL(x) (x).begin(),(x).end()
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define endl '\n'
int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}
ll gcd(ll a,ll b){return (b == 0 ? a : gcd(b, a%b));}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
constexpr ll MOD=1000000007;
constexpr ll INF=1000000011;
constexpr ll MOD2=998244353;
constexpr ll LINF = 1001002003004005006ll;
constexpr ld EPS=10e-8;
template <class T, class U> inline bool chmax(T& lhs, const U& rhs) { if (lhs < rhs) { lhs = rhs; return 1; } return 0; }
template <class T, class U> inline bool chmin(T& lhs, const U& rhs) { if (lhs > rhs) { lhs = rhs; return 1; } return 0; }
template<typename T> istream& operator>>(istream& is,vector<T>& v){for(auto&& x:v)is >> x;return is;}
template<typename T,typename U> istream& operator>>(istream& is, pair<T,U>& p){ is >> p.first; is >> p.second; return is;}
template<typename T,typename U> ostream& operator>>(ostream& os, const pair<T,U>& p){ os << p.first << ' ' << p.second; return os;}
template<class T> ostream& operator<<(ostream& os, vector<T>& v){
  for(auto i=begin(v); i != end(v); ++i){
    if(i !=begin(v)) os << ' ';
    os << *i;
  }
  return os;
}

ll A[3007],dp[3007][3007][5];
ll cme;

ll modpow(ll b, ll e, ll m){  // bのe乗のmod m を返す
  if (e == 0) return 1;
  cme = modpow(b, e / 2, m);
  cme = (cme * cme) % m;
  if (e % 2 == 1) cme = (cme * b) % m;
  return cme;
}

int main(){
  ll N,S,ANS=0;
  cin >> N >> S;
  rep(i,N){
    cin >> A[i+1];
  }
  dp[0][0][0]=1;
  Rep(i,1,N+1){
    rep(j,S+1){
      dp[i][j][0]+=dp[i-1][j][0];
      dp[i][j][1]+=dp[i-1][j][1];
      if(j==0){
        dp[i][j][1]+=dp[i-1][j][0];
      }
      if(j>=A[i]){
        dp[i][j][0]+=dp[i-1][j-A[i]][0];
        dp[i][j][1]+=dp[i-1][j-A[i]][1];
        if(j==A[i]){
          dp[i][j][1]++;
        }
      }
      dp[i][j][0]%=MOD2;
      dp[i][j][1]%=MOD2;
      dp[i][j][2]=(dp[i][j][1]+dp[i-1][j][2])%MOD2;
    }
  }
  cout << dp[N][S][2] << endl;
}

Measured memory_bytes: 355824
#include  <bits/stdc++.h>
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
using namespace std;

const int limit=55;
const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};

bool dist[limit][limit][4],ndist[limit][limit][4];
bool can[limit][limit][4];

void move(int n,int c){
	rep(loop,n-1){
		rep(x,limit)rep(y,limit)rep(d,4){
			if(dist[x][y][d]==false) continue;
			if(can[x][y][d]==false) continue; 
			int nx=x+dx[d],ny=y+dy[d];
			if(can[nx][ny][d]) ndist[nx][ny][d]=true;
			if(can[nx][ny][(d+1)%4]) ndist[nx][ny][(d+1)%4]=true;
			if(can[nx][ny][(d+3)%4]) ndist[nx][ny][(d+3)%4]=true;
		}
		rep(x,limit)rep(y,limit)rep(d,4) dist[x][y][d]=ndist[x][y][d],ndist[x][y][d]=false;
	}
	rep(x,limit)rep(y,limit)rep(d,4){
		if(dist[x][y][d]==false) continue;
		if(can[x][y][d]==false) continue; 
		int nx=x+dx[d],ny=y+dy[d];
		if(d==c&&can[nx][ny][d]) ndist[nx][ny][d]=true;
		if( (d==c||(d+1)%4==c)&&can[nx][ny][(d+1)%4]) ndist[nx][ny][(d+1)%4]=true;
		if( (d==c||(d+3)%4==c)&&can[nx][ny][(d+3)%4]) ndist[nx][ny][(d+3)%4]=true;
	} 
	rep(x,limit)rep(y,limit)rep(d,4) dist[x][y][d]=ndist[x][y][d],ndist[x][y][d]=false;
}

int main(void){
	int n,cx,cy,t;
	cin >> n >> cx >> cy >> t;
	rep(d,4) dist[cx][cy][d]=true;
	rep(i,n){
		int sx,sy,gx,gy;
		cin >> sx >> sy >> gx >> gy;
		if(sy==gy) rep(x,min(sx,gx),max(sx,gx)) can[x][sy][0]=true,can[x+1][sy][2]=true;
		if(sx==gx) rep(y,min(sy,gy),max(sy,gy)) can[sx][y][1]=true,can[sx][y+1][3]=true;
	}
	rep(loop,t){
		int m; char c;
		cin >> m >> c;
		if(c=='E') move(m,0);
		if(c=='N') move(m,1);
		if(c=='W') move(m,2);
		if(c=='S') move(m,3);
	}
	rep(x,limit)rep(y,limit){
		bool ok=false;
		rep(d,4) if(dist[x][y][d]) ok=true;
		if(ok) cout << x << " " << y << endl;
	}
	return 0;
}

Measured memory_bytes: 3136
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#define debug(x)  cerr << #x << " = " << x << endl
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;

const int maxN = 5e2 + 5;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;

ll gcd(ll a, ll b) {return !b ? a : gcd(b, a % b);}
ll sq(ll x) {return (x * x) % MOD;}
ll modP(ll a, ll b) {return (!b ? 1 : (sq(modP(a, b / 2)) * (b % 2 ? a : 1)) % MOD);}

int a[maxN][maxN];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n; cin >> n;
	for (int i = 0; i < n - 1; i++){
		for (int j = i + 1; j < n; j++){
			cout << 1 + __builtin_ctz(i ^ j) << " ";
		}
		cout << "\n";
	}
	cout << flush;
	return 0;
}



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


int n;
int a[N];
int ans;
int main(){
    cin >> n;
    REP(i,n) cin >> a[i];
    int ok=0;
    while(ok==0){
        REP(i,n){
            if(a[i]%2==1)ok=1;
        }
        if(ok==0){
            ans++;
            REP(i,n)a[i]=a[i]/2;
        }
    }
    printf("%d",ans);
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
#include<vector>
#include<cmath>
#define int long long int
#define mod 1000000007
#define inf 20001
int function(char mat[101][101],int x1,int y1,int x2,int y2,int n,int m,bool visited[101][101])
{
	if(x1<0||x1>n||y1<0||y1>m)
	    return inf;
	if(x1==x2&&y1==y2)
	{
		return 0;
	}
	if(visited[x1][y1])
	    return inf;
	else
	{
		visited[x1][y1]=true;
		int answer=0;
		if(mat[x1][y1]=='1')
		  answer++;
	    int a=answer+function(mat,x1+1,y1,x2,y2,n,m,visited);
	    int b=answer+function(mat,x1-1,y1,x2,y2,n,m,visited);
	    int c=answer+function(mat,x1,y1+1,x2,y2,n,m,visited);
	    int d=answer+function(mat,x1,y1-1,x2,y2,n,m,visited);
	    return min(min(a,b),min(c,d));
	}
}
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    int a,b,c;
    cin>>a>>b>>c;
    int x,y;
    cin>>x>>y;
    if(2*c<a+b)
    {
		int answer=min(x,y)*2*c;
		int p=min(x,y);
		x-=p;
		y-=p;
		if(x!=0)
		{
			int u=a*x;
			int v=2*c*x;
			answer+=min(u,v);
		}
		else if(y!=0)
		{
			int u=b*y;
			int v=2*c*y;
			answer+=min(u,v);
		}
		cout<<answer<<endl;
	}
	else
	{
		int answer=a*x+b*y;
		cout<<answer<<endl;
	}
    
}


Measured memory_bytes: 256
//Coded by Abhijay Mitra
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <numeric>
#include <vector>
#include <iterator> 
#include <map>
#include <set>
#include <climits>
#include <queue>
#include <cmath>
#include <stack>
#include <cctype>
#include <bitset>
#include <bits/stdc++.h>
#define double long double
#define int long long int
#define ll int
#define ibs ios_base::sync_with_stdio(false)
#define cti cin.tie(0)
#define bp __builtin_popcount
#define pb push_back
#define res(v) v.resize(unique(v.begin(), v.end()) - v.begin());
#define cnt_res(v) std::distance(v.begin(),std::unique(v.begin(), v.end())); 
#define timer cerr << "Time elapsed : " << 1.0 * clock() / CLOCKS_PER_SEC << " sec \n";
using vi = std::vector<int>;
using vvi = std::vector<vi>;
using pii = std::pair<int,int>;
using vpii = std::vector<pii>;
using vvpii = std::vector<vpii>;
#define mp         make_pair
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define per(i,b,a) for (int i = b; i >= a; i--)
#define all(x)     x.begin(), x.end()
using namespace std;
const int N=3e2+10;
const double inf = /*0x3f3f3f3f*/1021+10;
// const ll M = 998244353 ; // Mulo
// const int M = 1e9+7 ; // Mulo
const double Pi = 3.14159265;
#define F first
#define S second
double dp[N][N][N],d[N][N][N];int n,A[N];
double f(int i,int j,int k){
  if(d[i][j][k]!=inf)return d[i][j][k];
  if((i||j||k)==0)return 0;
  d[i][j][k]=0;
  double num=(double)n/(i+j+k);
  //num is the number of ways to reach state i,j,k
  if(i!=0)d[i][j][k]+=i*(f(i-1,j,k)+num)/(i+j+k);
  if(j!=0)d[i][j][k]+=j*(f(i+1,j-1,k)+num)/(i+j+k);
  if(k!=0)d[i][j][k]+=k*(f(i,j+1,k-1)+num)/(i+j+k);
  return d[i][j][k];
}
int a,b,c;
void solve(){
  cin>>n;rep(i,1,n)cin>>A[i];
  rep(i,1,n){
    if(A[i]==1)a++;
    if(A[i]==2)b++;
    if(A[i]==3)c++;
  }
  dp[a][b][c]=1;
  per(k,n,0)
    per(j,n,0)
      per(i,n,0){
        d[i][j][k]=inf;
        // if((i==0 and j==0) or (j==0 and k==0) or (i==0 and k==0))continue;
        if(i!=0){dp[i-1][j][k]+=dp[i][j][k]*(double)i/(i+j+k);}
        if(j!=0){dp[i+1][j-1][k]+=dp[i][j][k]*(double)j/(i+j+k);}
        if(k!=0){dp[i][j+1][k-1]+=dp[i][j][k]*(double)k/(i+j+k);}
      }
  //dp[i][j][k] is the probability of reaching the i j k state
  cout<<setprecision(20)<<f(a,b,c);
}
int32_t main()
{
  // ibs;cti; 
  solve()
  /*,cout<<"\n"*/;
  // cout<<"\n";
  int xx=0;
  // int t;cin>>t;while(t--){/*xx++;cout<<"Case "<<xx<<":\n"*/;solve();cout<<"\n";}
  return 0;
}

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

int main(void){
    int x; cin >> x;
    int n500, n5, r = x; 
    n500 = x /500;
    r = x % 500;
    n5 = r /5;

    int happy = n500 *1000 + n5 * 5;
    cout << happy << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

using namespace std;

int main(){
	int a,b,c,count = 0;
	scanf("%d %d %d",&a,&b,&c);
	for(int i = a; i <= b; i++){
		if(c%i == 0) count++;
	}
	printf("%d\n",count);
}


Measured memory_bytes: 2728
import java.util.ArrayDeque;

public class Main {
	private static int h, w, n;
	private static boolean[] wall;
	private static int[] sx, sy;

	private static int[] dx = { 0, 1,  0, -1 };
	private static int[] dy = { 1, 0, -1,  0 };
	
	private static int getInt() throws Exception {
		int i = 0;
		while(true){
			int buf = System.in.read();
			if('0' > buf || buf > '9'){
				break;
			}
			i = i * 10 + buf - '0';
		}
		return i;
	}
	private static int search(int sx, int sy, int ex, int ey) {
		int sc = 0;
		boolean[] visited = new boolean[h*w];
		ArrayDeque<Integer> qx = new ArrayDeque<>();
		ArrayDeque<Integer> qy = new ArrayDeque<>();
		ArrayDeque<Integer> qc = new ArrayDeque<>();
		qx.offer(sx);
		qy.offer(sy);
		qc.offer(sc);
		while(true){
			sx = qx.pop();
			sy = qy.pop();
			sc = qc.pop() + 1;
			for(int i = 0; i < 4; i++){
				int nx = sx + dx[i];
				int ny = sy + dy[i];
				int p = nx + ny*w;
				if(0 <= nx && nx < w && 0 <= ny && ny < h && !wall[p] && !visited[p]){
					if(nx == ex && ey == ny) return sc;
					visited[p] = true;
					qx.offer(nx);
					qy.offer(ny);
					qc.offer(sc);
				}
			}
		}
		
	}
	public static void main(String[] args) throws Exception {
		h = getInt();
		w = getInt();
		n = getInt();
		wall = new boolean[h*w];
		sx = new int[10];
		sy = new int[10];
		for(int y = 0; y < h; y++){
			for(int x = 0; x < w; x++) {
				int buf = System.in.read();
				if(buf =='\n' || buf == '\r'){
					x--;
					continue;
				}
				wall[x + y*w] = buf == 'X';
				if(buf == 'S'){
					sx[0] = x;
					sy[0] = y;
				}
				if('1' <= buf && buf <= '9'){
					buf -= '0';
					sx[buf] = x;
					sy[buf] = y;
				}
			}
		}
		int a = 0;
		for(int i = 1; i <= n; i++) a += search(sx[i-1], sy[i-1], sx[i], sy[i]);
		System.out.println(a);
	}

}

Measured memory_bytes: 64068
using System;
using System.Linq;

class B
{
	static void Main()
	{
		Func<int[]> read = () => Console.ReadLine().Split().Select(int.Parse).ToArray();
		Console.ReadLine();
		var v = read();
		var c = read();
		Console.WriteLine(v.Zip(c, (x, y) => x - y).Where(x => x > 0).Sum());
	}
}


Measured memory_bytes: 13396
import math
import fractions
import copy
import numpy as np
def j(q):
    if q==1: print("Yes")
    elif q == 0:print("No")
    exit(0)
rem = pow(10,9)+7
"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def iprow():
    return [int(i) for i in input().split()]
def ips():
    return (int(i) for i in input().split())
def printrow(a):
    for i in a:
        print(i)
"""
#decomment when needed
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
"""
cv = "abcdefghijklmnopqrstuvwxyz"
convert = [cv[i] for i in range(26)]
s = input()
t = input()
a = [convert.index(s[i]) for i in range(len(s))]
b = [convert.index(t[i]) for i in range(len(t))]
c = [[] for i in range(26)]
d = [[] for i in range(26)]

for i in range(len(a)):
    c[a[i]].append(b[i])
for i in range(len(b)):
    d[b[i]].append(a[i])
for i in range(26):
    if len(set(c[i]))>1 or len(set(d[i]))>1:j(0)
j(1)

Measured memory_bytes: 21288
package main

import (
       "bufio"
       "fmt"
       "os"
       "strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
     sc.Scan()
     i, e := strconv.Atoi(sc.Text())
     if e != nil {
     	panic(e)
     }
     return i
}

func main() {
     sc.Split(bufio.ScanWords)
     n := nextInt()
     k := nextInt()

     a := n % k
     b := k - a

     if a > b {
     	fmt.Println(b)
     } else {
        fmt.Println(a)
     }
}     

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define all(V) V.begin(),V.end()
#define ll long long
#define MOD 1000000007

ll X[100], Y[100], H[100];

int main() {
	int N, x, y, h;
	cin >> N;
	for (int i = 0;i < N;i++) {
		cin >> X[i] >> Y[i] >> H[i];
	}
	for (int x = 0;x <= 100;x++) {
		for (int y = 0;y <= 100;y++) {
			ll lv = 0, rv = INT32_MAX, t, rh;
			while (lv + 1 != rv) {
				t = (lv + rv) / 2;
				bool jd = 0;
				for (int n = 0;n < N;n++) {
					rh = max(t - abs(x - X[n]) - abs(y - Y[n]), 0LL);
					if(rh > H[n]) {
						rv = t;
						jd = 1;
						break;
					}
					if (rh < H[n]) {
						lv = t;
						jd = 1;
						break;
					}
				}
				if (jd)
					continue;
				cout << x << " " << y << " " << t << endl;
				return 0;
			}
		}
	}
}

Measured memory_bytes: 384
#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

int n,s[110],dp[110],sum=0,ans=0;

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++){scanf("%d",&s[i]);sum+=s[i];}
    if(sum%10!=0)ans=sum;
    else
    {
        sort(s,s+n);
        for(int i=0;i<n;i++)
        {
            if(s[i]%10!=0)
            {
                ans=sum-s[i];
                break;
            }
        }
    }
    printf("%d",ans);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
unordered_map<int, vector<int>> children;
int scores[200001];

void visit(int p, int accum)
{
    //cout << "visiting " << p << ", accumulated " << accum << ", given " << scores[p] << endl;
    scores[p] += accum;
    accum = scores[p];
    for (auto it : children[p])
    {
        visit(it, accum);
    }
}

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

    for (int i = 0; i < n - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        children[a].push_back(b);
    }

    for (int i = 0; i < q; i++)
    {
        int p, x;
        cin >> p >> x;
        scores[p] += x;
    }

    visit(1, 0);

    for (int i = 1; i <= n; i++)
    {
        cout << scores[i] << " ";
    }
    cout << endl;
}

Measured memory_bytes: 30152
#include <bits/stdc++.h>
using namespace std;
int main()
{
	string s;
	cin >> s;
	int cnt  = 0;
	for(int i=0; i<s.size(); i++) cnt+= s[i] - '0';
	cout << (cnt % 9 == 0 ? "Yes" : "No");
	return 0;
}


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

#define pb push_back
#define fst first
#define snd second
#define fill(a,c) memset(&a, c, sizeof(a))
#define fore(i,x,y) for(ll i=x;i<y;i++)
#define FIN ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

int main() {FIN;
    
    int n,l;cin>>n>>l;
    string arr[n];
    fore(i,0,n){
        cin>>arr[i];
    }sort(arr,arr+n);
    string ans="";
    fore(i,0,n){
        ans+=arr[i];
    }cout<<ans<<"\n";
    return 0;
}



Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using System.Text;


class Program
{
    static void Main(string[] args)
    {
        // 入力
        //var s = Console.ReadLine();
        decimal n = decimal.Parse(Console.ReadLine());
        //int[] n = Console.ReadLine().Split().Select(int.Parse).ToArray();

        decimal m = 100;
        decimal ans = 0;
        while (m < n)
        {
            m = Math.Floor((decimal)1.01 * m);
            ans++;
        }

        // 出力
        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 27620
import sys
input = sys.stdin.readline


def main():
    N = int(input())
    S = input().strip()
    ans = 0
    for i in range(1000):
        s = "{:03}".format(i)
        a = S.find(s[0])
        b = S.find(s[1], a+1)
        c = S.find(s[2], b+1)
        if a >= 0 and b >= 0 and c >= 0 and (a < b < c):
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
int INF = 1e8;
 
P ans;
 
int n,m;
char t[105][10005];
 
int func(int a,int b){
  return max(a,b)-min(a,b);
}
 
int main(){
  while(scanf("%d %d",&n,&m)!=EOF){
    for(int i=0;i<m;i++){
      scanf("%s",t[i]);
    }
    int w=0,e=0;
    int W=0,E=0;
    for(int i=0;i<m;i++){
      for(int j=0;j<n;j++){
        if(t[i][j]=='W')W++;
        else E++;        
      }
    }
    
    ans=P(W,0);
    //cout<<W<<' '<<E<<endl;
    for(int i=0;i<n;i++){      
      for(int j=0;j<m;j++){
        if(t[j][i]=='W'){
          W--;
          w++;
        }else{
          E--;
          e++;
        }
      }
      //cout<<i+1<<' '<<e<<' '<<W<<endl;
      ans=min(ans,P(e+W,i+1));
    }
    cout<<ans.second<<' '<<ans.second+1<<endl;
  }
  return 0;
}

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

  int N,l,r;
  
  int b = 0;
  
  cin >> N;
  
  for(int i = 0; i < N; i++){
      
 
  
  cin >> l >> r;

  int a = 1;

  a += r - l;
  
  b += a;

    }

    cout << b << endl;

}

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

#define deb(x)        cerr << #x << " = " << x << "\n";
#define deb2(x, y)    cerr << #x << " = " << x << ", " << #y << " = " << y << "\n";
#define deb3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << "\n";

#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define f  first
#define s  second

#define sortall(x) sort(x.begin(), x.end());
#define sz(x) (ll)x.size()

typedef long long         ll  ;

typedef vector < ll >     vl  ;
typedef vector < int >    vi  ;

typedef pair < ll, ll >   pl  ;
typedef pair < int, int > pi  ;

typedef vector < pl >     vpl ;
typedef vector < pi >     vpi ;

void solve()
{
	ll n;
	cin >> n;
	if (n%1000 == 0)
      cout << 0;
  else cout << 1000- (n% 1000);

}

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

	//freopen ("in.txt", "r", stdin); freopen("err.txt", "w", stderr); //freopen ("out.txt", "w", stdout);

	ll tc = 1;
	//cin >> tc;

	while (tc--)
	{
		solve();
		cout << endl;
	}

	return 0;
}

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

int main()
{
	int cnt=0;
	int x;
	cin>>x;
	for(int i=1;i<=x;i+=2)
	{
		int res=0;
		for(int j=1;j<=i;j++)if(i%j==0)res++;
		if(res==8)cnt++;
	}
	cout<<cnt<<endl;
	return 0;
}

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

int main() {
  string s;
  cin >> s;
  if(s.at(2) == s.at(3) && s.at(4) == s.at(5)) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

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

int main()
{
	string s, t;
	cin >> s >> t;
	int n = s.size(), m = t.size();
	vector<vector<int>> next_s(n + 1, vector<int>(26, n)), next_t(m + 1, vector<int>(26, m));
	for (int i = n - 1; 0 <= i; i--)
	{
		for (int j = 0; j < 26; j++)
		{
			next_s[i][j] = next_s[i + 1][j];
		}
		next_s[i][s[i] - 'a'] = i;
	}
	for (int i = m - 1; 0 <= i; i--)
	{
		for (int j = 0; j < 26; j++)
		{
			next_t[i][j] = next_t[i + 1][j];
		}
		next_t[i][t[i] - 'a'] = i;
	}
	vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0)), word(n + 1, vector<int>(m + 1, -1));
	vector<vector<pair<int, int>>> pre(n + 1, vector<pair<int, int>>(m + 1, make_pair(-1, -1)));
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			for (int k = 0; k < 26; k++)
			{
				if (next_s[i - 1][k] + 1 <= n && next_t[j - 1][k] + 1 <= m)
				{
					if (dp[next_s[i - 1][k] + 1][next_t[j - 1][k] + 1] < dp[i - 1][j - 1] + 1)
					{
						dp[next_s[i - 1][k] + 1][next_t[j - 1][k] + 1] = dp[i - 1][j - 1] + 1;
						pre[next_s[i - 1][k] + 1][next_t[j - 1][k] + 1] = {i - 1, j - 1};
						word[next_s[i - 1][k] + 1][next_t[j - 1][k] + 1] = k;
					}
				}
			}
		}
	}
	pair<int, int> f(0, 0);
	for (int i = 0; i <= n; i++)
	{
		for (int j = 0; j <= m; j++)
		{
			if (dp[f.first][f.second] < dp[i][j])
			{
				f = {i, j};
			}
		}
	}
	if (dp[f.first][f.second] == 0)
	{
		cout << "" << endl;
		return 0;
	}
	string ans = "";
	for (; f != make_pair(0, 0); f = pre[f.first][f.second])
	{
		ans += char('a' + word[f.first][f.second]);
	}
	reverse(ans.begin(), ans.end());
	cout << ans << endl;
	return 0;
}


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

using namespace std;

int main(int argc, const char *argv[]) {
  int n, k;
  cin >> n >> k;
  if (n % k == 0) {
    cout << 0 << '\n';
  } else {
    cout << 1 << '\n';
  }
  return 0;
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
#include <iomanip>
#include <math.h>
//#include <unistd.h>
//#include <stdio.h>
#define rep(i,x) for(ll i = 0;i<x;i++)
#define all(a) (a).begin(),(a).end()
using ll = long long;
using ld = long double;
using namespace std;
using dou = double;
const ll inf = 2147483647;
const ll INF = 1LL << 60;
const ld pi = 3.14159265358;
const ll mod = 1000000007;
typedef pair<ll,ll> P;
using graph = vector<vector<ll>>;
template<class T> inline bool chmax(T& a, T b){if(a < b){a = b; return true;}return false;}
template<class T> inline bool chmin(T& a, T b){if(a > b){a = b; return true;}return false;}
ll gcd(ll a,ll b){
    if(a < b)swap(a,b);
    if(a % b == 0)return b;
    else return gcd(b,a%b);
}
//素数判定O(sqrt(N))
bool isp(ll n){
    bool res = true;
    if(n == 1)return false;
    else{
        for(ll i = 2;i * i <= n;i++){
            if(n % i == 0){
                res = false;
                break;
            }
        }
        return res;
    }
}

ll fac[510000], finv[510000], inv[510000];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < 510000; i++){
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = mod - inv[mod%i] * (mod / i) % mod;
        finv[i] = finv[i - 1] * inv[i] % mod;
    }
}

// 二項係数計算
ll nCk(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}
//nのm乗をMODで割ったあまりO(logN)
ll modpow(ll n,ll m,ll MOD){
    ll res = 1;
    while(m){
        if(m & 1)res = (res * n) % MOD;
        m >>= 1;
        n *= n;
        n %= MOD;
    }
    return res;
}

//printf("%.10f\n", N);
/*  vector<ll> vec = {1,2,5,6,8,9,10};
    cout << binary_search(all(vec),5) << endl; -> true*/
/*
    vector<ll> vec = {1,2,5,6,8,9,10};
    auto n = upper_bound(all(vec),4);
    cout << *n << endl; -> 5*/

//    cout << fixed << setprecision(15);

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll N,M,A;
    cin >> N >> M >> A;
    for(ll i = 1;i <= N * M;i++){
        if(i % N == 0 && i % M == A){
            cout << "YES" << endl;
            return 0;
        }
    }
    cout << "NO" << endl;
}

Measured memory_bytes: 3652
# PyPy なら通る
# DP(貰うDP)
N = int(input())
S = input()

dp = [[0] * (N + 1) for _ in range(N + 1)]
result = 0
for i in range(N - 1, -1, -1):
    for j in range(N - 1, -1, -1):
        if S[i] == S[j]:
            dp[i][j] = dp[i + 1][j + 1] + 1
            t = dp[i][j]
            if t > j - i:
                t = j - i
            if t > result:
                result = t
print(result)


Measured memory_bytes: 231688
#include <stdio.h>
int main() {
    long int N,K,Q;
    scanf("%ld%ld%ld",&N,&K,&Q);
    
    long int P[N];
    long int A[Q];
    
    for (int i = 0; i<=N; i++) {
        P[i] = 0;
    }
    
    for (int i = 1; i <= Q; i++) {
        scanf("%ld",&A[i]);
    }
    
    for (int i = 1; i<= Q; i++) {
                P[A[i]] = P[A[i]] + 1;
    }
    
    for (int i = 1;i<=N; i++) {
        if (P[i] + K - Q <= 0) {
            printf("No\n");
        }else{
            printf("Yes\n");
        }
    }
    
    return 0;
}

Measured memory_bytes: 2048
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define all(x) (x).begin(),(x).end()

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

typedef long long ll;

using namespace std;
struct ed{int a,b,c;};
using P=pair<int,int>;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n,m;
  cin>>n>>m;
  vector<unordered_map<int, int>>num(n);
  vector<ed>es(m);
  rep(i,m)
  {
    int a,b,c;
    cin>>a>>b>>c;
    a--;b--;c--;
    es[i]={a,b,c};
    num[a][c]++;
    num[b][c]++;
  }
  int cnt=0;
  rep(i,n)
  {
    int tn=cnt++;
    for(auto &p:num[i])p.second=cnt++;
    num[i][-1]=tn;
  }
  vector<int>dist(cnt+2,-1);
  vector<vector<P>>edge(cnt+2);
  rep(i,n)
  {
    int t=num[i][-1];
    for(auto p:num[i])
    {
      if(p.first==-1)continue;
      int tn=p.second;
      edge[t].push_back({1,tn});
      edge[tn].push_back({0,t});
    }
  }
  rep(i,m)
  {
    int to=num[es[i].a][es[i].c],from=num[es[i].b][es[i].c];
    edge[to].push_back({0,from});
    edge[from].push_back({0,to});
  }
  int start=num[0][-1],end=num[n-1][-1];
  priority_queue<P,vector<P>,greater<P>>q;
  q.push({0,start});
  while(!q.empty())
  {
    P tp=q.top();q.pop();
    if(dist[tp.second]!=-1)continue;
    dist[tp.second]=tp.first;
    for(P nn:edge[tp.second])
    {
      if(dist[nn.second]!=-1)continue;
      q.push({nn.first+tp.first,nn.second});
    }
  }
  cout<<dist[end]<<endl;



  return 0;

}


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

int main() {
	ll a,b,v,w,t;
	cin >> a >> v;
	cin >> b >> w;
	cin >> t;

	ll d = abs(a-b);
	ll u = v-w;

	bool ans = false;

	if (u>0) {
		if (u*t>=d) ans = true;
	}

	if (ans) cout << "YES" << endl;
	else cout << "NO" << endl;

	return 0;
}


Measured memory_bytes: 3548