akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>

#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define all(c) begin(c),end(c)

template<typename T1, typename T2>
inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }

template<typename T1, typename T2>
inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }

//改造
typedef long long int ll;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 1000000007


//ここから編集する
class Solve {
public:
    void input() {

    }

    bool sol() {
        int n, m, p;
        cin >> n >> m >> p;
        if (n == 0) return false;
        vector<int> x(n);
        rep(i, 0, n) cin >> x[i];
        int sum = accumulate(all(x), 0);
        if (x[m - 1] == 0) {
            cout << 0 << endl;
        } else {
            int ans = sum * (100 - p) / x[m - 1];
            cout << ans << endl;
        }
        return true;
    }

    void solve() {
        input();
        while (sol()) {

        }

    }
};


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    Solve().solve();


    return 0;
}



Measured memory_bytes: 3144
package main

import (
	"bufio"
	"fmt"
	"math/big"
	"os"
	"strconv"
)

func main() {
	N := readInt()
	A := make([]*big.Int, N)
	for i := 0; i < N; i++ {
		A[i] = big.NewInt(int64(readInt()))
	}

	v := big.NewInt(1)
	for i := 0; i < N; i++ {
		gcd := new(big.Int).GCD(nil, nil, v, A[i])
		v.Mul(v, A[i])
		v.Div(v, gcd)
	}

	result := big.NewInt(0)
	for i := 0; i < N; i++ {
		result.Add(result, new(big.Int).Div(v, A[i]))
	}
	result.Rem(result, big.NewInt(1000000007))

	fmt.Println(result)
}

const (
	ioBufferSize = 1 * 1024 * 1024 // 1 MB
)

var stdinScanner = func() *bufio.Scanner {
	result := bufio.NewScanner(os.Stdin)
	result.Buffer(make([]byte, ioBufferSize), ioBufferSize)
	result.Split(bufio.ScanWords)
	return result
}()

func readString() string {
	stdinScanner.Scan()
	return stdinScanner.Text()
}

func readInt() int {
	result, err := strconv.Atoi(readString())
	if err != nil {
		panic(err)
	}
	return result
}


Measured memory_bytes: 6784
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <bitset>    // bitset
#include <cctype>    // isupper, islower, isdigit, toupper, tolower
#include <cstdint>   // int64_t, int*_t
#include <cstdio>    // printf
#include <deque>     // deque
#include <iostream>  // cout, endl, cin
#include <iomanip>    // setprecision
#include <map>       // map
#include <queue>     // queue, priority_queue
#include <set>       // set
#include <stack>     // stack
#include <string>    // string, to_string, stoi
#include <tuple>     // tuple, make_tuple
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <utility>       // pair, make_pair
#include <vector>        // vector
using namespace std;

int gcd(long long a, long long b) { return b != 0 ? gcd(b, a % b) : a; }

int main() {
    long long H;
    cin >> H;

    cout << setprecision(100);
    cout << pow(2, floor(log2(H)) + 1) - 1 << endl;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define all(v) ((v).begin()),((v).end())
#define ll long long
#define fastIO cout << fixed << setprecision(9), ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
double const EPS = 1e-9, PI = acos(-1);
const int N = 2e5 + 9, M = 1e3 + 9, OO = 1e9 + 7, MOD = 1e9 + 7;
const ll inf = 1e18;

ll add(ll a, ll b) {
  a = ((a % MOD) + (b % MOD)) % MOD;
  return a;
}

ll sub(ll a, ll b) {
  a = (((((a % MOD) - (b % MOD)) % MOD) + MOD) % MOD);
  return a;
}

ll mul(ll a, ll b) {
  return (a * b) % MOD;
}

ll power(ll a, ll b) {
  ll ret = 1;
  while(b) {
    if(b & 1)
      ret = mul(ret, a);
     b /= 2;
     a = mul(a, a);
  }
  return ret;
}

string arr[M];
ll fact[N], inv[N], dp[N];

int main() {
  fastIO;
#ifdef LOCAL
  freopen("input.in", "rt", stdin);
#endif
  fact[0] = 1, inv[0] = 1;
  for (int i = 1; i < N; ++i)
    fact[i] = mul(i, fact[i - 1]), inv[i] = power(fact[i], MOD - 2);
  int n, m, k, x, y;
  cin >> n >> m >> k;
  vector<pair<int, int>> vec;
  for (int i = 0; i < k; ++i) {
    cin >> x >> y;
    vec.push_back({x, y});
//    dp[i] = mul(fact[(x - 1) + (y - 1)], mul(inv[(x - 1)],inv[y - 1])); // (x - 1) + (y - 1) - (y - 1) => (x-1)
    cerr << dp[i] << endl;
  }
  sort(vec.begin(), vec.end());
  for (int i = 0; i < k; ++i) {
    x = vec[i].first, y = vec[i].second;
    ll tmp = mul(fact[(x - 1) + (y - 1)], mul(inv[(x - 1)],inv[y - 1]));
    for (int j = 0; j < k; ++j) {
      if(j == i || (vec[j].first == vec[i].first && vec[j].second == vec[i].second))
        continue;
      if(vec[j].first <= vec[i].first && vec[j].second <= vec[i].second) {
        ll temp = mul(fact[(vec[i].first - vec[j].first) + (vec[i].second - vec[j].second)], mul(inv[(vec[i].first - vec[j].first)],inv[(vec[i].second - vec[j].second)]));
        tmp = sub(tmp, mul(dp[j], temp));
//        cerr << dp[i] << endl;
      }
    }
    dp[i] = tmp;
  }
  dp[k] = mul(fact[(n - 1) + (m - 1)], mul(inv[(n - 1)],inv[m - 1]));
  for (int j = 0; j < k; ++j) {
    if(vec[j].first <= n && vec[j].second <= m) {
      ll temp = mul(fact[(n - vec[j].first) + (m - vec[j].second)], mul(inv[(n - vec[j].first)],inv[(m - vec[j].second)]));
      dp[k] = sub(dp[k], mul(dp[j], temp));
      cerr << dp[k] << endl;
    }
  }
  cout << dp[k];
//  for (int i = 1; i <= mm; ++i) {
//    int m = i;
//    memset(dp, 0, sizeof dp);
//    dp[0][0] = 1;
//    int a = n, b = m;
//    if(a < b)
//      swap(a, b);
//    ll ans = mul(fact[a+b-2], mul(inv[b - 1], inv[a - 1]));
//    cerr << ans << endl;
//    for (int i = 0; i < n; ++i) {
//      for (int j = 0; j < m; ++j) {
//        if(arr[i][j] == '#') continue;
//        if(i)
//          dp[i][j] = add(dp[i][j], dp[i-1][j]);
//        if(j)
//          dp[i][j] = add(dp[i][j], dp[i][j-1]);
//      }
//    }
//    cout << (dp[n-1][m-1] != ans) << endl;
//  }
  return 0;
}


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

#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define for1(i, n) for (int i = 1; i <= int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i <= int(r); ++i)
#define ford(i, n) for (int i = int(n)-1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define ms(a, x) memset(a, x, sizeof(a))
#define F first
#define S second
#define endl '\n'
#define de(x) cout<<#x<<" = "<<(x)<<endl
#define de2(x,y) cout<<#x<<" = "<<(x) <<' '<< #y<<" = "<<y<<endl;

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());

const int N=1005;
char a[N][N];
int dp[N][N];
const int mod=1e9+7;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	for1(i,n){
		cin>>a[i]+1;
	}
	dp[1][1]=1;
	for1(i,n){
		for1(j,m){
			if(i==1&&j==1) continue;
			if(a[i][j]=='.')
			dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod;
		}
	}
	cout<<dp[n][m];
    return 0;
}


Measured memory_bytes: 5248
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define all(x) (x).begin (),(x).end()
#define pb push_back
#define mp make_pair
#define vi vector<ll>
#define pii pair<ll,ll>
#define vii vector<pii>
#define mi map<ll,ll>
#define endl "\n"
#define si set<ll>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define M 1000000007LL


void solve()
{
    ll n,k;
    cin>>n>>k;
    n = n%k;
    n = min(n,k-n);
    cout<<n;
}

int main()
{
    SPEED;
    ll t = 1;

   // cin>>t;

    while(t--) solve();

   return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
//#define mt make_tuple
//typedef tuple<double,int,double> tp;
//typedef vector<tp> vt;
const double PI=acos(-1);
const double EPS=1e-7;
const int inf=1e9;
const ll INF=2e18;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int in[10][10];
int f(int a,int b){return in[a][b];};
int F(int a,int b,int c,int d,int e){
	vi t{a,b,c,d,e};
	rep(i,5)rep(j,10)if(t[i]!=j){
		int q=t[i];
		t[i]=j;
		if(!f(f(f(f(f(0,t[0]),t[1]),t[2]),t[3]),t[4]))return 1;
		t[i]=q;
	}
	rep(i,4)if(t[i]!=t[i+1]){
		swap(t[i],t[i+1]);
		if(!f(f(f(f(f(0,t[0]),t[1]),t[2]),t[3]),t[4]))return 1;
		swap(t[i],t[i+1]);
	}
	return 0;
}
int main(){
	rep(i,10)rep(j,10)cin>>in[i][j];
	int out=0;
	rep(i,10)rep(j,10)rep(k,10)rep(l,10){
		if(F(i,j,k,l,f(f(f(f(0,i),j),k),l)))out++;
	}
	cout<<out<<endl;
}

Measured memory_bytes: 3124
N = int(input())
A = list(map(int, input().split()))
D = [0]*(N+1)
for a in A:
  D[a] += 1
tot = sum([D[i]*(D[i]-1)//2 for i in range(1,N+1)])
#print(D)
#print([D[i]*(D[i]-1)//2 for i in range(N)])

#print([(D[i]-1)*(D[i]-2)//2 for i in range(N)])
#print(tot)
for a in A:
  print(tot - D[a]+1)

Measured memory_bytes: 26140
class Dice
  def initialize(t, s, e, w, n, b)
    $north = n
    $south = s
    $east = e
    $west = w
    $top = t
    $bottom = b
  end

  def execute_orders(orders)
    length = orders.length
    for i in 0...length
      if orders[i] == "N"
        move_north
      elsif orders[i] == "S"
        move_south
      elsif orders[i] == "E"
        move_east
      elsif orders[i] == "W"
        move_west
      else
        puts "error!"
      end
    end
  end

  def check_dices_same(order_t, order_s, order_e, order_w, order_n, order_b)
      100.times do
        execute_orders(["N", "W"].sample)
        return true if $top == order_t && $south == order_s && $east == order_e && $west == order_w && $north == order_n && $bottom == order_b
      end
    return false
  end


  private
  def move_north
    north = $north
    south = $south
    top = $top
    bottom = $bottom
    $north = top
    $top = south
    $bottom = north
    $south = bottom
  end

  def move_south
    north = $north
    south = $south
    top = $top
    bottom = $bottom
    $south = top
    $bottom = south
    $north = bottom
    $top = north
  end

  def move_east
    top = $top
    bottom = $bottom
    east = $east
    west = $west
    $east = top
    $bottom = east
    $west = bottom
    $top = west
  end

  def move_west
    top = $top
    bottom = $bottom
    east = $east
    west = $west
    $west = top
    $bottom = west
    $east = bottom
    $top = east
  end
end

dice_numbers_1 = gets.chomp.split.map(&:to_i)
dice_numbers_2 = gets.chomp.split.map(&:to_i)
dice1 = Dice.new(dice_numbers_1[0], dice_numbers_1[1], dice_numbers_1[2], dice_numbers_1[3], dice_numbers_1[4], dice_numbers_1[5])
if dice1.check_dices_same(dice_numbers_2[0], dice_numbers_2[1], dice_numbers_2[2], dice_numbers_2[3], dice_numbers_2[4], dice_numbers_2[5])
  puts "Yes"
else
  puts "No"
end

Measured memory_bytes: 8704
#include <bits/stdc++.h>
#define N 410
#define pb push_back
#define fi first
#define se second
#define si size()
#define ll long long
#define mp make_pair
#define iter ::iterator
#define all(v) v.begin(), v.end()
#define pp pop_back
#define mapiter map<int, int>::iterator
#define forn(i, n) for(int i = 0; i < n; ++i)
#define forn1(i, n) for(int i = 1; i <= n; ++i)
#define forr(i, n)	for(int i = n - 1; i >= 0; --i)
#define forr1(i, n)	for(int i = n; i >= 1; --i)
#define form(l, r, i)	for(int i = l; i <= r; ++i)
#define forv(r, l, i)	for(int i = r; i >= l; --i)
#define r0 return 0
#define barnarnar ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lld long double
#define elif else if
 
const int inf = 1e9 + 7;
const lld EPS = 0.00000001;
const ll modw = 1e9 + 7;
 
using namespace std;
 
ll dp[N][N]; // min sum to combine vertex from i to j
ll pr[N];
ll a[N];
 
ll get(ll l, ll r)
{
	return pr[r] - pr[l - 1];
}
 
int main()
{
	barnarnar
	int n;
	cin >> n;
	forn1(i, n)	cin >> a[i], pr[i] = pr[i - 1] + a[i];
	for(int len = 1; len <= n; len++)
	{
		for(int l = 1; l <= n - len + 1; l++)
		{
			int r = l + len - 1;
			if(len == 1)	dp[l][r] = 0;
			elif(len == 2)	dp[l][r] = a[l] + a[r];
			else
			{
				ll ans = min(dp[l + 1][r] + get(l + 1, r) + a[l], dp[l][r - 1] + get(l, r - 1) + a[r]); // combine [l] [l+1..r] and [l..r-1] [r]
				for(int j = l + 1; j <= r - 1; j++) // trying to combine [l..j][j+1..r]
				{
					ans = min(ans, dp[l][j] + dp[j + 1][r] + get(l, j) + get(j + 1, r));
				}
				dp[l][r] = ans;
			}
		}
	}
	cout << dp[1][n];
	return 0;
}

Measured memory_bytes: 1536
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
const int max_length = 1000;
int top,S[max_length];
void push(int t){
    S[++top] = t;
}
int pop(){
    top--;
    return S[top+1];
}
int main(){
    int a,b;
    top = 0;
    char s[100];
    while(scanf("%s",s) != EOF){
        if(s[0]=='+'){
            a = pop();
            b = pop();
            push(a+b);
        }else if(s[0]=='-'){
            a = pop();
            b = pop();
            push(b-a);
        }else if(s[0]=='*'){
            a = pop();
            b = pop();
            push(a*b);
        }else{
            push(atoi(s));
        }
    }
    printf("%d\n",pop());
    return 0;
}

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

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

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n)-1; i >= 0; i--)
#define repf(i, x, n) for (int i = (int)(x); i < (int)(n); i++)
#define repfr(i, x, n) for (int i = (int)(x)-1; i >= (int)(n); i--)
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;
}
template <class T> inline void in(T &a) { cin >> a; }
template <class T, class U> inline void in(T &a, U &b) { cin >> a >> b; }
template <class T, class U, class V> inline void in(T &a, U &b, V &c) {
  cin >> a >> b >> c;
}
template <class T> inline void out(T a) { std::cout << a << endl; }
template <class T, class U> inline void out(T a, U b) {
  cout << a << ' ' << b << endl;
}
template <class T, class U, class V> inline void out(T a, U b, V c) {
  cout << a << ' ' << b << ' ' << c << endl;
}
#define inf 1e9
using ll = int64_t;
#define waru 1000000007

void Main() {
  ll n, k;
  in(n, k);
  out((n * n) - k);

  return;
}

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  Main();
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

int main(){
    string str;
    cin >> str;
    int K;
    cin >> K;

    set<string> strs;
    vector<string> sstrs;

    for(int i=0; i<str.length(); i++){
        for(int j=i+1; j<=min((int)str.length(), i+6); j++){
            string tmp = str.substr(i, j-i);
            strs.insert(tmp);
        }
    }

    for(string s : strs){
        sstrs.push_back(s);
    }

    sort(sstrs.begin(), sstrs.end());
    cout << sstrs[K-1] << endl;
}

Measured memory_bytes: 2560
import java.util.*;

class Main
{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String s = sc.next();
		
		int len = s.length();
		
		int min = 900;
		
		for(int i = 0; i < len - 2; ++i) {
		    String sub = s.substring(i, i + 3);
		    int n = Integer.parseInt(sub);
		    
		    if(min > Math.abs(n - 753)) min = Math.abs(n - 753);
		    else continue;
		}
		
		System.out.println(min);
	}
}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

int a,b,c,n;

int main(){
	cin>>a>>b>>c>>n;
	int res=0;
	for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) for(int k=0;k<=n;k++) if(i+j+k==n){
		res=max(res,a*(1<<i)+b*(1<<j)+c*(1<<k));
	}
	cout<<res<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);

using namespace std;

namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9;

int main(){
	cin.tie(0); cin.sync_with_stdio(0);
	string s, t; cin >> s >> t;
	const int mod = 1e9 + 7;
	vi dp(t.size() + 1);
	dp[0] = 1;
	rep(i, s.size()){
		for(int j = (int)t.size() - 1; j >= 0; j--){
			if(s[i] != t[j]) continue;
			(dp[j + 1] += dp[j]) %= mod;
		}
	}
	cout << dp[t.size()] << endl;
	return 0;
}


Measured memory_bytes: 3232
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using static System.Math;

namespace CSharpSpiral {
	class Program {
		static void Main(string[] args) {
			var sw = new StreamWriter(Console.OpenStandardOutput()) {
				AutoFlush=
#if DEBUG
			true
#else
			false
#endif
			};
			Console.SetOut(sw);
			new Program().Solve(new ConsoleInput(
#if DEBUG
			new StreamReader("../../../inputData.txt")
#else
			Console.In
#endif
			, ' '));
			Console.Out.Flush();
		}
		public void Solve(ConsoleInput cin) {
			var D = new Dictionary<string, int>();
			var N = cin.ReadInt;
			for(int i = 0; i<N; i++) {
				var S = cin.ReadLine;
				if(D.ContainsKey(S)) D[S]++;
				else D.Add(S, 1);
			}
			Console.WriteLine(D.Count());
		}
	}
	static class ExtendClass {
		public static void Swap<T>(this T[] A, int x, int y) {
			var tmp = A[x];
			A[x]=A[y];
			A[y]=tmp;
		}
		public static string Join<T>(this IEnumerable<T> X, string separator = " ") => string.Join(separator, X);
		public static IEnumerable<int> Indices<T>(this T[] X) => Enumerable.Range(0, X.Length);
		public static IEnumerable<int> Indices<T>(this T[,] X, int dim)
			=> Enumerable.Range(0, X.GetLength(dim));
		public static string Join<T>(this T[,] X, string separatorD2 = ",", string separatorD1 = "\n")
			=> X.Indices(0).Select(
				i => X.Indices(1).Select(j => X[i, j]).Join(separatorD2)
			).Join(separatorD1);
	}
	class ConsoleInput {
		private readonly TextReader _stream;
		private readonly char _separator = ' ';
		private readonly Queue<string> inputStream;
		public ConsoleInput(TextReader stream, char separator = ' ') {
			this._separator=separator;
			this._stream=stream;
			inputStream=new Queue<string>();
		}
		public string Read {
			get {
				if(inputStream.Count!=0) return inputStream.Dequeue();
				string[] tmp = _stream.ReadLine().Split(_separator);
				for(int i = 0; i<tmp.Length; ++i)
					inputStream.Enqueue(tmp[i]);
				return inputStream.Dequeue();
			}
		}
		public string ReadLine { get { return _stream.ReadLine(); } }
		public int ReadInt { get { return int.Parse(Read); } }
		public long ReadLong { get { return long.Parse(Read); } }
		public double ReadDouble { get { return double.Parse(Read); } }
		public string[] ReadStrArray(long N) {
			var ret = new string[N];
			for(long i = 0; i<N; ++i)
				ret[i]=Read;
			return ret;
		}
		public int[] ReadIntArray(long N) { var ret = new int[N]; for(long i = 0; i<N; ++i) ret[i]=ReadInt; return ret; }
		public long[] ReadLongArray(long N) { var ret = new long[N]; for(long i = 0; i<N; ++i) ret[i]=ReadLong; return ret; }
		public double[] ReadDoubleArray(long N) { var ret = new double[N]; for(long i = 0; i<N; ++i) ret[i]=ReadDouble; return ret; }
		public bool isEOF {
			get { return _stream.Peek()==-1; }
		}
	}
}

Measured memory_bytes: 50288
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
const int INF = 100010001;
const ll LINF = (ll)INF*INF*10;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n, a, b;
    cin >> n >> a >> b;
    ll num = n*b-b+a-n*a-b+a+1;
    cout << (num > 0?num:0) << endl;
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long  a,b,x;
    cin>>a>>b>>x;
    long long  p = a/x;
    long long q = b/x;
    if((a%x)!=0)
        p++;
    cout<<q-p+1<<endl;
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
#define range(i, l, r) for(long long int (i) = (l); (i) < (r); (i)++)
#define reversed_range(i, l, r) for (long long int (i) = (r) - 1; (i) >= l; (i)--)
using namespace std;
template <typename T>
using vec = vector<T>;
using lint = long long;
using ulint = unsigned long long;
using pint = pair<int, int>;
using plint = pair<lint, lint>;

template <typename S, typename T>
ostream& operator <<(ostream& os, pair<S, T> p) {
    os << "(";
    os << p.first << ", " << p.second;
    return os << ")";
}

template <typename T>
ostream& operator <<(ostream& os, vec<T> v) {
    os << "[";
    if (v.size() == 0) return os << "]";
    for (int i = 0; i < v.size() - 1; i++) {
        os << v.at(i) << ", ";
    }
    return os << v.at(v.size() - 1) << "]";
}

template <typename T>
ostream& operator <<(ostream& os, set<T>& s) {
    os << "{";
    if (s.begin() == s.end()) return os << "}";
    auto it_first_item = s.begin();
    os << *it_first_item;
    for (auto it = ++it_first_item; it != s.end(); it++) {
        os << ", " << *it;
    }
    return os << "}";
}

template <typename T>
ostream& operator <<(ostream& os, unordered_set<T>& s) {
    os << "{";
    if (s.begin() == s.end()) return os << "}";
    auto it_first_item = s.begin();
    os << *it_first_item;
    for (auto it = ++it_first_item; it != s.end(); it++) {
        os << ", " << *it;
    }
    return os << "}";
}

template <typename K, typename V>
ostream& operator <<(ostream& os, map<K, V> m) {
    os << "{";
    if (m.begin() == m.end()) return os << "}";
    auto it_first_item = m.begin();
    os << it_first_item->first << ": " << it_first_item->second;
    for (auto it = ++it_first_item; it != m.end(); it++) {
        os << ", " << it->first << ": " << it->second;
    }
    return os << "}";
}

template <typename K, typename V>
ostream& operator <<(ostream& os, unordered_map<K, V> m) {
    os << "{";
    if (m.begin() == m.end()) return os << "}";
    auto it_first_item = m.begin();
    os << it_first_item->first << ": " << it_first_item->second;
    for (auto it = ++it_first_item; it != m.end(); it++) {
        os << ", " << it->first << ": " << it->second;
    }
    return os << "}";
}

lint pow(lint num, lint e, lint MOD) {
    lint res = 1;
    lint cur_num = num;
    while (e) {
        if (e & 1) {
            res *= cur_num;
            res %= MOD;
        }
        cur_num *= cur_num;
        cur_num %= MOD;
        e >>= 1;
    }
    return res;
}

int main() {
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    lint N; cin >> N;
    map<string, lint> count;
    range(i, 0, N) {
        string S; cin >> S;
        count[S] += 1;
    }
    lint max_cnt = -1;
    for (const auto& p : count) {
        lint c;
        c = p.second;
        max_cnt = max(max_cnt, c);
    }
    for (const auto& p : count) {
        if (p.second == max_cnt) cout << p.first << "\n";
    }
}

Measured memory_bytes: 23936
import java.io.*
import java.util.*

fun solve(N: Int, S: String){
    var ans = 0
    var ret = S[0]
    for(i in 0 until N){
        if(ret != S[i]){
            ans++
            ret = S[i]
        }
    }
    println(ans + 1)
    return
}


fun main(args: Array<String>) {
    fun StringArray(size: Int, init: (Int) -> String = { "\u0000" }): Array<String> {
        return Array<String>(size, init)
    }
    class Scanner(stream: InputStream) {
        private val reader = BufferedInputStream(stream).bufferedReader()
        private var st: StringTokenizer? = null
        fun next(): String {
            while (!(st?.hasMoreTokens() ?: false)) st = StringTokenizer(reader.readLine())
            return st!!.nextToken()
        }
    }
    val sc = Scanner(System.`in`)
    val N = sc.next().toInt()
    val S = sc.next()
    solve(N, S)
}



Measured memory_bytes: 32432
///By Stephan Ramirez dsramirezc@unal.edu.co
#include<bits/stdc++.h>
#define ms(a,v) memset(a,v,sizeof a)
#define ll long long
#define N 100005
using namespace std;

bool vis[N];
int ans[N];
int arr[N];
int n;
priority_queue<pair<int,int> ,vector<pair<int,int>>, greater<pair<int,int>> > pq;
int main(){
	#ifdef LOCAL
		//freopen("in.txt","r",stdin);
		//freopen("out.txt","w",stdout);
	#endif
    scanf("%d",&n);
    for(int i=0;i<n-1;i++){
        scanf("%d",&arr[i]);
        pq.push(make_pair(arr[i],i));
    }
    while(pq.size()>0){
        pair<int,int> a=pq.top();
        pq.pop();
        if(vis[a.second]==false){
            vis[a.second]=true;
            ans[a.second]=a.first;
        }
        if(vis[a.second+1]==false){
            vis[a.second+1]=true;
            ans[a.second+1]=a.first;
        }
    }
    ll res=0;
    for(int i=0;i<n;i++){
        res+=ans[i];
    }
    cout<<res<<endl;
	return 0;
}



Measured memory_bytes: 256
N = int(input())

maxL = [0] * (N+1)
maxR = [0]*(N+1)
num = []
for i in range(N):
    num.append(int(input()))
    maxL[i+1] = maxL[i] if maxL[i] > num[i] else num[i]

for i in range(N-1, 0, -1):
    maxR[i-1] = maxR[i] if maxR[i] > num[i] else num[i]

for i in range(N):
    print(max(maxL[i], maxR[i]))


Measured memory_bytes: 92624
// AtCoder Grand Contest 033
// A - Darker and Darker
// https://atcoder.jp/contests/agc033/tasks/agc033_a
#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for(int i = 0; i < (n); i++)
#define all(a) begin(a),end(a)
template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}
template<class T> inline bool chmax(T& a, T b) {return a<b?a=b,true:false;}

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

    int H, W; cin >> H >> W;
    vector<string> grid(H);
    vector<vector<int>> d(H, vector<int>(W, -1));
    queue<pair<int, int>> q;
    rep(i, H) {
        cin >> grid[i];
        rep(j, W) {
            if (grid[i][j] == '#') {
                d[i][j] = 0;
                q.push(make_pair(i, j));
            }
        }
    }

    int ans = 0;

    int dw[4] = { 0, 0,-1, 1 };
    int dh[4] = {-1, 1, 0, 0 };

    while (!q.empty()) {
        pair<int, int> hw = q.front(); q.pop();
        rep(j, 4) {
            int h = hw.first + dh[j];
            int w = hw.second + dw[j];
            if (0 <= h && h < H && 0 <= w && w < W && grid[h][w] != '#' && d[h][w] == -1) {
                d[h][w] = d[hw.first][hw.second]+1;
                chmax(ans, d[h][w]);
                q.push(make_pair(h, w));
            }
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 13456
#include<stdio.h>
int main(){
  int a,b,count=0,i;
  scanf("%d%d",&a,&b);
  for(i=a;i<=b;i++)
    if(i%10==(i/10000)%10 && (i/10)%10==(i/1000)%10)
      count++;
  printf("%d\n",count);
  return 0;
}


Measured memory_bytes: 128
#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
#include <set>
#include <map>
#include <queue>


using namespace std;
using ll = long long int;

template <class T> ostream &operator<<(ostream &os, vector<T> &v) {
  for (auto i = v.begin(); i != v.end(); i++) {
    os << *i << " ";
  }
  return os;
}


void solve(long long N, long long M, std::vector<long long> x, std::vector<long long> y){
  vector<ll> b(N+1, 1);
  vector<bool> r(N+1, false);
  r[1] = true;
  for(int i=0; i<M; i++) {
    if(r[x[i]])
      r[y[i]] = true;
    b[x[i]]--;
    b[y[i]]++;
    if(b[x[i]]==0)
      r[x[i]]=false;
  }
  ll ans = 0;
  for(auto x:r) {
    if(x)
      ans++;
  }
  std::cout << ans << std::endl;
}

int main(){
  long long N;
  scanf("%lld",&N);
  long long M;
  scanf("%lld",&M);
  std::vector<long long> x(M);
  std::vector<long long> y(M);
  for(int i = 0 ; i < M ; i++){
    scanf("%lld",&x[i]);
    scanf("%lld",&y[i]);
  }
  solve(N, M, std::move(x), std::move(y));
  return 0;
}



Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxn 100005
#define maxm 200005
#define INF 1234567890
#define eps 1e-15
#define p 1000000007
const double pi=acos(-1);
template<class T>inline bool read(T &x)
{
    x=0;register char c=getchar();register bool f=0;
    while(!isdigit(c)){if(c==EOF)return false;f^=c=='-',c=getchar();}
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    if(f)x=-x;
    return true;
}
template<class T>inline void print(T x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10^48);
}
template<class T>inline void print(T x,char c){print(x),putchar(c);}
template<class T,class ...S>inline bool read(T &x,S &...y){return read(x)&&read(y...);}
ll n,a,b;
int main()
{
    read(n,a,b);
    if(n==1&&a!=b||a>b)return print(0,'\n'),0;
    else if(n==1&&a==b)return print(1,'\n'),0;
    print((n-2)*(b-a)+1,'\n');
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <sstream>
#include <stack>
#include <map>
#include <set>
#include <ios>
#include <cctype>
#include <cstdio>

#define REP(i,a) for(int i = 0;i < (a);++i)
#define FOR(i,a,b) for(int i = (a);i < (b); ++i)
#define FORR(i,a,b) for(int i = (b) - 1;i >=a;--i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SIZE(obj) (int)(obj).size()
#define MAX(list) std::max(list)
#define MIN(list) std::min(list)
#define YESNO(cond,yes,no){cout <<((cond)?(yes):(no))<<endl; }
#define SORT(list) sort(ALL((list)));
#define RSORT(list) sort((list).rbegin(),(list).rend())

using namespace std;

template<typename T>
T round_up(const T& a, const T& b) {
    return (a + (b - 1)) / b;
}

template <typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
    is >> p.first >> p.second;
    return is;
}

template <typename T1, typename T2>
ostream& operator<<(ostream& os, pair<T1, T2>& p) {
    os << p.first << p.second;
    return os;
}

template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
    REP(i, (int)v.size())is >> v[i];
    return is;
}

template <typename T>
ostream& operator<<(ostream& os, vector<T>& v) {
    REP(i, (int)v.size())os << v[i] << endl;
    return os;
}


using ll = long long;
constexpr int mod = 1'000'000'007;
constexpr int INF = 1'050'000'000;

int clamp(int n, int a, int b) {
    if (n < a)n = a;
    if (n > b)n = b;
    return n;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    std::cout << fixed << setprecision(20);

    int N, K;
    cin >> N >> K;
    double ans = 0.0;
    FOR(i, 1, N + 1) {
        int p = log2(round_up(K, i) - 1) + 1;
        double half = 1.0;
        REP(j, p) {
            half *= 0.5;
        }
        ans += 1.0 / N * half;
    }
    cout << ans << endl;
    return 0;

}

Measured memory_bytes: 256
import sys
def index(x,n):
    if x < 0: return 0
    if n < x: return n
    return x

las = [int(raw_input())]
for s in sys.stdin:
    now = map(int,s.split(","))
    nin,lin = len(now)-1,len(las)-1
    if nin > lin: d = -1
    if nin < lin: d = 1
    for i in xrange(nin+1):
        now[i] += max(las[index(i+d,lin)],las[index(i,lin)])
    if not nin: print now[0]
    las = now

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

// macro
#define rep(i,n) for(i=0;i<n;i++)
#define ll long long
#define all(v) v.begin(), v.end()

// code starts
#define INF 10000000
typedef pair<int,int> P;

int main()
{
  int w,h;cin>>w>>h;
  while(w!=0||h!=0)
  {
    bool maps[h][w][4];//up,right,down,left
    int i,j,k;
    rep(i,h)rep(j,w)rep(k,4)maps[i][j][k]=false;
    rep(i,h)
    {
      maps[i][0][3]=true;
      maps[i][w-1][1]=true;
    }
    rep(i,w)
    {
      maps[0][i][0]=true;
      maps[h-1][i][2]=true;
    }
    maps[0][0][0]=false;
    maps[h-1][w-1][2]=false;
    rep(i,h*2-1)
    {
      if(i%2==0)
      {
        rep(j,w-1)
        {
          int num;cin>>num;
          if(num==1)
          {
            maps[i/2][j][1]=true;
            maps[i/2][j+1][3]=true;
          }
        }
      }
      else
      {
        rep(j,w)
        {
          int num;cin>>num;
          if(num==1)
          {
            maps[i/2][j][2]=true;
            maps[i/2+1][j][0]=true;
          }
        }
      }
    }
    int steps[h][w];
    rep(i,h)rep(j,w)steps[i][j]=INF;
    steps[0][0]=0;
    queue<P> q;
    queue<P> q2;
    vector<int> dh={-1,0,1,0};
    vector<int> dw={0,1,0,-1};
    q.push(make_pair(0,0));
    while(!q.empty())
    {
      while(!q.empty())
      {
        P now=q.front();
        q.pop();
        int nh=now.first;
        int nw=now.second;
        rep(i,4)
        {
          int toh=nh+dh[i];
          int tow=nw+dw[i];
          if(toh<0||toh>=h||tow<0||tow>=w)
          {
            continue;
          }
          if(maps[nh][nw][i])
          {
            continue;
          }
          if(steps[toh][tow]==INF)
          {
            steps[toh][tow]=steps[nh][nw]+1;
            q2.push(make_pair(toh,tow));
          }
        }
      }
      while(!q2.empty())
      {
        q.push(q2.front());
        q2.pop();
      } 
    }
    if(steps[h-1][w-1]==INF)cout<<0<<endl;
    else cout<<steps[h-1][w-1]+1<<endl;
    cin>>w>>h;
  }
}


Measured memory_bytes: 3164
N = int(input())
a = [int(input()) for _ in range(N)]
a.sort()
if N == 2:
    print(a[-1] - a[0])
    exit()

if N % 2 == 0:
    ans = 2 * sum(a[N // 2:]) - 2 * sum(a[:N // 2]) + a[(N // 2) - 1] - a[N // 2]
else:
    ans1 = 2 * sum(a[(N // 2) + 1:]) - 2 * sum(a[:N // 2]) - a[N // 2] + a[(N // 2) - 1]
    ans2 = 2 * sum(a[(N // 2) + 1:]) - 2 * sum(a[:N // 2]) + a[N // 2] - a[(N // 2) + 1]
    ans = max(ans1, ans2)
print(ans)

Measured memory_bytes: 7512
#include <stdio.h>
#include <stdlib.h> 

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;

Node treeMinimum(Node x){
  while(x->left != NIL){
    x = x->left;
  }
  return x;
}

Node treeMaximum(Node x){
  while(x->right != NIL){
    x = x->right;
  }
  return x;
}

Node treeSearch(Node u, int k){
  if(u == NIL || k == u->key) return u;
  if(k < u->key) return treeSearch(u->left, k);
  else return treeSearch(u->right, k);
}

Node treeSuccessor(Node x){
  Node y;
  if(x->right != NIL) return treeMinimum(x->right); 
		       
  y = x->parent;
  while((y != NIL) && x == y->right ){
    x = y;
    y = y->parent;
    return y;         
  }

  
}

void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y

  if( (z->left == NIL) || z->right ==NIL )   y = z ;
  else y = treeSuccessor(z);

  if(y->left != NIL) x = y->left;
  else x = y->right;

  if(x != NIL)x->parent = y->parent;
  if(y->parent == NIL)root =x;
  else if(y == y->parent->left) y->parent->left = x;
  else y->parent->right = x;

  if(y != z) z->key = y->key;

}

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while(x != NIL){
    y = x;
    if( z->key < x->key)
      x = x->left;
    else
      x = x->right;
  }

  z->parent = y;

  if(y == NIL)    root = z ;
  else if(z->key < y->key) y->left = z;
  else  y->right = z;


}

void inorder(Node u){
  if(u != NIL){
    inorder(u->left);
    printf(" %d",u->key);
    inorder(u->right);
  }
  
}
void preorder(Node u){
  if(u != NIL){
    printf(" %d",u->key);
    preorder(u->left);
    preorder(u->right);
  }
}


int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      
      inorder(root);
      // if(i != n-1)printf(" ");//空白処理
       printf("\n");
       
      preorder(root);
      // if(i != n-1) printf(" ");//空白処理
      printf("\n");
      
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }

  return 0;
}



Measured memory_bytes: 20448
def main():
    S = list(input())

    dp = [[0 for _ in range(13)] for _ in range(len(S))]
    # 上からj桁目までの数を13で割ったあまりがiであるものの個数

    for i, sk in enumerate(S):
        if i == 0:
            if sk == '?':
                for j in range(10):
                    dp[0][j] = 1
            else:
                s = int(sk)
                dp[0][s] = 1
            continue
        if sk == '?':
            for j in range(13):
                for l in range(10): # 上からi桁目に入れる数字
                    k = (10*j+l)%13
                    dp[i][k] += dp[i-1][j]
        else:
            s = int(sk)
            for j in range(13):
                k = (10*j+s)%13
                dp[i][k] += dp[i-1][j]
        for j in range(13):
            dp[i][j] = dp[i][j] % 1000000007

    print(dp[-1][5])

if __name__ == '__main__':
    main()

Measured memory_bytes: 71048
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)    for(int i=0; i<(n); ++i)
#define REP(i, d, n) for(int i=(d); i<(n); ++i)
#define rrep(i, n)   for(int i=(n-1); i>=0; --i)
#define all(v)       v.begin(), v.end()
#define rall(v)      v.rbegin(), v.rend()
#define int          long long
template<typename T>
using vv  = vector<vector<T>>;
using vi  = vector<int>;
using vvi = vector<vector<int>>;
using P   = pair<int, int>;
using ll  = long long;
constexpr ll INF = 1LL << 60;

signed main(){

    int n;
    cin >> n;

    int a = 1000 * (n / 1000 + 1);
    cout << ((a - n) == 1000 ? 0 : a-n) << endl;

    return 0;
}



Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct ii {
    int a, b;
    bool operator < (ii o) const {
        return tie(a, b) < tie(o.a, o.b);
    }
};
struct iii {
    int a, b, c;
    bool operator < (iii o) const {
        return tie(a, b, c) < tie(o.a, o.b, o.c);
    }
};

const int MOD = 1000000007;
const ll INF = 1000000000000000000;
const int MAXN = 1000005;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    ll ans = -INF;
    ans = max(ans, a*c);
    ans = max(ans, a*d);
    ans = max(ans, b*c);
    ans = max(ans, b*d);
    cout << ans << "\n";
}


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

int main(){
  int A,B;
  cin >> A >> B;
  if(A<=B){
    for(int i=0;i<B;i++){
      cout << A;
    }
    cout << endl;
  }
  else{
    for(int i=0;i<A;i++){
      cout << B;
    }
    cout << endl;
  }
}
    

Measured memory_bytes: 3608
#include<stdio.h>
int R=1,C=1,H[2000010],N[2000010];
//評価関数（いまはMAX）
int hyouka(int a,int b){
  if(C<b)return 1;
  if(C<a||b==0)return 0;
  return N[H[a]]<N[H[b]]?1:0;
}
//挿入関数
void hin(int a){
  int i=C++;
  for(N[H[0]=R]=a;hyouka(0,i/2);i/=2)H[i]=H[i/2];
  H[i]=R++;
}
//取り出す関数
int hout(){
  int rt=H[1],i,j=2,k=H[--C];
  for(i=1;hyouka(i,C);i=j)H[i]=H[j=i*2+1-hyouka(i*2,i*2+1)];
  H[j/2]=k;
  return rt;
}
int ta[100010],to[100010],co[100010],nt[100010],s[100010];
int MAX(int a,int b){return a>b?a:b;}
int f(int n){//printf("in%d\n",n);
  int i,j;
  for(i=ta[n];i+1;i=nt[i])co[to[i]]=f(to[i]);
  R=C=1;
  for(i=ta[n];i+1;i=nt[i])hin(co[to[i]]);//printf("%d %d\n",n,C);
  if(C==1)return 0;
  for(i=0;C-1;i++)s[i]=N[hout()];
  //for(j=0;j<i;j++)printf("%d,",s[j]);printf("\n");
  for(j=1;j<i;j++)s[j]=MAX(s[j-1]+1,s[j]);
  return s[i-1]+1;
}
int main(){
  int n,a,i,j;
  scanf("%d",&n);
  for(i=0;i<n;i++)ta[i+1]=-1;
  for(i=1;i<n;i++){
    scanf("%d",&a);
    to[i]=i+1;
    nt[i]=ta[a];
    ta[a]=i;
  }
  printf("%d\n",f(1));
  return 0;
}


Measured memory_bytes: 4864
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=200000+10;

int n;
string s[maxn];
long long kq;

int main(){
  scanf("%d",&n);
  for(int i=1;i<=n;i++){
    cin>>s[i];
    sort(s[i].begin(),s[i].end());
  }
  sort(s+1,s+n+1);kq=0;int tmp=1;
  //for(int i=1;i<=n;i++) cout<<s[i]<<" ";cout<<endl;
  s[n+1]='0';
  for(int i=2;i<=n+1;i++)
    if (s[i-1]==s[i]) tmp++;
    else{
      kq=kq+1ll*tmp*(tmp-1)/2;
      tmp=1;
    }
  cout<<kq;
}


Measured memory_bytes: 8064
#include<bits/stdc++.h>
using namespace std;
int main ()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	string s;
	cin>>s;
	long long n=s.size(),i,ans=0;
	vector<long long>l(n+1),r(n+1);
	l[0]=0;
	for(i=1;i<=n;i++)
		if(s[i-1]=='<')l[i]=l[i-1]+1;
		else l[i]=0;
	r[n]=0;
	for(i=n-1;i>=0;i--)
		if(s[i]=='>')r[i]=r[i+1]+1;
		else r[i]=0;
	for(i=0;i<=n;i++)
		ans+=max(l[i],r[i]);
	cout<<ans<<'\n';
}


Measured memory_bytes: 8732
//何故かRE

#include <bits/stdc++.h>
using namespace std;
int h,w,i,j;
char s[50][50];
int main(){
  cin>>h>>w;
  for(i=0;i<h;i++){
    for(j=0;j<w;j++){
      cin>>s[i][j];
    }
  }
  int cou=0;
  for(i=0;i<h;i++){
    for(j=0;j<w;j++){
      if(s[i][j]=='#'&&s[i-1][j]!='#'&&s[i+1][j]!='#'&&s[i][j-1]!='#'&&s[i][j+1]!='#'){
      cou++;
      }
    }
  }
  if(cou!=0)cout<<"No"<<endl;
  else cout<<"Yes"<<endl;
  return 0;
}


Measured memory_bytes: 256
<?php
  fscanf(STDIN,"%d %d",$n,$m);
  $h = explode(" ",trim(fgets(STDIN)));

  $good=array_fill(1,$n,true);
  for($i=0; $i<$m; $i++){
    fscanf(STDIN,"%d %d",$a,$b);
    if($h[$a-1] >= $h[$b-1])$good[$b] = false;
    if($h[$a-1] <= $h[$b-1])$good[$a] = false;
  }
  $count=0;
  for($i=1; $i<=$n; $i++){
    if($good[$i]){
      $count++;
    }
  }
  echo $count."\n";


Measured memory_bytes: 27120
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;


int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(12);


    int n;
    long long K;
    cin >> n >> K;

    vector<int> P(n);
    for (int i = 0; i < n; ++i) {
        cin >> P[i];
        --P[i];
    }
    vector<long long> C(n);
    for (int i = 0; i < n; ++i) {
        cin >> C[i];
    }

    long long res = -(1LL << 62);

    vector<bool> visited(n, false);

    vector<int> que(n + 123);
    vector<long long> sums(n * 2 + 123, 0);
    multiset<long long> M;
    multiset<long long> M2;
    for (int i = 0; i < n; ++i) {
        if (visited[i]) {
            continue;
        }
        int sz = 0;
        int x = i;
        while (!visited[x]) {
            visited[x] = true;
            que[sz++] = x;
            x = P[x];
        }

        sums[0] = 0;
        for (int j = 0; j < 2 * sz; ++j) {
            sums[j + 1] = sums[j] + C[que[j % sz]];
        }
        long long total = sums[sz];

        int R = (K - 1) % sz + 1;
        M.clear();
        M2.clear();
        M.insert(0);
        M2.insert(0);

        for (int j = 0, k = -1, l = -1; j < 2 * sz; ++j) {
            while (k + sz < j || k + K < j) {
                auto it = M2.find(sums[k + 1]);
                if (it != M2.end()) {
                    M2.erase(it);
                }
                ++k;
            }
            while (l + R < j) {
                auto it = M.find(sums[l + 1]);
                if (it != M.end()) {
                    M.erase(it);
                }
                ++l;
            }
            assert(M.size() > 0);
            assert(M2.size() > 0);
            {
                long long ans = sums[j + 1] - *M.begin();
                ans += max(0LL, (K - 1) / sz * total);
                res = max(res, ans);
            }
            {
                long long ans = sums[j + 1] - *M2.begin();
                ans += max(0LL, max(0LL, (K - 1) /sz - 1) * total);
                res = max(res, ans);
            }
            M.insert(sums[j + 1]);
            M2.insert(sums[j + 1]);
        }
    }

    cout << res << '\n';

    return 0;
}

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

int main() {
  int h,n;
  cin >> h >> n;
  vector<int> a(n);
  int total = 0;
  for(int i=0; i<n; i++){
    cin >> a[i];
    total += a[i];
  }
  
  if(total<h) cout << "No" << endl;
  else cout << "Yes" << endl;
}

Measured memory_bytes: 640