akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;

int n, m, a[50], b[50];
bool graph[50][50], v[50];

void dfs(int s) {
    v[s] = true;
    for (int g = 0; g < n; g++) {
        if (graph[s][g] && !v[g]) dfs(g);
    }
}

int main(void) {
    int ans = 0;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> a[i] >> b[i];
        a[i]--, b[i]--;
        graph[a[i]][b[i]] = graph[b[i]][a[i]] = true;
    }
    for (int i = 0; i < m; i++) {
        graph[a[i]][b[i]] = graph[b[i]][a[i]] = false;
        for (int j = 0; j < n; j++) v[j] = false;
        dfs(0);
        bool flag = false;
        for (int j = 0; j < n; j++) if (!v[j]) flag = true;
        if (flag) ans++;
        graph[a[i]][b[i]] = graph[b[i]][a[i]] = true;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(){

  int x,y,k,i,j,v;

  scanf("%d%d",&x, &y);


  if(x>=y){
    if(x==y) v=x;

    k=x%y;
      for(i=1;i<=k;i++){
	if(y%i==0 && k%i==0) v=i;
    }
  }
  
  else if(y>x){
    k= y%x;
    for(i=1;i<=k;i++){
      if(x%i==0 && k%i==0) v=i;
    }
  }

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

  return 0;
}


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

int main(){
  int num; cin >> num;
  int d[num];
  for(int i=0;i<num;i++){
    cin >> d[i];
  }
  int total = num * (num-1) / 2;
  int ret = 0;
  
  for(int i=0;i<num; i++){
    for(int j=i+1;j<num;j++){
      //cout << d[i] << " " << d[j] << endl;
      ret +=(d[i] * d[j]);
    }
  }
  cout << ret << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define itrfor(itr,A) for(auto itr = A.begin(); itr !=A.end();itr++)
typedef long long llong;
char moji[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
char moji2[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
char moji3[10]={'0','1','2','3','4','5','6','7','8','9'};
#define Sort(a) sort(a.begin(),a.end());
#define Reverse(a) reverse(a.begin(),a.end());
#define n_max int(1e5)


int main(){
    int n;
    cin >> n;
    llong ans1=0,ans2=0,tmp,wa=0;
    llong A[n_max+5];
    REP(i,n) scanf("%lld",&A[i]);

    REP(i,n){
        wa+=A[i];
        if(i%2==0){
            ans1 += max(llong(0), 1 -wa);
            wa = max( wa,llong(1));
        }
        else{
            ans1+= max(llong(0),wa + 1);
            wa = min(-llong(1),wa);
        }
    }

    wa=0;
    REP(i,n){
        wa+=A[i];
        if(i%2==1){
            ans2 += max(llong(0), 1 -wa);
            wa = max( wa,llong(1));
        }
        else{
            ans2+= max(llong(0),wa + 1);
            wa = min(-llong(1),wa);
        }
    }
    cout << min( ans1,ans2) << endl;


}

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

string A;

int main() {
    cin >> A;
    vector<int> cnt(26);
    long long N = A.length();
    long long ans = (N + 1) * N / 2 + 1 - N;
    for (int i = 0; i < N; i++) {
        cnt[A[i] - 'a']++;
    }
    for (int i = 0; i < 26; i++) {
        ans -= 1LL * cnt[i] * (cnt[i] - 1) / 2;
    }
    cout << ans << endl;
}




Measured memory_bytes: 640
import java.util.*;

public class Main {

    /* チェックリスト
     * intの範囲を超えていないか
     * TLEしそうな処理の有無
     */
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        String[] ints = sc.nextLine().split(" ");
        int a = Integer.parseInt(ints[0]);
        int b = Integer.parseInt(ints[1]);
        if(a - b * 2 < 0){
            System.out.println(0);
        }else{
            System.out.print(a - b * 2);
        }
    }
}

Measured memory_bytes: 21972
#include <iostream>
#include <list>
#include <algorithm>
#include <map>
#include <math.h>
#include <set>
#include <string>
#include <algorithm>
#include <list>
#include <string.h>
#include <unordered_map>
#include <ctype.h>
#include <queue>
#include <numeric>
#include <vector>
#include <iomanip>
#include <cstdlib>
#include <stack>
#include <ctime>
#define  lld long long int
#define rep(i,start,end) for(lld i = start;i<end;i++)
#define newline cout << endl
#define fastio ios:: sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define pb push_back
#define in insert
#define mp make_pair
#define se second
#define fi first
#define starttime chrono::time_point<chrono::system_clock> start, end; start = chrono::system_clock::now()
#define showtime end = chrono::system_clock::now();  chrono::duration<double> elapsed_seconds = end - start; time_t end_time = chrono::system_clock::to_time_t(end); cout << "elapsed time: " << elapsed_seconds.count() << "s\n"
#define INF 1e17
lld MOD =  (lld)(1e9+7);
#define mh make heap
#define ph push_heap
#define poph pop_heap
#define openf   freopen("input.txt", "rt", stdin); freopen("output.txt", "wt", stdout);
using namespace std;
lld add(long long a, long long b){return ((a%MOD)+(b%MOD))%MOD;}
lld mul(long long a, long long b){return ((a%MOD)*(b%MOD))%MOD;}
lld sub(long long a, long long b){lld ans = ((a%MOD-b%MOD))%MOD; if(ans<0) ans += MOD; return ans;}
lld modInverse(lld a ){   lld m = MOD,m0 = m, y = 0, x = 1;  if (m == 1) return 0;   while (a > 1) {  lld q = a / m, t = m;  m = a % m, a = t, t = y;          y = x - q * y, x = t;   } if (x < 0)  x += m0; return x; } 
lld gcd(lld a, lld b){if (b == 0) return a; return gcd(b, a % b);}
void MAIN(lld i,lld t);
int get(){lld t;cin>>t; ; return t;}
int log(string name){cout<<name<<endl; return 0;}
void test(int t) { for(lld i = 0;i<t;i++){MAIN(i,t); cout <<endl;} }
lld power(lld x, lld y) { lld res = 1; x = x%MOD; if(x==0) return 0;   while (y > 0) {   if (y & 1)      res = (res*x)%MOD; y = y>>1; x = (x*x)%MOD;} return res; }
#define all(v) (v).begin(),(v).end()
lld popcount(lld x){return __builtin_popcount(x);}
lld lcm(lld a,lld b){ return (a*b)/gcd(a,b);}
lld n,x;
vector<lld> v;
void MAIN(lld current_test_case,lld total_test_cases){
    cin >> n;
    cout << (lld)1000*ceil(1.0*n/1000)- n; 
}   
int main(){  
    fastio;
    #ifndef ONLINE_JUDGE 
     openf
    #endif
    test(1);
    return 0;
}


Measured memory_bytes: 3832
def main():
    a,b,k = map(int,input().split())
    if a >= k:
        print(str(a-k)+" "+str(b))
    elif a+b <= k:
        print("0 0")
    else:
        print("0 "+str(b+a-k))
        
if __name__ == '__main__':
    main()

Measured memory_bytes: 38384
sa = input()
sb = input()
sc = input()

a, b, c = 0, 0, 0
t = sa[a]
a += 1

while True:
    if t == 'a':
        if a == len(sa): break
        t = sa[a]
        a += 1
    elif t == 'b':
        if b == len(sb): break
        t = sb[b]
        b += 1
    else:
        if c == len(sc): break
        t = sc[c]
        c += 1
print(t.upper())
    

Measured memory_bytes: 3064
#include <iostream>
using namespace std;
int main(void){
    int a,b;
    char op;
    while(true){
        cin >> a >>  op >> b;
        if(op == '?'){
            break;
        }
        if(op == '+'){
            cout << (a+b) << endl;
        }
        if(op == '-'){
            cout << (a-b) << endl;
        }
        if(op == '*'){
            cout << (a*b) << endl;
        }
        if(op == '/'){
            cout << (a/b) << endl;
        }
    }
}



Measured memory_bytes: 3096
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
#include <functional>

using namespace std;

int main()
{
	int a, b;
	cin >> a >> b;
	cout << a * b << " " << 2 * a + 2 * b << endl;
	return 0;
}

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

using namespace std;

#define intt long long
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const int N = 100005;

int n;
int a[N];

bool check (int n) {
	bool a = false, b = false, c = false;
	while (n > 0) {
		if (n % 10 == 3) a = true;
		else if (n % 10 == 5) b = true;
		else c = true;
		n /= 10;
	}
	return (a && b && c);
}

int main() {

	FAST;

	cin >> n;
	queue <int> q;
	int ans = 0;
	q.push(0);
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		intt a = 1LL * x * 10 + 3;
		intt b = 1LL * x * 10 + 5;
		intt c = 1LL * x * 10 + 7;
		if (a <= 1LL * n) {
			q.push(a);
			if (check(a)) ans ++;
		}
		if (b <= 1LL * n) {
			q.push(b);
			if (check(b)) ans ++;
		}
		if (c <= 1LL * n) {
			q.push(c);
			if (check(c)) ans ++;
		}
	}
	cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 384
#include <cstring>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;

const int MX = 3000;

double memo[MX][MX];
bool seen[MX][MX];

double solve(int idx, int a, vector<double>& probs) {
  if ( idx == probs.size() ) return a > idx / 2;
  if ( seen[idx][a] ) return memo[idx][a];
  
  double answer = 0;
  answer += solve(idx + 1, a, probs) * ( 1 - probs[idx] );
  answer += solve(idx + 1, a + 1, probs) * ( probs[idx] );
  
  seen[idx][a] = true;
  return memo[idx][a] = answer;
}

int main() {
  int n;
  cout << fixed << setprecision(12);
  while ( cin >> n ) {
    memset(seen, 0, sizeof seen);
    vector<double> probs(n);
    for ( auto& i : probs ) cin >> i;
    cout << solve(0, 0, probs) << endl;
  }
  return 0;
}

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

using namespace std;
using ll = long long;

int main()
{
    int n;
    cin >> n;
    vector<int> a(n + 1), b(n);
    for (int i = 0; i <= n; i++){
        cin >> a[i];
    }
    for (int i = 0; i < n; i++){
        cin >> b[i];
    }
    ll ans = 0;
    for (int i = 0; i < n; i++){
        if (b[i] > a[i]){
            ans += a[i];
            b[i] -= a[i];
            ans += min(a[i + 1], b[i]);
            a[i + 1] -= min(b[i], a[i + 1]);
        } else {
            ans += min(a[i], b[i]);
        }
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
#include<map>
#include<bitset>
using namespace std;

typedef long long ll;
#define rep(i, n) for(int i = 0;i < (n);i++)
#define repr(i, n) for(int i = (n);i >= 0;i--)
#define repf(i, m, n) for(int i = (m);i < (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;}
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
//////////////////////////////////////////////////


int main() {
    ll x; cin >> x;
    ll a = 100;
    int ans = 0;
    while (a < x) {
        a *= 1.01;
        // cout << a << endl;
        ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3632
# -*- coding:utf-8 -*-
import bisect
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
ans = 0
a.sort()
b.sort()
c.sort()
for tmp in range(n):
    ans += bisect.bisect_left(a,b[tmp])*(n-bisect.bisect_right(c,b[tmp]))
print(ans)

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

int main(){
    int n, x, t;
    cin >> n >> x >> t;
    int ans = n / x * t;
    if(n % x != 0){
        ans+= t;
        cout << ans << endl;
    }
    else cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3592
N,W=map(int,input().split())
v=[0]*1010
w=[0]*1010
for i in range(1,N+1):
    x,y=map(int,input().split())
    v[i]=x
    w[i]=y
    
a=[[0 for i in range(W+1)]for j in range(N+1)]
a[0][W]=0
for i in range(1,N+1):
    for j in range(1,1+W):
        if w[i]<=j:
            a[i][j]=max(a[i-1][j-w[i]]+v[i],a[i-1][j])
        else:
            a[i][j]=a[i-1][j]
print(a[N][W])


Measured memory_bytes: 42468
#include<cstdio>
#include<algorithm>
using namespace std;
char p[30];
int n, v[30];
int main() {
	int i, ck = 0, j, k;
	scanf("%s", p);
	for (i = 0; p[i]; i++) {
		v[p[i] - 'a'] = 1;
		if (p[i] + i != 'z') {
			ck = 1;
		}
	}
	n = i;
	if (n != 26) {
		for (i = 0; i < 26; i++)if (!v[i])break;
		p[n] = i + 'a';
		printf("%s\n", p);
		return 0;
	}
	if (ck == 0) {
		printf("-1\n");
		return 0;
	}
	for (i = n - 1; i >= 0; i--) {
		for (j = 0; j < 26; j++)v[j] = 0;
		for (j = 0; j < i; j++) {
			v[p[j] - 'a'] = 1;
		}
		for (j = p[i] - 'a' + 1; j < 26; j++) {
			if (!v[j]) {
				v[j] = 1;
				p[i] = 'a' + j;
				p[i + 1] = 0;
				printf("%s\n", p);
				return 0;
			}
		}
	}
}

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

int main(void) 
{
    int k;
    cin >> k;

    //ルンルン数を入れる配列
    vector<ll> a;

    //1から9まではルンルン数
    for(int i = 1; i < 10; i++) a.push_back(i);

    while(1)
    {
        if(k <= a.size())
        {
            cout << a[k-1] << endl;
            return 0;
        }
        //kを更新
        k -= a.size();
        vector<ll> old;
        swap(old, a);
        
        //順に取り出す
        for(ll x : old)
        {
            //-1, 0, 1を末尾に付け足すとルンルン数
            for(int i = -1; i <= 1; i++)
            {
                int d = x%10 + i;
                if((d < 0) || (d > 9)) continue;
                ll target = 10 * x +d;
                a.push_back(target);
            }
        }
    }
    return 0;
}

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

const int INF=(1<<21);

int n;
int dp[105][105], p[105];

void matrixChainMultiplication(){
    for(int i=1; i<=n; i++) dp[i][i]=0;

    for(int l=2; l<=n; l++){
        for(int i=1; i<=n-l+1; i++){
            int j=i+l-1;
            dp[i][j]=INF;
            for(int k=i; k<=j-1; k++){
                dp[i][j]=min(dp[i][j], dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j]);
            }
        }
    }
}

int main(void){
    cin >> n;
    for(int i=0; i<n; i++){
        int a,b; cin >> a >> b;
        if(i==0){
            p[0]=a, p[1]=b;
        }
        else p[i+1]=b;
    }

    matrixChainMultiplication();

    cout << dp[1][n] << endl;
}


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

int main(){
  int n,k;
  scanf("%d%d",&n,&k);
  double ret=0;
  for(int i=1; i<n+1; i++){
    double a=1.0/n;
    int now=i;
    while(now<k){
      now*=2;
      a/=2;
    }
    ret+=a;
  }
  printf("%.12f\n",ret);
  
}

Measured memory_bytes: 256
def main():
    n, *x = map(int, open(0).read().split())
    y = sorted(x)
    a, b = y[n // 2 - 1], y[n // 2]
    ans = ""
    f = lambda i: str(b) if i <= a else str(a)
    *c, = map(f, x)
    ans = '\n'.join(c)
    print(ans)


if __name__ == '__main__':
    main()


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

int main(){

	long long n; cin >> n;
	// if(!n) break;
	int ans = 0;
	for(int i=1; i<21; i++){
		long long a = powl(2, i);
		long long b = powl(3, i);
		if(a <= n && n <= b){
			ans = i;
			break;
		}
	}

	cout << ans << endl;

	return 0;
}



Measured memory_bytes: 3340
#include <iostream>
#include <string>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <cmath>
#define rep(i,n) for(int i=0; i<n; i++)
using namespace std;
int main()
{
	long long int i;
	long long int n, sum=0;
	cin >> n;
	for(i=1; i<=n; i++){
		if(i%3 != 0 && i%5 != 0){
			sum += i;
		}
	}
	cout << sum <<endl;
	return 0;
}

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

int main() {
    int n, m;
    cin >> n >> m; 
    vector<int> a(n);
    rep(i,m) {
        int k;
        cin >> k;
        rep(j,k) {
            int s;
            cin >> s;
            s--;
            a[s] |= 1 << i;
        }
    }
    int p = 0;
    rep(i,m) {
        int P;
        cin >> P;
        p |= P<<i;
    }
    int ct = 0;
    rep(i,1<<n) {
        int t = 0;
        rep(j,n) {
            if (i>>j&1) t ^= a[j];
        }
        if (p == t) ct++;
    }
    cout << ct << endl;
}

Measured memory_bytes: 256
#include<stdio.h>

void swap(int *a, int *b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

int bubblesort(int A[], int N)
{
    int count = 0;
    for (int i = 0; i < N; i++)
    {
        for (int j = N - 1; j > i; j--)
        {
            if (A[j] < A[j - 1])
            {
                swap(&A[j], &A[j-1]);
                count++;
            }
        }
    }
    return count;
}

int main()
{
    int A[100], N;
    int count = 0;
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &A[i]);
    }

    count = bubblesort(A, N);
    
    for (int i = 0; i < N; i++)
    {
        if (i > 0) printf(" ");
        printf("%d", A[i]);
    }
    printf("\n");
    printf("%d\n", count);
    return 0;
}



Measured memory_bytes: 2040
#include <iostream>
#include <math.h>
#include <algorithm>
#include <functional> 
#include <string>
#include <vector>

#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <utility>

using namespace std;

typedef long long LL;

#define dump(c) { for (auto it = c.begin(); it != c.end(); ++it) if (it == c.begin()) cout << *it; else cout << ' ' << *it; cout << endl; } 
#define rep(i,n) for (int i = 0; i < (n); ++i)

const int MOD = 1000000007;

int main()
{
    map<string, map<int, int, greater<int>>> c2p2r;
    int N;
    cin >> N;
    rep(i, N) {
        string S;
        int P;
        cin >> S >> P;
        c2p2r[S][P] = (i+1);
    }

    for (auto it : c2p2r) {
        for (auto it2: it.second) {
            cout << it2.second << endl;
        }
    }

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#define rep(i, n) for(int i = 0; i < n; i++)
#define reps(i, s, n) for(int i = s; i < n; i++)
using namespace std;
int main(void) {
    int n, k;
    cin >> n >> k;
    int x[n];
    rep(i, n) cin >> x[i];

    int c = 1e9;
    rep(i, n-k+1) {
        int xl = abs(x[i]), xr = abs(x[i+k-1]);
        int ci = 0;
        if (x[i]>0 xor x[i+k-1]>0)
            ci = xl + xr + min(xr, xl);
        else 
            ci = max(xr, xl);
        c = min(c, ci);
    }

    cout << c << endl;

}



Measured memory_bytes: 640
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		char[] s = sc.next().toCharArray();
		
		for(int i=0;i<s.length;i++) {
			s[i] = 'x';
		}
		
		System.out.println(s);
	}
}


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

int main(void){
    string s;
    int cnt=0;
    int ret=0;
    cin>>s;
    for(int i=0;i<s.size();i++){
        if(s[i] == 'A' || s[i] == 'C' || s[i] == 'G' || s[i] == 'T'){
            cnt++;
            if(ret<cnt) ret = cnt;
        }
        else
            cnt=0;
            
    }
    cout<<ret<<endl;

    return 0;
}

Measured memory_bytes: 256
n = int(input())
A = [int(i) for i in input().split()]
dp = [0] * n

for i in range(1, n):
    dp[i] = dp[i - 1] + abs(A[i] - A[i - 1])
    if i > 1:
        dp[i] = min(dp[i], dp[i - 2] + abs(A[i] - A[i - 2]))
    
print(dp[-1])

Measured memory_bytes: 13928
# -*- coding: utf-8 -*-

H, W, K = map(int, input().split())
c = [[0] * W for x in range(H)]
for i in range(H):
    c[i] = input()

h_l = [i for i in range(H)]
w_l = [i for i in range(W)]

ans = 0
for i in range(2 ** H):
    for j in range(2 ** W):
        count = 0
        for h in range(H):
            for w in range(W):
                if ((i >> h) & 1) and ((j >> w) & 1):
                    if c[h][w] == "#":
                        count += 1
        if count == K:
            ans += 1

print(ans)


Measured memory_bytes: 9128
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep_inv(i, n, m) for(int i = (int)(n); i > (int)(m); i--)
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vc = vector<char>;
using vvl = vector<vl>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using vpii = vector<pll>;

int main(){
  ll N, K;
  cin >> N >> K;
  vl p(N);
  rep(i, N){
    cin >> p[i];
  }

  double expect = 0.0;
  rep(i, K){
    expect += ((double)p[i] + 1.0) / 2.0;
  }

  if(K < N){
    double tmp = expect;

    rep2(i, K, N){
      tmp = tmp + ((double)p[i] + 1.0) / 2.0 - ((double)p[i - K] + 1.0) / 2.0;
      if(tmp > expect){
		expect = tmp;
      }
    }
  }

  cout << setprecision(10) << expect << endl;
  
  return 0;
}


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

int main(){
	int n; cin >> n;
	int ga[n][n];
	memset(ga, 0, n*n*sizeof(int));
	rep(i, n){
		int u, k; cin >> u >> k;
		rep(j, k){
			int v; cin >> v;
			ga[u-1][v-1] = 1;
		}
	}

	rep(i, n)rep(j, n) cout << ga[i][j] << char((j == n-1)?'\n':' ');
	return 0;
}



Measured memory_bytes: 3136
character(5000) :: s
integer :: k,lens
character(5),allocatable :: store(:)
character(5) :: ans
integer :: i,j,kk,l
read *,s
read *,k
lens = len_trim(s)
allocate(store(k*lens))

kk = 0
do i  = 1, lens
   do j = 0, k-1
      l = i + j
      if (l > lens) exit
      kk = kk + 1
      store(kk) = s(i:l)
   enddo
enddo

call cs11(kk, store)

i = 1
j = 1
ans = store(1)
do while (i < k)
   j = j + 1
   if (store(j) /= ans) then
      i = i + 1
      ans = store(j)
   endif
enddo

print '(a)',ans
stop

contains

subroutine cs11(Ncomb,a)
   integer, intent(in) :: Ncomb
   character(5), intent(inout) :: a(Ncomb)
   integer :: icomb, jcomb
   character(5) :: rswp
   logical :: flg_swp

   icomb = Ncomb
   flg_swp = .false.
   do while (icomb > 1 .or. flg_swp)
      icomb = (icomb * 10) / 13
      if (icomb < 1) then
         icomb = 1
      else if (icomb == 9 .or. icomb == 10) then 
         icomb = 11
      endif
      flg_swp = .false.
      do jcomb = 1, Ncomb-icomb
         if (a(jcomb) > a(jcomb+icomb)) then
            rswp = a(jcomb) 
            a(jcomb) = a(jcomb+icomb)
            a(jcomb+icomb) = rswp
            flg_swp = .true.
         endif
      enddo
   enddo
endsubroutine cs11
end

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

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

    int ans = a*x+b*y;
    for(int i = 1; i < max(x,y)+1; i++){
        ans = min(max((x-i),0)*a+max((y-i),0)*b+2*i*c,ans);
    }

    cout << ans << endl;
    return 0;

}


Measured memory_bytes: 256
A, B, C, D, E, F = map(int, input().split())

w = set()
for i in range(F // (100 * A) + 1):
    for j in range(F // (100 * B) + 1):
        a = (A * i + B * j) * 100
        if a < F:
            w.add(a)
w.remove(0)

s = set()
t = E * F // 100
for i in range(t // C + 1):
    for j in range(t // D + 1):
        b = C * i + D * j
        if b < t:
            s.add(b)

best_concentration = -1
best_a = -1
best_b = -1
for a in w:
    for b in sorted(s):
        if a + b > F:
            break
        if b > E * a // 100:
            break
        concentration = 100 * b / (a + b)
        if concentration > best_concentration:
            best_concentration = concentration
            best_a = a
            best_b = b
print(best_a + best_b, best_b)


Measured memory_bytes: 3188
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
int main(int argc, char const *argv[]) {
    int n, h ,w;
    cin >> n >> h >> w;
    cout << (n-h+1)*(n-w+1) << std::endl;
    return 0;
}

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

int main() {
	int N, i, ano = 0;
	long A[200005] = {};
	cin >> N;
	for (i = 0;i < N;i++) {
		cin >> A[i];
	}

	sort(A, A + N);

	for (i = 0; i < N - 1;i++) {
		if (A[i] == A[i + 1]) {
			ano = 1;
		}
	}

	if (ano == 0) {
		cout << "YES";
	}
	else {
		cout << "NO";
	}
}

Measured memory_bytes: 1792
#include <stdio.h>

int main(){
  int a,b,c,tmp;
    
  scanf("%d%d%d",&a,&b,&c);
    
  if(a>b) {
    tmp = a;
    a = b;
    b =tmp;
  }
  
  if(b>c) {
    tmp = c;
    c = b;
    b =tmp;
  }
    
  if(a>b) {
    tmp = a;
    a = b;
    b =tmp;
  }
    
    
    
     printf("%d %d %d\n",a,b,c);
    
    return 0;
}



Measured memory_bytes: 2072
N,M=map(int,input().split())
List = []
for i in range (N):
  List.append(list(map(int, input().split())))
List.sort()
res = 0
num = 0
i = 0
while num < M:
  if List[i][1] != 0:
    pass
  else:
    i +=1
  num += 1
  res += List[i][0]
  List[i][1] += -1
print(res)

Measured memory_bytes: 27456
#include <stdio.h>


int main(){
	int n, aux;
	scanf("%i", &n);
	aux=n;
	while(n>0){
		if(n%2==0){
			if(n%aux==0){
				printf("%i\n", n);
				return 0;
			}
			else
				n=n+2;

		}
		else
			n++;
	}
	
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
#define ll long long
#define debug(a) cout<<a<<endl
#define pii pair<ll,ll>
#define INF (int) 1e9+7
#define maxn 109
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    ll aant=a;
    ll ansc=0;
    ll ansd=0;
    if(a%c!=0)a+=((c*(a/c+1))-a);
    if(a<=b)ansc=(b-a)/c+1;
    a=aant;
    if(a%d!=0)a+=((d*(a/d+1))-a);
    if(a<=b)ansd=(b-a)/d+1;
    ll mm=c*d/__gcd(c,d);
    a=aant;
    if(a%mm!=0)a+=((mm*(a/mm+1))-a);
    ll tir=0;
    if(a<=b)tir=(b-a)/mm+1;
    a=aant;
    cout<<(b-a+1)-ansc-ansd+tir<<endl;
    return 0;
}
///usar double sempre ou long double
///pensar em casos que coisas dao negativas
///N esquecer de limpar as coisas em quest de varios testes
///OLHAR A COMPLEXIDADE PRA VER SE N PASSA POR BRUTE FORCE OU BRUTE FORCE COM ALGUMAS OTIMIZACOES



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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int k,n;
	cin>>k>>n;
	vector<int>a(n);
	for(auto&i:a)cin>>i;
	sort(a.begin(),a.end());
	int64_t ans=0,last;
	for(int i=1;i<n;++i)ans=max(ans,(int64_t)a.at(i)-a.at(i-1));
	last=min(a.back()-a.front(),a.front()+k-a.back());
	ans=max(ans,last);
	cout<<k-ans<<"\n"s;
}

Measured memory_bytes: 1024
from collections import deque
from functools import reduce

d = int(input())
cl = [int(i) for i in input().split()]

sm = []
for _ in range(d):
  sm.append([int(i) for i in input().split()])
sd = deque(sm)

tl = []
for _ in range(d):
  tl.append(int(input()))

hold = [0] * 26
satisfy = 0
for t, num in enumerate(tl):
  hold[num-1] = t + 1
  sl = sd.popleft()
  satisfy += sl[num - 1]
  satisfy -= sum([i * j for i, j in zip(cl, [t - j + 1 for j in hold])])
  print(satisfy)



Measured memory_bytes: 9904
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<pair<int, int> > vpii;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef vector<ll> vll;
#define INF 0x3f3f3f3f
#define MOD 998244353LL
#define EPSILON 0.00001
#define f first
#define s second
#define pb push_back
#define mp make_pair
 
#define FOR(i, a, b) for (ll i=(a); i<=(signed)(b); i++)
#define F0R(i, a) for (ll i=0; i<(signed)(a); i++)
#define RFOR(i, a, b) for (int i=(a); i >= b; i--)

#define MN 105
int dp[MN][MN];

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

    int n, m;
    cin >> n >> m;
    cout << n*(n-1)/2+m*(m-1)/2 << "\n";

    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
#define INF 9223372036854775807
#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define RFOR(i,a,b) for(long long i = (b-1);i>=a;i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<P> Graph;

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

  string s;
  int n;
  cin >> s >> n;
  
  int cnt = 0;
  while(cnt < s.size()){
    cout << s[cnt];
    cnt += n;
  }

  return 0;
}


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

const int INF = 1e9;

bool compare(pair<int,int> p1, pair<int,int> p2){
  return p1.second>p2.second;
}
int main() {
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++) cin>>a[i];

  pair<int,int> cnt1[(int)1e5+1];
  pair<int,int> cnt2[(int)1e5+1];
  for(int i=0;i<(int)1e5+1;i++){
    cnt1[i]=make_pair(i,0);
    cnt2[i]=make_pair(i,0);
  }
  for(int i=0;i<n/2;i++){
    ++cnt1[a[2*i]].second;
    ++cnt2[a[2*i+1]].second;
  }
  sort(cnt1,cnt1+(int)(1e5+1),compare);
  sort(cnt2,cnt2+(int)(1e5+1),compare);
  if(cnt1[0].first!=cnt2[0].first){
    cout<<n-cnt1[0].second-cnt2[0].second<<endl;
  }else{
    cout<<n-max(cnt1[0].second+cnt2[1].second,cnt1[1].second+cnt2[0].second)<<endl;
  }
}

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

int main(){
	long long N , X , ans; cin >> N >> X; ans = N;
	long long P = X , Q = N - X;
	while(Q){ans += (P / Q * 2 - !(P % Q)) * Q; P %= Q; swap(P , Q);}
	cout << ans; return 0;
}


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

long long int n,m;
vector<long long int>a[100001];
bool vis[100001];
long long int save[100001];
long long int dis[100001];

void dfs(long long int s)
{
    vis[s]=true;
    for(int k=0;k<a[s].size();k++)
    {
        if(!vis[a[s][k]])
        {
            dfs(a[s][k]);
        }
        save[s]=max(save[s],1+save[a[s][k]]);

    }
}
int main()
{
    cin>>n>>m;
    long long int i,j,k,x,y,ans=0;
    for(i=0;i<m;i++)
    {
        cin>>x>>y;
        a[x].push_back(y);
    }
    for(i=1;i<=n;i++)
    {
        if(!vis[i])
        {
         dfs(i);
        }
    }
    for(i=1;i<=n;i++)
    {
        ans=max(ans,save[i]);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 8704
#include "bits/stdc++.h"
using namespace std;

int main() {
	long long N, M;
	cin >> N >> M;
	vector<long long> ANS(N, -1);
	for (int i = 0; i < M; i++) {
		long long S, C;
		cin >> S >> C;
		S--;
		if (ANS[S] >= 0 && ANS[S] != C) {
			cout << -1 << endl;
			return 0;
		}
		ANS[S] = C;
	}
	if (N == 1) {
		if (ANS[0] == -1) cout << 0 << endl;
		else cout << ANS[0] << endl;
		return 0;
	}
	if (ANS[0] == 0) {
		cout << -1 << endl;
		return 0;
	}
	for (int i = 0; i < N; i++) {
		if (ANS[i] == -1) {
			if (i == 0) cout << 1;
			else cout << 0;
		}
		else cout << ANS[i];
	}
	cout << endl;
}

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

int main(){
    int n;
    cin >> n;
    vector<int> a(3*n);
    for (int i = 0; i < 3*n; i++) cin >> a[i];
    sort(a.begin(), a.end(), greater<int>());
    long long ans = 0;
    for (int i = 1; i < 2*n; i += 2) ans += a[i];
    cout << ans << endl;
}


Measured memory_bytes: 1408
#include<iostream>
#include<vector>

int main(){
    long long int N,K;
    std::cin >> K >> N;
    std::vector<long long int> V(N,0);
    std::vector<long long int>D(N,0);
    for( int i=0;i<N;i++){
        std::cin>>V[i];
    }

    for (int i=0;i<N-1;i++){
        D[i] = V[i+1]-V[i];
    }
    D[N-1] = K - (V[N-1]-V[0]);
    std::cout<<K - *std::max_element(D.begin(),D.end())<<std::endl;
    return 0;
}


Measured memory_bytes: 3456
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <limits>

using namespace std;

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

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

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define EXISTch(s,c) ((((s).find_first_of(c)) != std::string::npos)? 1 : 0)//cがあれば1 if(1)
#define SORT(c) sort((c).begin(),(c).end())

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18

int main() {

	string s; cin >> s;
	
	if (s == "Sunny")cout << "Cloudy" << endl;
	if (s == "Cloudy")cout << "Rainy" << endl;
	if (s == "Rainy")cout << "Sunny" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int64_t,int64_t> pll;
typedef vector<int64_t> vl;
int dx[]={1,-1,0,0,1,-1,1,-1};
int dy[]={0,0,1,-1,1,-1,-1,1};
const long double PI = acos(-1);
#define INF (2147483647)
#define mod (1000000007)
#define limit (7368791)
#define rep(i,a,b) for (int64_t i = (a); i < (b); i++)
#define REP(i,n) rep(i,0,n)
#define sz(s) (s).size()
#define ALL(a) begin(a),end(a)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define fi first
#define se second

void solve() 
{
    string s;cin>>s;int ans=0;
    REP(i,s.size()/2){
        if(s[i]!=s[s.size()-1-i])ans++;
    }cout<<ans<<endl;
}

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


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    int a, b, c=0;
    char brd[100][100];
    cin>>a>>b;
    for (int i=0; i<100; i++)
    {
        for (int j=0; j<100; j++)
        {
            if (i<50) brd[i][j]='#';
            else brd[i][j]='.';
        }
    }
    for (int i=0; i<50; i++)
    {
        for (int j=0; j<100; j++)
        {
            if (i%2==0 && j%2==1 &c<a-1)
            {
                brd[i][j]='.';
                c++;
            }
        }
    }
    c=0;
    for (int i=51; i<100; i++)
    {
        for (int j=0; j<100; j++)
        {
            if (i%2==0 && j%2==1 && c<b-1)
            {
                brd[i][j]='#';
                c++;
            }
        }
    }
    cout<<"100 100\n";
    for (int i=0; i<100; i++)
    {
        for (int j=0; j<100; j++) cout<<brd[i][j];
        cout<<'\n';
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
#define pb push_back
#define ld long double
#define f first
#define s second
#define in insert
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int INF = 1e18 + 5;
const int mod = 1e9 + 7;
const int  N = 2e5 + 314;
const long double pi = 3.1415926535897932384626433832795;
void solve(){
    int n;
    string s;
    cin>>n>>s;
    int cntr=0, ans=0;
    for(int i = 0; i < n; i++)cntr+=(s[i]=='R');
    for(int i = 0; i < cntr; i++){
        if(s[i]!='R')ans++;
    }   
    cout<<ans;
}
signed main(){
    speed;
    int t=1;
    //cin>>t;
    while(t--)solve();
}

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

#define int long long
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rep1(i,n) for(int i=1;i<=(int)(n);++i)
#define rep11(i,n) for(int i=1;i<(int)(n);++i)
#define repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define repm(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define sperase(v,n) (v).erase(remove(all(v), n), (v).end())
#define vdelete(v) (v).erase(unique(all(v)), (v).end())
#define pb(n) push_back(n)
#define mp make_pair
#define MOD 1000000007
#define INF 9223372036854775807

string s;
int ans[13],memo=1;

signed main() {
    cin >> s;
    ans[0]++;
    repm(i,s.size()) {
        if(s[i] == '?') {
            int anstmp[13]={};
            rep(j,10) {
                int tmp = memo*j%13;
                rep(k,13) {
                    anstmp[k] += ans[(k-tmp+13)%13];
                    anstmp[k] %= MOD;
                }
            }
            rep(k,13) ans[k] = anstmp[k]%MOD;
        } else {
            int tmp = s[i]-'0',anstmp[13]={};
            tmp = (memo*tmp)%13;
            rep(j,13) anstmp[j] = ans[(j-tmp+13)%13];
            rep(j,13) ans[j] = anstmp[j];
        }
        memo = (memo*10)%13;
    }
    cout << ans[5]%MOD << endl;
}





Measured memory_bytes: 512
a = [list(input()) for _ in range(5)]
b = [int(''.join(a[i])) for i in range(len(a))]
c = []
h = 10
y = 0
for i in range(5):
    if 0 < int(a[i][-1]) <= h:
        h = int(a[i][-1])
        y = a.index(a[i])
r = b[y]
b[y] = 0
for i in range(5):
    while b[i] % 10 != 0:
        b[i] += 1

print(sum(b) + r)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main(){
  vector<char> s(3);
  for(int i=0; i<3; ++i) cin >> s[i];
  sort(s.begin(), s.end());
  if(s[0] == 'a' && s[1] == 'b' && s[2] == 'c') cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

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

using namespace std;

double x[1004];
double y[1004];

#define PI 3.14159265358979323

int main(void){
  double px, py;
  double arg;

  px = 1;
  py = 0;
  for(int i=0;i<1003;i++){
	arg = atan(py / px);
	if(px < 0) arg += PI;
	arg += PI/2;
	px += cos(arg);
	py += sin(arg);
	x[i] = px;
	y[i] = py;
  }
  int n;
  while(cin >> n){
	if(n == -1) break;
	cout << x[n-2] << endl;
	cout << y[n-2] << endl;
  }
}

Measured memory_bytes: 0
/*package whatever //do not write package name here */
import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
	public static void main (String[] args) {
// 		System.out.println("GfG!");
        Scanner input=new Scanner(System.in);
        String ch;
        ch=input.next();
        // char[] array=ch.toCharArray();
        // System.out.println("ch="  + ch.charAt(0));
        
        boolean ans=Character.isUpperCase(ch.charAt(0));
        if(ans)
            System.out.println("A");
        else  
             System.out.println("a");
        input.close();
	}
}

Measured memory_bytes: 35480
//Keep pluggin',this is your only outlet.
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cctype>
#include<cmath>
#define MM(x,y) memset(x,y,sizeof(x))
#define MCPY(a,b) memcpy(a,b,sizeof(b))
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,b,a) for(int i=b;i>=a;i--)
#define fi first
#define mp make_pair
#define se second
using namespace std;
#define int long long

inline int quickpow(int m,int n,int p){int b=1;while(n){if(n&1)b=b*m%p;n=n>>1;m=m*m%p;}return b;}
inline int quickmul(int x,int y,int mod){return (x*y-(int)((long double)x/mod*y)*mod+mod)%mod;}
inline int getinv(int x,int p){return quickpow(x,p-2,p);}
inline int read(void){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){f=ch=='-'?-1:1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x * f;
}
const int MAXN = 1e7 + 5;
const int Mod = 998244353;
int fac[MAXN],ifac[MAXN],A,B,N,K;
inline int C(int n,int m){
    if (n < m) return 0;
    return fac[n] * ifac[m] % Mod * ifac[n - m] % Mod;
}
inline void pre(void){
    fac[0] = ifac[0] = 1;
    for (int i  = 1; i < MAXN; ++i) fac[i] = fac[i-1] * i  % Mod;
    ifac[MAXN-1] = getinv(fac[MAXN-1],Mod);
    for (int i = MAXN - 2; i >= 1; --i) ifac[i] = ifac[i+1] * (i + 1) % Mod;
}
inline void ex_gcd(int a,int b,int &d,int &x,int &y){
	if(!b){d = a;x = 1;y = 0;}
	else {
        ex_gcd(b,a%b,d,y,x);
        y-=x*(a/b);
    }
}
///------------------head------------------
signed main(signed argc, char *argv[]){
    pre();
    N = read(),A = read(),B = read(),K = read();
    if (N <= 10) {
        int anss = 0;
        for (int i = 0; i <= N; ++i)
            for (int j = 0; j <= N; ++j)
                for (int k = 0; k <= N; ++k){
                    if (A * i + B * j + (A + B) * k == K && i + j + k <= N)
                    anss = (anss + C(N,i) * C(N-i,j) % Mod * C(N-i-j,k) % Mod) % Mod;
                }
        printf("%lld\n",anss);
        return 0;
    }
    int step = 1,ans = 0,P,Q,flag = 0;
    for (int i = 0; i <= N; i += step)
		if ((K-A*i)%B==0)
		{
			if (!flag) step = B /__gcd(A,B),flag=1;
			P = i; Q = (K-A*i)/B;
			if (Q > N || Q < 0) continue;
			ans=(ans+C(N,P)*C(N,Q)%Mod)%Mod;
		}
	printf("%lld\n",ans%Mod);
    return 0;
}

/* Examples: */
/*

*/

/*

*/


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


#define ll long long
#define pb push_back
#define mp make_pair
#define loop(i, a, b) for(int i = (a); i < (b); i++)
#define loopb(i, a, b) for(int i = (a); i > (b); --i)

typedef pair <int,int> ii;
typedef vector <int> vi;
typedef vector <ii> vii;
typedef vector <ll> vl;

const int mod = 1e9+7;
const int inf = 2e18+5;

vi ans(100005,0);
vi reached(100005,0);
vi g[100005];

int dfs(int i){
  if(reached[i]==1)
    return ans[i];
  for (auto x:g[i]){
    ans[x] = dfs(x);
    ans[i] = max(ans[i] , ans[x] + 1);
  }
  reached[i] = 1;
  return ans[i];
}

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

    int n,m,u,v,res=0;
    cin>>n>>m;

    loop(i,0,m){
      cin>>u>>v;
      g[u].pb(v);
    }

    loop(i,1,n+1)
      res = max ( res, dfs(i) );

    cout<<res;
    return 0;
}


Measured memory_bytes: 8576
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        // Here your code !
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        String[] word = line.split(" ");
        char a = word[0].charAt(0);
        char b = word[1].charAt(0);
        char c = word[2].charAt(0);
        System.out.println(a + "" + b + "" + c);
    }
}

Measured memory_bytes: 24404
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int [] c = new int [n];
		for(int i = 0; i < n; i++) {
			c[i] = sc.nextInt();
		}
		int ans = 999999;

		for(int i = 1; i < n; i++) {
			int l=0,r=0;
			for(int j = 0;j < i;j++) {
				l+=c[j];
			}
			for(int j = i; j < n;j++) {
				r+=c[j];
			}
			ans = Math.min(ans, Math.abs(l-r));
		}
		System.out.println(ans);

	}

}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < n; ++i)
ll dx[4] = { 0, 1, 0, -1 };
ll dy[4] = { 1, 0, -1, 0 };
const ll INF = 1e14;
const ll MOD = 1e9 + 7;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int N, M;
    cin >> N >> M;

    // 通れる階段
    vector<int> oks(N + 1, true);
    rep(i, M)
    {
        int a;
        cin >> a;
        oks[a] = false;
    }

    vector<ll> dp(N + 1, 0);
    dp[0] = 1;
    if (oks[1]) {
        dp[1] = 1;
    }
    for (int n = 2; n <= N; ++n) {
        if (oks[n - 1]) {
            dp[n] += dp[n - 1];
        }
        if (oks[n - 2]) {
            dp[n] += dp[n - 2];
        }
        dp[n] %= MOD;
    }
    cout << dp[N] << endl;
    return 0;
}

Measured memory_bytes: 1408
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

n = inn()
print((1000-n%1000)%1000)


Measured memory_bytes: 61768
fun main(args: Array<String>) {
    agc002c()
}

fun agc002c() {
    val (n, l) = readLine()!!.split(" ").map { it.toInt() }
    val aList = readLine()!!.split(" ").map { it.toLong() }

    val leaveLastKnotIndex = (0 until n - 1).find { i ->
        aList[i] + aList[i + 1] >= l
    } ?: return println("Impossible")

    val knots = ((0 until leaveLastKnotIndex).toList() + (n - 2 downTo leaveLastKnotIndex).toList()).map { it + 1 }

    println("Possible")
    println(knots.joinToString(separator = System.lineSeparator()))
}


Measured memory_bytes: 61172
#include <iostream>
#include <vector>
#include <utility>
#include <cmath>
#include <algorithm>
#include <set>

using namespace std;
typedef long long lint;

int main() {
    int N;
    lint C;
    cin >> N >> C;
    vector<lint> xs(N), vs(N);
    for (int i = 0; i < N; i++) {
        cin >> xs[i] >> vs[i];
    }
    vector<lint> right(N+1), left(N+1), right2(N+1), left2(N+1);
    // 時計回り(right)
    {
        lint sum = 0;
        for (int i = 0; i < N; i++) {
            sum += vs[i];
            right[i+1] = sum - xs[i];
            right2[i+1] = sum - 2 * xs[i];
        }
    }
    // 反時計回り
    {
        lint sum = 0;
        for (int i = N-1; i >= 0; i--) {
            sum += vs[i];
            left[i+1] = sum - (C - xs[i]);
            left2[i+1] = sum - 2 * (C - xs[i]);
        }
    }
    lint ans = 0;
    // 時計回り -> 戻る -> 反時計回り
    {
        lint maxi = 0;
        for (int i = 0; i <= N; i++) {
            ans = max(ans, maxi + left[i]);
            maxi = max(maxi, right2[i]);
        }
    }
    // 反時計回り -> 戻る -> 時計回り
    {
        lint maxi = 0;
        for (int i = N; i >= 0; i--) {
            ans = max(ans, maxi + right[i]);
            maxi = max(maxi, left2[i]);
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4992
#include <stdio.h>
int main(){
  int a,b,c,i;
  for(i=1;i<=4;i++){
    scanf("%d %d",&a,&b);
    if(a==1){
      c=6000*b;
    }else if(a==2){
      c=4000*b;
    }else if(a==3){
      c=3000*b;
    }else if(a==4){
      c=2000*b;
    }
    printf("%d\n",c);
  }
  return 0;
}

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

const int MOD = 1000000007;
const int INF = 1e9;

//long long
using ll = long long;

//出力系
#define print(x) cout << x << endl
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
 
// begin() end()
#define all(x) (x).begin(),(x).end()

//for
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(int i=n, i##_len=(n); i>=0; i--)
#define FOR(i,a,b) for(int i=(a), i##_len=(b); i<i##_len; ++i)

//最大公約数 
unsigned gcd(unsigned a, unsigned b) {
  if(a < b) return gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
} 

int main(){
int N, M;
cin >> N >> M;

vector<pair<ll, ll>> S(N);
vector<tuple<ll, ll, int>> C;

for(int i = 0; i < N; i++){ 
   ll a, b;
   cin >> a >> b;
   S.at(i).first = a;
   S.at(i).second = b;
}


REP(i, M){
  ll c, d;
  cin >> c >> d;
  C.emplace_back(c, d, i);
} 

REP(i, N){
  ll min_m = MOD;
  int x;
  REP(j, M){
  ll am = abs(S.at(i).first - get<0>(C.at(j)));
  ll bm = abs(S.at(i).second - get<1>(C.at(j)));
  // print(am + bm);
  if(min_m > am + bm) x = get<2>(C.at(j)) + 1;
  min_m = min(min_m, am + bm);
  }
print(x);
}
}

Measured memory_bytes: 256