akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <math.h>

int main(){
    int uni, amount;
    int sum_price=0, sum_amount=0, count=0;

    while(scanf("%d,%d", &uni, &amount) != EOF){
        sum_price += uni * amount;
        sum_amount += amount;
        count++;
    }
    printf("%d\n", sum_price);
    printf("%d\n", (int)ceil(sum_amount/(double)count));
    
    return 0;
}

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

int main(){
    int a,b;
    cin >> a >> b;
    if (a < b){
        cout << 'a' << ' ' << '<' << ' ' << 'b' << endl;
    }
    else if(a == b){
        cout << 'a' << ' ' << "==" << ' '<< 'b' << endl;
    }
    else{
        cout << 'a' << ' ' << '>' << ' ' << 'b' << endl;
    }
    return 0;
}


Measured memory_bytes: 3104
#include <bits/stdc++.h>
typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,a) FOR(i,0,a)
	
using namespace std;
const int MAX_N=1e5,MAX_LOG_K=39;
int N;
ll K,A[MAX_N];
int bit[MAX_LOG_K+1];

int main(){
	cin>>N>>K;
	REP(i,N)cin>>A[i];
	REP(i,N){
		REP(j,MAX_LOG_K+1){
			if ((A[i]>>j)&1){
				bit[j]++;
			}
		}
	}
	ll ans=0;
	FOR(i,-1,MAX_LOG_K+1){
		ll sm=0;
		if (i==-1 || ((K>>i)&1)){
			REP(j,MAX_LOG_K+1){
				if(j<i){
					sm+=max(bit[j],N-bit[j])*(1ll<<j);
				}else if (j==i){
					sm+=(bit[j])*(1ll<<j);
				}else{
					if ((K>>j)&1){
						sm+=(N-bit[j])*(1ll<<j);
					}else{
						sm+=bit[j]*(1ll<<j);
					}
				}
			}
		}
		ans=max(ans,sm);
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <cstdio>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
 
const int MAX_N = 300000;
bool MSprime[MAX_N+1];
 
void sieve()
{
  fill(MSprime, MSprime+MAX_N+1, false);
  MSprime[0] = MSprime[1] = false;
  FOR(i,2,MAX_N+1)
    if((i % 7 == 1) || (i % 7 == 6))
      MSprime[i] = true;
  FOR(i,2,MAX_N+1)
    if(MSprime[i])
      for(int j = i*2; j < MAX_N+1; j += i)
        MSprime[j] = false;
}
int main()
{
  sieve();
  while(1){
    int N;
    scanf("%d",&N);
    if(N == 1) break;
    printf("%d:",N);
    FOR(i,2,MAX_N+1)
      if(MSprime[i] && (N % i == 0))
        printf(" %d",i);
    putchar('\n');
  }
}

Measured memory_bytes: 1484
#include <stdio.h>

int main() {
  int N;
  scanf("%d\n", &N);
  int a[N];
  int ans = 0;
  for (int i = 0; i < N; i++) {
    scanf("%d", &a[i]);
    int s = 1;
    while ((a[i] >> s) << s == a[i]) {
      s++;
      ans++;
    }
  }
  printf("%d\n", ans);
  return 0;
}

Measured memory_bytes: 256
// AGC 29 A
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000007

int main(){
    string s; cin >> s;
    int len = s.length();
    ll c = 0, b = 0;
    bool fw = false;
    for(int i = len-1; i >= 0; i--){
        if(s[i] == 'B'){
            if(fw){
                c+= (len-1-b)-i;
            }
            b++; 
        }else if(s[i] == 'W'){
            fw = true;
        }
    }
    cout << c << endl;
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int H, W;
  cin >> H >> W;
  int c = 0;
  string SU, SS, SB;
  cin >> SS;
  
  for (int i = 0; i < H; i++) {
    
    if (i < H - 1) {
      cin >> SB;
    }
    
    for (int j = 0; j < W; j++) {
      if (SS.at(j) == '.') {
        
        if (i != 0 && j != 0) {
          if (SU.at(j-1) == '#') {
            c++;
          }
        }
        
        if (i != 0) {
          if (SU.at(j) == '#') {
            c++;
          }
        }
        
        if (i != 0 && j != W-1) {
          if (SU.at(j+1) == '#') {
            c++;
          }
        }
      
        if (j != W-1) {
          if (SS.at(j+1) == '#') {
            c++;
          }
        }
        
        if (i != H-1 && j != W-1) {
          if (SB.at(j+1) == '#') {
            c++;
          }
        }
        
        if (i != H-1) {
          if (SB.at(j) == '#') {
            c++;
          }
        }
        
        if (i != H-1 && j != 0) {
          if (SB.at(j-1) == '#') {
            c++;
          }
        }
        
        if (j != 0) {
          if (SS.at(j-1) == '#') {
            c++;
          }
        }
        
        cout << c;
        c = 0;
      }
      else {
        cout << '#';
      } 
    } 

    cout << endl;
    SU = SS;
    SS = SB;
    SB = "";
  }    
  
}

Measured memory_bytes: 3620
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;
using ll = long long int;

ll count(const vector<int>& vec) {
  vector<vector<vector<ll>>> dp(vec.size() + 1,
                                vector<vector<ll>>(2, vector<ll>(2, 0)));
  dp[0][0][0] = 1;

  // 桁 dp
  int cnt = 0;
  for (int i = 0; i < vec.size(); i++) {
    for (int d = 0; d < 10; d++) {
      for (int j = 0; j < 2; j++) {
        for (int l = 0; l < 2; l++) {
          // skip large number
          if (l == 0 && vec[i] < d) {
            continue;
          }
          int nj = (d == 4 || d == 9) ? 1 : j;
          int nl = (vec[i] > d) ? 1 : l;

          dp[i + 1][nj][nl] += dp[i][j][l];
        }
      }
    }
  }
  return dp[vec.size()][1][1] + dp[vec.size()][1][0];
}
int main() {
  ll H, W;
  cin >> H >> W;
  vector<vector<char>> mp(H, vector<char>(W));
  vector<bool> white_row(H);
  vector<bool> white_col(W);

  for (ll i = 0; i < H; i++) {
    for (ll j = 0; j < W; j++) {
      cin >> mp[i][j];
    }
  }

  for (ll i = 0; i < H; i++) {
    bool white = true;
    for (ll j = 0; j < W; j++) {
      if (mp[i][j] == '#') {
        white = false;
      }
    }
    white_row[i] = white;
  }

  for (ll j = 0; j < W; j++) {
    bool white = true;
    for (ll i = 0; i < H; i++) {
      if (mp[i][j] == '#') {
        white = false;
      }
    }
    white_col[j] = white;
  }

  for (ll i = 0; i < H; i++) {
    if (white_row[i]) {
      continue;
    }
    for (ll j = 0; j < W; j++) {
      if (white_col[j]) {
        continue;
      }
      cout << mp[i][j];
    }
    cout << endl;
  }
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
 
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/2
#define all(x) (x).begin(),(x).end()
#define debug(x) cerr<<#x<<": "<<x<<endl
#define debug_vec(v) cerr<<#v<<":";rep(i,v.size())cerr<<" "<<v[i];cerr<<endl
//----------------------------------------------------------------

int MOD = 998244353;
// int MOD = 1000000007;

//----------------------------------------------------------------
signed main(){
   
    int n;
	cin >> n;
	int x[10],y[10];
	rep(i,n){
		cin >> x[i] >> y[i];
	}
	vll p(n);
	rep(i,n)p[i] = i;

	double ans = 0;
	do {
        rep(i,n-1){
			ans += sqrt((x[p[i]]-x[p[i+1]])*(x[p[i]]-x[p[i+1]]) + (y[p[i]]-y[p[i+1]])*(y[p[i]]-y[p[i+1]]));
		}
    } while( next_permutation(p.begin(), p.end()) ); 

	rep(i,n)ans /= (i+1);
	printf("%.10lf\n",ans);

	return 0;
}

//----------------------------------------------------------------

// g++ -std=c++14 code1.cpp
// sudo pip3 install --upgrade online-judge-tools
// rm -r -f test;oj dl https://code-festival-2018-quala.contest.atcoder.jp/tasks/code_festival_2018_quala_c
// rm -r -f test;oj dl https://nikkei2019-2-qual.contest.atcoder.jp/tasks/nikkei2019_2_qual_b
// rm -r -f test;oj dl https://abc145.contest.atcoder.jp/tasks/abc145_b

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,N) for(int i=0;i<(N);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9;
typedef long long ll;
typedef pair<ll,int> P;
typedef set<int> S;
ll n,m;
int main(){
    cin >> n >> m;
    vector<ll> p(m),y(m);
    vector<pair<pair<ll,ll>,ll>> cities;
    rep(i,m){
        cin>>p[i]>>y[i];
        cities.push_back(make_pair(make_pair(y[i],p[i]),i));
    }
    sort(cities.begin(),cities.end());
    vector<ll> num(m),cnt(n+1);
    rep(i,cities.size()){
        ++cnt[cities[i].first.second];
        num[cities[i].second] = cnt[cities[i].first.second];
    }
    rep(i,m){
        cout<<setfill('0')<<right<<setw(6)<<p[i];
        cout<<setfill('0')<<right<<setw(6)<<num[i];
        cout<<endl;
    }
    return 0;
}

Measured memory_bytes: 7536
s = input().strip()
for i in range(len(s)-1):
    if s[i] == s[i+1]:
        print(i+1, i+2)
        break
    elif i < len(s)-2 and s[i] == s[i+2]:
        print(i+1, i+3)
        break
else:
    print(-1, -1)


Measured memory_bytes: 39408
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <math.h>
#include <cmath>
#include <vector>
#include <map>
#include <algorithm>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <cassert>
#include <random>
#include <deque>
#include <bitset>
#include <string>
#include <queue>
#include <complex>

//#define int long long

#define mp(a, b) make_pair(a, b)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

#define endl '\n'

using namespace std;
typedef long long ll;
typedef long double ld;

mt19937 mrand(random_device{}());

double PI = acos((double)-1);
const ld eps = 1e-7;
const ll inf0 = 1023 * 1024 * 1024;
const ll inf = inf0 * inf0;
//const ll mod = 1e9 + 9;
const ll mod = 998244353;

void solve();
void scan();

signed main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	cout << fixed; cout.precision(15);
	solve();
	return 0;
}

const int N = 2e3 + 7;

int dist[N][N];

vector<int> g[N];

void bfs(int v, int* d) {
	d[v] = 0;
	queue<int> f;
	f.push(v);
	while (!f.empty()) {
		int s = f.front();
		f.pop();
		for (int u : g[s]) {
			if (d[u] > d[s] + 1) {
				f.push(u);
				d[u] = d[s] + 1;
			}
		}
	}
}

void solve() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
			dist[i][j] = inf0;
	}
	int n; cin >> n;
	for (int i = 0; i < (n - 1); i++) {
		g[i].push_back(i + 1);
		g[i + 1].push_back(i);
	}
	int x, y; cin >> x >> y; x--; y--;
	g[x].push_back(y);
	g[y].push_back(x);
	for (int i = 0; i < n; i++)
		bfs(i, dist[i]);
	vector<int> ans(n);
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			ans[dist[i][j]]++;
		}
	}
	for (int i = 1; i < n; i++)
		cout << ans[i] << endl;
	return;
}

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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
string char_to_string(char val) {
  return string(1, val);
}
int char_to_int(char val) {
  return val - '0';
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template<class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

int vector_finder(std::vector<ll> vec, int number) {
  auto itr = std::find(vec.begin(), vec.end(), number);
  size_t index = std::distance( vec.begin(), itr );
  if (index != vec.size()) { // 発見できたとき
    return 1;
  }
  else { // 発見できなかったとき
    return 0;
  }
}

int main() {
  int N, M, X; cin >> N >> M >> X;
  vector<int> C(N);
  vector<vector<int>> A(N, vector<int>(M));
  REP(i, N) {
    cin >> C[i];
    REP(k, M) {
      cin >> A[i][k];
    }
  }
  ll ans = pow(10, 17);
  vector<int> tmp(M);
  for(int bit = 0; bit < (1 << N); ++bit) {
    ll sum = 0;
    REP(i, M) tmp[i] = 0;
    for(int i = 0; i < N; ++i) {
      if(bit & (1 << i)) {
        sum += C[i];
        REP(k, M) {
          tmp[k] += A[i][k];
        }
      }
    }
    REP(i, M) {
      if(tmp[i] < X) break;
      if(i == M - 1 && ans > sum) {
        ans = sum;
      }
    }
  }
  if(ans == pow(10, 17)) cout << -1 << endl;
  else cout << ans << endl;
}

Measured memory_bytes: 3568
#include <iostream>
using namespace std;
typedef unsigned long long u64;

int main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  int a[n];
  int cnt = 0;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    a[i]--;
    if (a[i] < i && a[a[i]]==i) cnt++;
  }
  cout << cnt << endl;
  return 0;
}


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

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

#define FOR(i, n, m) for (ll(i) = (m); (i) < (n); ++(i))
#define REP(i, n) FOR(i, n, 0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll)1e15;

int main()
{
    string s;
    cin >> s;
    int a = 0;
    REP(i, s.length())
    {
        if (s[i] == '1')
            a++;
    }
    cout << a << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod=998244353;
#define MP make_pair
#define PB push_back
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline ll read(){
	char ch=getchar();ll x=0,f=0;
	while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
	return f?-x:x;
}
string s;
map<string,int> f,g;
int G(string);
int F(string s){
	if(f.count(s)) return f[s];
	int n=s.size(),ans=G(s);
	FOR(i,1,n-1) ans=(ans+1ll*F(s.substr(0,i))*G(s.substr(i,n)))%mod;
	return f[s]=ans;
}
int G(string s){
	if(g.count(s)) return g[s];
	int n=s.size();
	if(n==1) return s[0]-'0'+1;
	int ans=0;
	FOR(i,1,n-1) if(n%i==0){
		string t;
		FOR(j,0,i-1){
			bool flag=true;
			for(int k=j;k<n;k+=i) flag&=s[k]-'0';
			t+=flag+'0';
		}
		ans=(ans+F(t))%mod;
	}
	return g[s]=ans;
}
int main(){
	cin>>s;
	cout<<F(s)<<endl;
}

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

using namespace std;

int n, m;
vector <int> a;

int main(){
	scanf("%d%d", &n, &m);
	
	int cnt = 0;
	
	for(int i = 0; i < m; i++){
		int x, y;
		scanf("%d%d", &x, &y);
		
		if(x >= n) cnt++;
		else
		a.push_back(n - x);
	}
	
	if(cnt >= m - 1)
	return 0 * printf("0\n");
	
	sort(a.begin(), a.end());
	
	int res = 0;
	int diff = m - 1 - cnt;
	
	for(int i = 0; i < diff; i++)
	res += a[i];
	
	printf("%d\n", res);
}



Measured memory_bytes: 3272
#include <iostream>
#include <string>
#include <algorithm> 
#include <cstdlib>
#include <map>
#include <queue>
#include <vector>
#include <utility>
#include <climits>
#include <numeric>
#define ll long long
#define INF INT_MAX 
using namespace std;
int main(){
    ll n;
    cin >> n;
    ll count=1;
    ll ans[100000];
    for(int i=0;i<100000;i++){
        ans[i] = 0;
    }
    ans[n]++;
    while(1){
        if(n%2==0){
            n = n/2;
        }else{
            n = n*3+1;
        }
        ans[n]++;
        count++;
        if(ans[n]>=2){
            cout << count << endl;
            return 0;
        }
    }
}
  

Measured memory_bytes: 1024
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) {
		FastScanner sc = new FastScanner(System.in);
		long a = sc.nextLong(), b = sc.nextLong(), n = sc.nextLong();
		long x = Math.min(b-1, n);
		System.out.println((a*x)/b - a*(x/b));
	}

	static class FastScanner {
		private BufferedReader reader = null;
	    private StringTokenizer tokenizer = null;
	    public FastScanner(InputStream in) {
	        reader = new BufferedReader(new InputStreamReader(in));
	        tokenizer = null;
	    }

	    public String next() {
	        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
	            try {
	                tokenizer = new StringTokenizer(reader.readLine());
	            } catch (IOException e) {
	                throw new RuntimeException(e);
	            }
	        }
	        return tokenizer.nextToken();
	    }

	    public String nextLine() {
	        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
	            try {
	                return reader.readLine();
	            } catch (IOException e) {
	                throw new RuntimeException(e);
	            }
	        }

	        return tokenizer.nextToken("\n");
	    }

	    public long nextLong() {
	        return Long.parseLong(next());
	    }

	    public int nextInt() {
	        return Integer.parseInt(next());
	    }

	    public double nextDouble() {
	         return Double.parseDouble(next());
	     }

	    public int[] nextIntArray(int n) {
	        int[] a = new int[n];
	        for (int i = 0; i < n; i++)
	            a[i] = nextInt();
	        return a;
	    }

	    public long[] nextLongArray(int n) {
	        long[] a = new long[n];
	        for (int i = 0; i < n; i++)
	            a[i] = nextLong();
	        return a;
	    }
	}
}


Measured memory_bytes: 32612
n=int(input())
l=[0]+list(map(int,input().split()))+[0]
s=sum(abs(l[i+1]-l[i]) for i in range(n+1))
for i in range(n):
  a,b,c=l[i:i+3]
  print(s-min(abs(b-c),abs(b-a))*2*(max(a,c)<b or min(a,c)>b))

Measured memory_bytes: 14048
n, k = map(int, input().split())
a = list(map(int, input().split()))

dp = [[None] * (k + 1) for _ in range(2)]
# def dfs(at=k, taro=True):
#     if dp[taro][at]:
#         return dp[taro][at]
#
#     if at == 0:
#         r = True ^ taro # taro lose -> False
#         dp[taro][at] = r
#         return r
#
#     results = []
#     for i in range(n):
#         if at >= a[i]:
#             results.append(dfs(at - a[i], not taro))
#
#     if not results:
#         r = True ^ taro
#         dp[taro][at] = r
#         return r
#     r = (any if taro else all)(results)
#     dp[taro][at] = r
#     return r

for at in range(k + 1):
    for taro in range(2):
        if at == 0:
            dp[taro][at] = not taro
            continue
        results = []
        for i in range(n):
            if at >= a[i]:
                results.append(dp[not taro][at - a[i]])

        if not results:
            dp[taro][at] = not taro
            continue
        dp[taro][at] = (any if taro else all)(results)
print('First' if dp[True][k] else 'Second')


Measured memory_bytes: 46556
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;

typedef long long int ll;

int n;
ll d[512][512];
int main(void){
	cin >> n;
	for(int i=0;i<n;i++)for(int j=0;j<n;j++) cin >> d[i][j];

	ll sum = 0;
	for(int i=0;i<n;i++)for(int j=i;j<n;j++){
		ll mini = LLONG_MAX;
		for(int k=0;k<n;k++){
			if (i==k || j==k) continue;
			mini = min(mini, d[i][k]+d[k][j]);
		}
		if (mini < d[i][j]){
				cout << -1 << endl; return 0;
		}else if (mini > d[i][j]){
			sum += d[i][j];
		}
	}
	cout << sum << endl;



	return 0;
}


Measured memory_bytes: 1408
n=int(input())
a=list(map(int, input().split()))
b=list(map(int, input().split()))
br=0
for i in range(len(b)):
    x=min(a[i],b[i])
    a[i]-=x
    b[i]-=x
    br+=x
    x=min(a[i+1],b[i])
    a[i+1]-=x
    b[i]-=x
    br+=x
print(br)


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

int main(){
    int n;
    cin >> n;
    
    int i;
    cout << " ";
    for(i = 1; i < n + 1; i++){
        if(i % 3 == 0){
            if(i == n || i == n - 1 || i == n - 2){
                cout << i;
            }
            else{
            cout << i << " ";
            }
        }
        else if(i % 10 == 3){
            if(i == n || i == n - 1 || i == n - 2){
                cout << i;
            }
            else{
            cout << i << " ";
            }
        }
        else if((i / 10) % 10 == 3){
            if(i == n || i == n - 1 || i == n - 2){
                cout << i;
            }
            else{
            cout << i << " ";
            }
        }
        else if((i / 100) % 10 == 3){
            if(i == n || i == n - 1 || i == n - 2){
                cout << i;
            }
            else{
            cout << i << " ";
            }
        }
        else if(i / 1000 == 3){
            if(i == n || i == n - 1 || i == n - 2){
                cout << i;
            }
            else{
            cout << i << " ";
            }
        }
    }
    cout << endl;
}


Measured memory_bytes: 3096
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <sstream>
#include <unordered_map>
#include <vector>


#define INF 4000000000000000000LL
#define MOD 1000000007
#define ALL(x) std::begin(x), std::end(x)


int main(int argc, char** argv)
{
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(0);

  std::cout << std::fixed << std::setprecision(6);
  std::cerr << std::fixed << std::setprecision(6);

  int N;

  std::cin >> N;

  std::cout << (1000 - N % 1000) % 1000 << std::endl;

  return 0;
}


Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
template <class T> inline bool chmin(T &a, T b) {if (a > b){a = b;return true;}return false;}
template <class T> inline bool chmax(T &a, T b) {if (a < b){a = b;return true;}return false;}


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


int main(){
    ll a, b, c, d; cin >> a >> b >> c >> d;
    ll cnt = b-a+1;
    ll nonc = (b-b/c) - ((a-1)-(a-1)/c);
    ll nond = (b-b/d) - ((a-1)-(a-1)/d);
    ll gg =lcm(c,d);
    ll noncd = (b-b/gg) - ((a-1)-(a-1)/gg);

    cout << nonc+nond-noncd << endl;
}

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

using namespace std;

#define ll long long

struct Gem {
	int a, b;
};

bool cmp(Gem x, Gem y) {
	return x.a - x.b > y.a - y.b;
}


void solve() {

	int n;
	cin >> n;
	Gem arr[n];
	for(int i = 0; i < n; i++) {
		cin >> arr[i].a;
	}
	for(int i = 0; i < n; i++) {
		cin >> arr[i].b;
	}
	sort(arr, arr + n, cmp);
	ll total = 0;
	for(int i = 0; i < n; i++) {
		if(arr[i].a - arr[i].b < 0) {
			break;
		}
		else {
			total += arr[i].a - arr[i].b;
		}
	}
	cout << total;

	




	
}

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	solve();

	return 0;
}

Measured memory_bytes: 3556
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx")
#include <bits/stdc++.h>

namespace {
    template<int n, typename T>
    void mult(const T */*__restrict*/ a, const T */*__restrict*/ b, T */*__restrict*/ res) {
        if (n <= 64) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    res[i + j] += a[i] * b[j];
                }
            }
        } else {
            const int mid = n / 2;
            alignas(64) T btmp[n], E[n] = {};
            auto atmp = btmp + mid;
            for (int i = 0; i < mid; i++) {
                atmp[i] = a[i] + a[i + mid];
                btmp[i] = b[i] + b[i + mid];
            }
            mult<mid>(atmp, btmp, E);
            mult<mid>(a + 0, b + 0, res);
            mult<mid>(a + mid, b + mid, res + n);
            for (int i = 0; i < mid; i++) {
                const auto tmp = res[i + mid];
                res[i + mid] += E[i] - res[i] - res[i + 2 * mid];
                res[i + 2 * mid] += E[i + mid] - tmp - res[i + 3 * mid];
            }
        }
    }
}

using ll = long long;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);
    const int NMAX = (1 << 11)*49;
    alignas(64) static ll a[NMAX], b[NMAX * 2];
    int n; ll k; std::cin >> n >> k;
    for (int i = 0, val; i < n; i++) {
        std::cin >> val;
        a[val]++;
    }
    mult<NMAX>(a,a,b);
    ll answ(0);
    for (int i = 2 * NMAX - 1; k > 0 && i >= 0; i--) {
        answ += std::min(k, b[i]) * i;
        k -= b[i];
    }
    std::cout << answ << std::endl;
    return 0;
}


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

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define each(i, mp) for (auto &i : mp)

int main()
{
  string s;
  cin >> s;
  int q;
  cin >> q;
  string t;
  rep(qi, q)
  {
    int ty;
    cin >> ty;
    if (ty == 1)
    {
      swap(s, t);
    }
    else
    {
      int f;
      char c;
      cin >> f >> c;
      if (f == 1)
      {
        t += c;
      }
      else
      {
        s += c;
      }
    }
  }
  reverse(t.begin(), t.end());
  t += s;
  cout << t << endl;
  return 0;
}


Measured memory_bytes: 1128
N, M = map(int, input().split())
A = list(map(int, input().split()))

A.sort(reverse=True)
U = A[0] * 2

# cgs[i] は パワーがi以上のゲストの数
cgs = [0] * (U + 1)
for a in A:
    cgs[a] += 1
for i in range(U, 0, -1):
    cgs[i - 1] += cgs[i]


def is_ok(n):
    m = 0
    for a in A:
        m += cgs[max(n - a, 0)]
    return m >= M


ok = A[-1] * 2
ng = U + 1
while ng - ok > 1:
    m = (ok + ng) // 2
    if is_ok(m):
        ok = m
    else:
        ng = m

# cps[i] は A[0]～A[i] の累積和
cps = A[:]
for i in range(1, N):
    cps[i] += cps[i - 1]

result = 0
for a in A:
    t = cgs[max(ok - a, 0)]
    if t != 0:
        result += a * t + cps[t - 1]
        M -= t
result += ok * M
print(result)


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

#ifndef __TOPCYBERFLOWER
#define debug(...) 0
#else
#define debug(...) cout << " [-] ", _dbg(#__VA_ARGS__, __VA_ARGS__)
template<class TH> void _dbg(const char *sdbg, TH h){ cout << sdbg << '=' << h << endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
    while(*sdbg != ',') cout << *sdbg++;
    cout << '=' << (h) << ','; 
    _dbg(sdbg+1, a...);
}
#endif

#define TYPEMAX(type)   numeric_limits<type>::max()
#define TYPEMIN(type)   numeric_limits<type>::min()
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
int main(void){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    string s; cin>>s;
    if(s.compare("AAA")==0 || s.compare("BBB")==0) cout<<"No";
    else cout<<"Yes";
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int s[80000],m[1000000],i,j,n=0;
int main() {
	for (i=2; i<1000000 ; i++) {
		if (m[i]==0) {
			s[n++]=i;
			for (j=i; j<1000000; j+=i) m[j]=1;
		}
	}
	while(cin >> i) {
		for (j=0;s[j]<=i && j<n;j++) ;
		cout << j << endl;
	}
return 0;
}

Measured memory_bytes: 5372
/*

結果:
*/
#define _USE_MATH_DEFINES
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>  
#include <stdbool.h>   
#define inf (INT_MAX-1)
#define INF 9223372036854775807
#define PI 3.14159265358979323846;
#define EPS 1e-10
#define sq(n) ((n)*(n))
#define rep(i,n) for(i=0;i<n;i++)
#define rev(i,n) for(i=n-1;i>=0;i--)
/*
#define sort(a,n) qsort(a,n,sizeof(TYPE),cmp)
#define sort_r(a,n) qsort(a,n,sizeof(TYPE),cmp_r)
*/
#define chsort(s,n) qsort(s,n,sizeof(char),cmp)
#define chsort_r(s,n) qsort(s,n,sizeof(char),char_cmp_r)
#define TYPE long long
#define ll long long
#define MEMSET(a) memset(a,0,sizeof(a))
#define MEMSET_U(a) memset(a,-1,sizeof(a))
const int mod = (int)1e09 + 7;

//#define DEBUG1
//#define DEBUG2
//#define DEBUGF
#define DUMMY

int in(void) { int i; scanf("%d", &i); return i; }
long long llin(void) { long long i; scanf("%lld", &i); return i; }
double din(void) { double i; scanf("%lf", &i); return i; }
void chin(char s[]) { scanf("%s", s); }

void print(int a) { printf("%d\n", a); }
void llprint(long long a) { printf("%lld\n", a); }
void dprint(double a) { printf("%.10f\n", a); }
void print2(int a, int b) { printf("%d %d\n", a, b); }
int Max(int a, int b) { if (a>b) { return a; }return b; }
int Min(int a, int b) { if (a<b) { return a; }return b; }
long long llmax(long long a, long long b) { return a > b ? a : b; }
long long llmin(long long a, long long b) { return a < b ? a : b; }
double dmax(double a, double b) { return a > b ? a : b; }
double dmin(double a, double b) { return a < b ? a : b; }
//long long llmax(long long a, long long b) { return a > b ? a : b; }
//long long llmin(long long a, long long b) { return a < b ? a : b; }
//double dmax(double a, double b) { return a > b ? a : b; }
int cmp(const void *a, const void *b) { return *(TYPE *)a - *(TYPE *)b; }
int cmp_r(const void *a, const void *b) { return *(TYPE *)b - *(TYPE *)a; }
int char_cmp(const void *a, const void *b) { return strcmp((char *)a, (char *)b); }
int char_cmp_r(const void *a, const void *b) { return strcmp((char *)b, (char *)a); }
void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }




int main() {
	int A, B, C, D;
	scanf("%d%d%d%d", &A, &B, &C, &D);

	int a[102] = { 0 };
	int b[102] = { 0 };
	for (int i = A; i < B; i++) {
		a[i]++;
	}
	for (int i = C; i < D; i++) {
		b[i]++;
	}


	int tmp = 0;
	for (int i = 0; i < 101; i++) {
		if (a[i] == 1 && b[i] == 1) {
			tmp++;
		}
	}

	int ans = 0;
	ans = tmp;

	printf("%d\n", ans);

#ifdef DEBUGF
	getch();
#endif
	return 0;
}

Measured memory_bytes: 128
import std.stdio;
import std.algorithm;
import std.string;
import std.conv;
import std.math;

void main(){
    while(true){
	auto s = readln();
	if(stdin.eof()) break;
	s = chomp(s);
	if(s=="")break;
	string s1,s2;
	s1 = s;
	s2 = s;
	while(s1.length > 1){
	    s2 = "";
	    for(int i=0;i<s1.length-1;i++){
		s2 ~= to!char( '0' + (to!int(s1[i]-'0') + to!int(s1[i+1]-'0'))%10);
	    }
	    swap(s1,s2);
	}
	writeln(s1);
    }
}

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

using namespace std;

int main()
{
	string s;
	cin >> s;

	if (s == "A") {
		cout << "T" << endl;
	}
	else if (s == "T") {
		cout << "A" << endl;
	}
	else if (s == "C") {
		cout << "G" << endl;
	}
	else {
		cout << "C" << endl;
	}
}

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

int selection_sort(int A[], int n);
void trace(int A[], int n);

int main(int argc, char *argv[])
{
	int A[100];
	int n, sn;
	cin >> n;
	
	for (int i = 0; i < n; i++)
	{
		cin >> A[i];
	}
	
	sn = selection_sort(A, n);
	trace(A, n);
	cout << sn << endl;
	return 0;
}


int selection_sort(int A[], int n)
{
	int sw = 0;
	for (int i = 0; i < n; i++)
	{
		int min = i;
		for (int j = i+1; j < n; j++)
		{
			if (A[j] < A[min])
				min = j;
		}
		if (min != i)
		{
	    	swap(A[i], A[min]);
    		sw++;		    
		}

	} 
	return sw;
} 

void trace(int A[], int n)
{
	for (int i = 0; i < n; i++)
	{
		if (i) cout << ' ';
		cout << A[i]; 
	}
	cout << endl;
}


Measured memory_bytes: 3092
package main

import (
	"fmt"
)

func main() {

	var N int
	fmt.Scanf("%d", &N)

	V := make([]int, N)
	C := make([]int, N)
	for i := 0; i < N; i++ {
		fmt.Scanf("%d", &V[i])
	}

	for i := 0; i < N; i++ {
		fmt.Scanf("%d", &C[i])
	}

	var max int = 0
	for i := 0; i < N; i++ {
		if V[i] > C[i] {
			max += V[i] - C[i]
		}

	}
	fmt.Println(max)
}


Measured memory_bytes: 1836
n, t = map(int, input().split())
a = list(map(int, input().split()))

ans = 0
same = 0
mn = 1100000000
dif = 0
for x in a:
  mn = min(mn, x)
  if dif == x - mn:
    ans += 1
  if dif < x - mn:
    dif = x - mn
    ans = 1
  
print(ans)

Measured memory_bytes: 15020
(n,m)=map(int,input().split())
a=input().split()
a=list(map(int,a))
l=[]
k=0
a=sorted(a)
for i in range(m-1):
    d=abs(a[i]-a[i+1])
    k=k+d
    l.append(d)
# k=k-d
c=n-k
l.append(c)
l=sorted(l)
l1=sum(l)
print(l1-l[-1])

Measured memory_bytes: 26420
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)        for(int i=0; i<(int)(n); ++i)
//解説AC
int main(){
    int n,m;
    cin>>n>>m;
    vector<int>suicchi(n);
    rep(i,m){
        int k;
        cin>>k;
        rep(j,k){
            int s;
            cin>>s;
            s--;
            suicchi[s] |= 1<<i;
        }
    }
    int p=0;
    rep(i,m){
        int x;
        cin>>x;
        p |= x<<i;
    }
    int count = 0;
    for (int bits = 0; bits < (1 << (int)n); bits++) {  
        int t = 0;
        for (int i = 0; i < (int)n; i++) {
            if (bits>>i & 1) {  // i番目のbitが立っていれば加算する
                t^=suicchi[i];
            }
        }
        if(t==p)count++;
    }
    cout<<count<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define range(i, a, b) for(auto i = (a); i < (b); i++)
#define rep(i, a) range(i, 0, a)
using namespace std;
const int INF = sizeof(int) == sizeof(long long) ? LONG_LONG_MAX : INT_MAX;
const int MOD = 1000000007;
const long double EPS = 1e-8;

signed main() {
	char c[3][3];
	rep (i, 3) rep (j, 3) {
		cin >> c[i][j];
		if (i == j) cout << c[i][j];
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;
#define FOR(i,a,n) for(ll i=(ll)a;i<(ll)n;i++)
#define RFOR(i,a,n) for(ll i=(ll)n-1;i >= (ll)a;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,0,n)
#define ALL(v) v.begin(), v.end()
#define bra(first,second) '(' << first << ',' << second << ')'
//constexpr ll MOD = 1000000007;
constexpr ll MOD = 998244353;
ll INF = 6001001001001001001;
long double EPS = 1e-11;
long double PI = 3.141592653589793238;
template<typename T>
void remove(std::vector<T>& vector, unsigned int index){
    vector.erase(vector.begin() + index);
}

using Graph = vector<vector<ll>>;

ll N;

bool F(char a,char b){
    return (a == b || a == '?' || b == '?');
}

bool AB[100000];
bool AC[100000];
bool BC[100000];

int main(){
   string A,B,C;
   cin >> A >> B >> C;
   ll a = A.size(),b = B.size(),c = C.size();
   rep(i,a) rep(j,b) if(!F(A[i],B[j])) AB[50000+i-j] = true; 
   rep(i,a) rep(j,c) if(!F(A[i],C[j])) AC[50000+i-j] = true; 
   rep(i,b) rep(j,c) if(!F(B[i],C[j])) BC[50000+i-j] = true;
   ll ans = INF;
   FOR(i,-4000,4000) FOR(j,-4000,4000){
       if(!AB[50000+i] && !AC[50000+j] && !BC[50000+j-i]){
           ans = min(ans,max(b+i,max(c+j,a)) + max(0LL,max(-i,-j)));
       }
   }
   cout << ans << endl;
}

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

int main() {
    ll n,k;cin>>n>>k;
    ll ans=k;
    rep(i,n-1)ans*=k-1;
    cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3616
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <iostream>
#include <fstream>
#include <numeric>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <cmath>
#include <set>
#include <map>
#include <functional>
#include <bitset>
#include <iomanip>
#include <stack>
#include <list>
using namespace std;
#define ll           long long
#define all(v)       (v).begin() , (v).end()
#define vi           vector <ll>
#define vii          vector <pair<ll,ll>>
#define ii           pair<ll,ll>
#define sz(v)	     ((int)((v).size()))
#define lp(i,a,b)    for(int i=a;i<b;i++)
#define pb           push_back
#define pf           push_front
#define F            first
#define S            second
#define endl         "\n"
#define IOS          ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const double PI = 3.14159265358979323846;
const ll inf=2e9,MOD=1e9+7 ,MAX=1e5+2;

vector<int>adj[MAX];
int n,dp[MAX][2];
int sol(int node,bool prev,int p){
    if(sz(adj[node])<2&&node!=1)
        return 1;
    int &ret=dp[node][prev];
    if(~ret)
        return ret;
    ret=1;
    for(auto i:adj[node]){
        if(i==p)
            continue;
        int x=sol(i,0,node);
        if(!prev)
            x+=sol(i,1,node),x%=MOD;
        ret=((ret%MOD)*(x%MOD))%MOD;
    }
    return ret;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    IOS;
    cin>>n;
    lp(i,0,n-1){
        int a,b;
        cin>>a>>b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    memset(dp,-1,sizeof(dp));
    cout<<(sol(1,0,0)+sol(1,1,0))%MOD;
}


Measured memory_bytes: 18168
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        char[] S = sc.next().toCharArray();
        char[] T = sc.next().toCharArray();
        char[] ans = new char[2 * N];

        int pos = 0;
        for (int i = 0; i < N; i++) {
            ans[pos] = S[i];
            pos++;
            ans[pos] = T[i];
            pos++;
        }

        System.out.println(ans);
    }
}


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

using namespace std;

struct UnionFind
{
  vector< int > data;

  UnionFind(int sz)
  {
    data.assign(sz, -1);
  }

  bool unite(int x, int y)
  {
    x = find(x), y = find(y);
    if(x == y) return (false);
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return (true);
  }

  int find(int k)
  {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }

  int size(int k)
  {
    return (-data[find(k)]);
  }
};

struct LowLink
{
  UnionFind uf;
  vector< vector< int > > g;
  vector< int > used, ord, low, parent;

  LowLink(size_t v) : g(v), used(v, 0), ord(v), low(v), uf(v), parent(v, -1) {}

  virtual void add_edge(int x, int y)
  {
    g[x].push_back(y);
    g[y].push_back(x);
  }

  void dfs(int idx, int &k, int par = -1)
  {
    used[idx] = true;
    ord[idx] = k++;
    low[idx] = ord[idx];

    for(auto &to : g[idx]) {
      if(!used[to]) {
        dfs(to, k, idx);
        low[idx] = min(low[idx], low[to]);
        parent[to] = idx;
        if(ord[idx] >= low[to]) uf.unite(idx, to);
      } else if(to != par) {
        low[idx] = min(low[idx], ord[to]);
      }
    }
  }

  void dfs()
  {
    int k = 0;
    dfs(0, k);
  }
};

struct ArticulationPoints : LowLink
{
  ArticulationPoints(size_t v) : LowLink(v) {}

  vector< int > build()
  {
    LowLink::dfs();
    vector< int > vs;
    int sum = 0;
    for(int i = g.size() - 1; i >= 1; i--) {
      if(parent[i] == 0) ++sum;
      else if(ord[parent[i]] <= low[i]) vs.push_back(parent[i]);
    }
    if(sum > 1)vs.push_back(0);
    sort(begin(vs), end(vs));
    vs.erase(unique(begin(vs), end(vs)), end(vs));
    return (vs);
  }
};

struct BiConnectedComponents : LowLink
{
  vector< pair< int, int > > edges;
  vector< int > comp;

  BiConnectedComponents(size_t v) : LowLink(v), comp(v) {}

  void add_edge(int x, int y)
  {
    LowLink::add_edge(x, y);
    edges.push_back(minmax(x, y));
  }

  int operator[](int k)
  {
    return (comp[k]);
  }

  vector< pair< int, int > > build(vector< vector< int > > &t)
  {
    LowLink::dfs();
    int ptr = 0;
    vector< int > cc(g.size());
    for(int i = 0; i < g.size(); i++) {
      if(i == uf.find(i)) cc[i] = ptr++;
    }

    t.resize(ptr);
    for(int i = 0; i < g.size(); i++) {
      comp[i] = cc[uf.find(i)];
    }
    vector< pair< int, int > > vs;
    for(auto &e : edges) {
      int x = comp[e.first], y = comp[e.second];
      if(x == y) continue;
      vs.emplace_back(e.first, e.second);
      t[x].push_back(y);
      t[y].push_back(x);
    }
    sort(begin(vs), end(vs));
    return (vs);
  }
};


void solve()
{
  int V, E;
  cin >> V >> E;
  BiConnectedComponents graph(V);
  vector< vector< int > > malta;
  for(int i = 0; i < E; i++) {
    int s, t;
    cin >> s >> t;
    graph.add_edge(s, t);
  }
  for(auto &p : graph.build(malta)) {
    cout << p.first << " " << p.second << endl;
  }

}

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

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

int main(){
  int x, n;
  cin >> x >> n;
  vector<int> p(n);
  for(int i = 0; i < n; i++) cin >> p.at(i);
  
  vector<int> q(201);
  for(int i = 0; i < 201; i++) q.at(i) = i;
  
  for(int i = 0; i < n; i++){
    for(int j = 0; j < (int)q.size(); j++){
      if(p[i] == q[j]){
        q.erase(q.begin() + j);
        j--;
      }
    }
  }
  
  int ans = 201, minimum = 201;
  
  for(int i = q.size()-1; i >= 0; i--){
    if(minimum >= abs(x-q[i])){
      minimum = abs(x-q[i]);
      ans = q[i];
    }
  }
  
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

const ll MOD = 1000000007;

ll fact[1000000],fact_inv[1000000];

ll power(ll a,ll b){
  ll res = 1;
  while(b>0){
    if(b&1) res = res*a%MOD;
    a = a*a%MOD;
    b>>=1;
  }
  return res;
}

ll comb(ll n,ll r){
  return (fact[n]*fact_inv[r])%MOD*fact_inv[n-r]%MOD;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n,k;
  cin >> n >> k;

  vector<ll> s(n+1,0);
  for(int i=0;i<n;i++){
    s[i+1] = s[i] + i+1;
  }

  /*
  fact[0] = 1;
  for(int i=0;i<=n;i++){
    fact[i+1] = fact[i]*(i+1)%MOD;
  }
  fact_inv[n+1] = power(fact[n+1],MOD-2);
  for(int i=n;i>=0;i--){
    fact_inv[i] = fact_inv[i+1]*(i+1)%MOD;
  }

  */

  ll sum = 0;
  for(int i=k;i<=n;i++){
    sum += (s[n]-s[n-i]) - s[i-1]+1;
    sum %= MOD;
  }
  sum++;
  sum %= MOD;

  cout << sum << endl;
}


Measured memory_bytes: 4784
n=int(input())
a=list(map(int,input().split()))
b=[0]
b.extend(a)
b.append(0)
a=b
base=0
for i in range(n+1):
    base+=abs(a[i+1]-a[i])
ans=[]
for i in range(1,n+1):
    ans.append(base+abs(a[i+1]-a[i-1])-abs(a[i+1]-a[i])-abs(a[i]-a[i-1]))
for i in range(n):
    print(ans[i])

Measured memory_bytes: 60012
#include <bits/stdc++.h>
// std::numeric_limits<int>::max(), min()
// std::setprecision(X)
// std::islower(), std::isupper(), std::tolower, std::toupper
// std::accumulate(m.begin(), m.end(), 0LL);
// std::sort(begin(),end()) // 0, 1, 2, 3 ,4 (default, less);
// std::priority_queue<int, vector<int>, less<int>> que; // 4, 3, 2, 1 (defualt, less) : 
// if ( std::regex_match(S, std::regex("(dream|dreamer|erase|eraser)*")) ) std::cout << "YES" << std::endl;
 
#define rep(i, n) for(int i = 0; i < (int)(n);    i++)
#define sz(x) ((int)(x).size())
#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;
typedef std::vector<int> vi;
typedef std::vector<std::vector<int>> vvi;

ll gcd ( ll a, ll b ) { if ( b == 0 ) return a; else return gcd ( b, a%b ); }
ll lcm ( ll a, ll b ) { return a * b / gcd(a, b); }

int arr[] = { 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51 };

int main (void) {
  std::cin.tie(0);  std::ios::sync_with_stdio(false);
  int K; std::cin >> K;
  std::cout << arr[K-1] << std::endl; 
  return 0;
}



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

int main()
{
	string a,b;
	cin >> a >> b;
	if(a.length()>b.length()) {
		cout << "GREATER";
		return 0;
	}
	else if(a.length()<b.length()){
		cout << "LESS";
		return 0;
 }
	else
		for(int i=0;i<a.length();i++){
			if(a>b) {
				cout << "GREATER";
				return 0;
			}
			else if(a<b) {
				cout << "LESS";
				return 0;
			}
		}
	cout << "EQUAL";
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
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; }

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> a(3);
	rep(i,3) cin >> a[i];
	vector<P> query;
	rep(i,n){
		string s;
		cin >> s;
		if(s == "AB") query.emplace_back(0, 1);
		if(s == "AC") query.emplace_back(0, 2);
		if(s == "BC") query.emplace_back(1, 2);
	}
	string ans = "";
	rep(i,n){
		int x = query[i].first;
		int y = query[i].second;
		if(a[x] == 0 && a[y] == 0){
			cout << "No" << endl;
			return 0;
		}
		if(a[x] == 0){
			++a[x];
			--a[y];
			ans += 'A' + x;
		}
		else if(a[y] == 0){
			++a[y];
			--a[x];
			ans += 'A' + y;
		}
		else{
			int nx = query[i+1].first;
			int ny = query[i+1].second;
			if(x == nx || x == ny){
				++a[x];
				--a[y];
				ans += 'A' + x;
			}
			else{
				++a[y];
				--a[x];
				ans += 'A' + y;
			}
		}
	}
	cout << "Yes" << endl;
	rep(i,n) cout << ans[i] << endl;
	return 0;
}

Measured memory_bytes: 4264
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<math.h>
#include<limits.h>
int main(){
    int L,R,d;
    int ans = 0;
    scanf("%d %d %d",&L,&R,&d);
    for(int i=L;i<=R;i++)
        if(i%d==0) ans++;
    printf("%d",ans);
}


Measured memory_bytes: 1732
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=(1<<20)+3,INF=1<<28;
vector<pair<int,ll>> G[MAX];//firstのタイミングでsecond個
int cnt0[MAX];

ll rui(ll a,ll b){
    ll ans=1;
    while(b>0){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b/=2;
    }
    return ans;
}

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N;cin>>N;
    vector<int> A(N+1);
    for(int i=0;i<N;i++){
        cin>>A[i+1];
        A[i+1]^=A[i];
        cnt0[i+1]=cnt0[i];
        
        if(A[i+1]==0){
            cnt0[i+1]++;
        }else{
            if(G[A[i+1]].size()==0) G[A[i+1]].push_back({i+1,1});
            else{
                G[A[i+1]].push_back({-1,cnt0[i+1]-cnt0[G[A[i+1]].back().first]});
                G[A[i+1]].push_back({i+1,1});
            }
        }
    }
    
    if(A[N]!=0){
        int X=A[N];
        
        vector<vector<ll>> dp(G[X].size()+1,vector<ll>(2));
        dp[0][0]=1;
        
        for(int i=1;i<=G[X].size();i++){
            if(G[X][i-1].first!=-1){
                dp[i][0]=dp[i-1][0];
                dp[i][1]=dp[i-1][0]+dp[i-1][1];
            }else{
                dp[i][0]=dp[i-1][0]+dp[i-1][1]*G[X][i-1].second;
                dp[i][1]=dp[i-1][1];
            }
            
            dp[i][0]%=mod;
            dp[i][1]%=mod;
            
            //cout<<G[X][i-1].first<<" "<<G[X][i-1].second<<endl;
        }
        
        cout<<dp[G[X].size()][0]<<endl;
    }else{
        ll ans=0;
        ans+=rui(2,cnt0[N]-1);
        
        for(int X=1;X<(1<<20);X++){
            if(G[X].size()==0) continue;
            
            vector<vector<ll>> dp(G[X].size()+1,vector<ll>(2));
            dp[0][0]=1;
            
            for(int i=1;i<=G[X].size();i++){
                if(G[X][i-1].first!=-1){
                    dp[i][0]=dp[i-1][0];
                    dp[i][1]=dp[i-1][0]+dp[i-1][1];
                }else{
                    dp[i][0]=dp[i-1][0]+dp[i-1][1]*G[X][i-1].second;
                    dp[i][1]=dp[i-1][1];
                }
                
                dp[i][0]%=mod;
                dp[i][1]%=mod;
            }
            
            ans+=dp[G[X].size()][1];
            ans%=mod;
        }
        
        cout<<ans<<endl;
    }
}


Measured memory_bytes: 70116
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

LL n,m,k;

LL ncr[305][305];

LL dp[305][305],sum[305][305];  // size, root

int main()
{
    cin>>n>>k>>m;
    for(int i=0;i<=n+1;i++)
    {
        ncr[i][0]=ncr[i][i]=1;
        for(int j=1;j<i;j++)ncr[i][j]=(ncr[i-1][j-1]+ncr[i-1][j])%m;
    }

    for(int i=0;i<=k;i++)
    {
        dp[1][i]=1;
        sum[1][i]=(k-i+1)%m;
    }

    for(int sz=2;sz<=n+1;sz++)
    {
        for(int root=0;root<=k;root++)
        {
            for(int x=1;x<sz;x++)dp[sz][root]+=(((dp[sz-x][root]*sum[x][root+1])%m)*ncr[sz-2][x-1])%m;
            dp[sz][root]%=m;

        }
        for(int root=k;root>=0;root--) sum[sz][root]=(dp[sz][root]+sum[sz][root+1])%m;
    }
    cout<<dp[n+1][0]<<endl;
    return 0;

}


Measured memory_bytes: 2432