akhauriyash/Code-Regression huggingface dataset:
using System.Linq;
using System.Text;
using System;
using System.Collections;
using System.Collections.Generic;
using System.Globalization;
using System.IO;
using System.Diagnostics;
using System.Threading;
using System.Runtime.CompilerServices;
using System.IO.Pipes;

namespace AtCoder
{
    class Program
    {

        struct Point
        {
            public int x;
            public int y;

            public Point(int x, int y)
            {

                this.x = x;
                this.y = y;

            }

        }


        const int BiggestMod = 1000000007;

        public static void Main()
        {

            int num = int.Parse(Console.ReadLine());
            long ans = 0;

            long[] args = Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToArray();

            long[] data = new long[num - 1];

            data[num - 2] = args[num - 1];

            for (int i = num - 2; 0 < i; --i)
                data[i - 1] = (args[i] + data[i]) % BiggestMod;

            for (int i = 0; i < num - 1; ++i)
            {

                ans += args[i] * data[i];
                ans %= BiggestMod;

            }

            Console.WriteLine(ans);

            /*

            int num = int.Parse(Console.ReadLine());

            int GetGcd(int a, int b)
                => Gcd(Math.Max(a, b), Math.Min(a, b));

            int Gcd(int a, int b)
                => (a % b == 0 ? b : Gcd(b, a % b));

            var args = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            var buf = args[0];

            for (int i = 1; i < num; ++i)
            {

                buf = GetGcd(buf, args[i]);
                if (buf == 1)
                {
                    goto skip;
                }

            }

            Console.WriteLine("not coprime");
            return;

        skip:

            Array.Sort(args);

            for (int i = 0; i + 1< num; ++i)
                for (int j = i + 1; j < num; ++j)
                    if (Gcd(args[j], args[i]) != 1)
                    {

                        Console.WriteLine("setwise coprime");
                        return;

                    }

            Console.WriteLine("pairwise coprime");
            return;
            
            
             */

        }

    }

}

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

#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;

int mod = 1000000007;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M; cin >> N >> M;
    ll X[N], Y[M];
    rep(i, N) cin >> X[i];
    rep(i, M) cin >> Y[i];
    ll accx = 0, accy = 0;
    rep(i, N) accx = (accx + X[i]*(2*i+1-N)) % mod;
    rep(i, M) accy = (accy + Y[i]*(2*i+1-M)) % mod;
    cout << (accx*accy) % mod << endl;
    return 0;
}

Measured memory_bytes: 1792
#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  int n, k;
  std::cin >> n >> k;

  std::vector<int> h(n);
  for (auto&& hi : h) std::cin >> hi;

  const auto n_passengers =
      std::count_if(h.begin(), h.end(), [k](auto hi) { return hi >= k; });
  std::cout << n_passengers << std::endl;
}

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

vector<string> getlist(int n) {
  vector<string> vec(n);
  rep(i, n)
    cin >> vec.at(i);
  return vec;
}

int count(vector<string> vec, string name) {
  int c = 0;
  rep(i, vec.size()) {
    if (vec.at(i) == name)
      c++;
  }
  return c;
}

int main() {
  int n, m;
  int result = 0;
  
  cin >> n;
  vector<string> blue(n);
  blue = getlist(n);
  
  cin >> m;
  vector<string> red(m);
  red = getlist(m);
  
  int b, r;
  rep(i, blue.size()) {
    b = count(blue, blue.at(i));
    r = count(red, blue.at(i));
    if (b-r > result)
      result = b-r;
  }
  
  cout << result << endl;
}

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

int main() {
	ios_base::sync_with_stdio( false );

	int N;
	cin >> N;
	N -= 1;

	vector<int> B( N );
	for( auto& v: B ) { cin >> v; }

	int result = B.back();
	for( int i = N-1; i > 0; --i ) {
		result += min( B[i], B[i-1] );
	}

	result += B[0];

	cout << result << endl;
}


Measured memory_bytes: 256
// abc102_b
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) rep(i,v.size())cout<<" "<<v[i];cout<<endl<<endl;
#define show2d(v) rep(i,v.size()){rep(j,v[i].size())cout<<" "<<v[i][j];cout<<endl;}cout<<endl;
using namespace std;
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;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int main(int argc, char *argv[])
{
  int n,a,n_min=1000000000,n_max=1;
  cin>>n;
  rep(i,n){
    cin>>a;
    n_min = min(n_min,a);
    n_max = max(n_max,a);
  }
  cout<<n_max-n_min<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=6050;
int f[N][N],a[N],b[N],c[N],na,nb,n;
char s[N*2];
string func(int *g){
  string ans="";
  for (int i=1; i<=2*n; ++i)
    if (g[c[i]])
      ans+=s[i];
  return ans;
}
int main(){
  cin>>n;
  scanf("%s",s+1);
  for (int i=1; i<=2*n; ++i)
    if (s[i]=='a')
      a[++na]=i,c[i]=na;
    else
      b[++nb]=i,c[i]=nb;
  f[n][n]=1;
  for (int i=n-1; i>=1; --i){
    f[i][i]=1;
    int mx=0;
    if (a[i]<b[i]){
      for (int j=a[i]; j<=b[i]; ++j)
	mx=max(mx,c[j]);
      for (int j=mx+1; j<=n; ++j)
	f[i][j]=f[mx+1][j];
    }
    else{
      int tot=0;
      for (int j=b[i]; j<=a[i]; ++j){
	if (c[j]<i) continue;
	if (c[j]!=i) ++tot;
	mx=max(mx,c[j]),f[i][c[j]]=1;
      }
      for (int j=a[i]+1; j<=2*n; ++j)
	if (s[j]=='b'){
	  if (tot==0)
	    f[i][c[j]]=f[mx+1][c[j]];
	  else
	    f[i][c[j]]=1,++tot;
	}
	else{
	  if (tot==0)
	    f[i][c[j]]=f[mx+1][c[j]];
	  else
	    f[i][c[j]]=1,mx=max(mx,c[j]),--tot;
	}
    }
    if (func(f[i])<func(f[i+1]))
      memcpy(f[i],f[i+1],sizeof f[i]);
  }
  cout<<func(f[1]);
  return 0;
}

Measured memory_bytes: 71936
#include<stdio.h>
int main(){
	int a,b;
	while(scanf("%d%d",&a,&b)!=EOF){
		if(a+b>=1000000){
			printf("7\n");
		}
		else if(a+b>=100000){
			printf("6\n");
		}
		else if(a+b>=10000){
			printf("5\n");
		}
		else if(a+b>=1000){
			printf("4\n");
		}
		else if(a+b>=100){
			printf("3\n");
		}
		else if(a+b>=10){
			printf("2\n");
		}
		else{
			printf("1\n");
		}
	}
	return 0;
}

Measured memory_bytes: 584
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String alice = sc.next();
        String bob = sc.next();
        String charlie = sc.next();
        int a, b, c;
        a = b = c = 0;
        int turn = 1;
        while(true){
            if(turn == 1){
                if(a == alice.length()){
                    System.out.println('A');
                    break;
                }else{
                    if(alice.charAt(a) == 'a')
                        turn = 1;
                    else if(alice.charAt(a) == 'b')
                        turn = 2;
                    else
                        turn = 3;
                    a += 1;
                }
            }else if(turn == 2){
                if(b == bob.length()){
                    System.out.println('B');
                    break;
                }else{
                    if(bob.charAt(b) == 'a')
                        turn = 1;
                    else if(bob.charAt(b) == 'b')
                        turn = 2;
                    else
                        turn = 3;
                    b += 1;
                }
            }else{
                if(c == charlie.length()){
                    System.out.println('C');
                    break;
                }else{
                    if(charlie.charAt(c) == 'a')
                        turn = 1;
                    else if(charlie.charAt(c) == 'b')
                        turn = 2;
                    else
                        turn = 3;
                    c += 1;
                }
            }
        }
    }
}


Measured memory_bytes: 23508
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define iter(it,a) for(auto it=a.begin();it!=a.end();it++)
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define pii pair<int,int> 
#define endl '\n'
#define preturn(X) cout<<X<<endl; return 0
typedef long long ll;

int h,w,k;
char a[801][801];
bool visited[801][801];
pair<int,int> start;
vector<pair< ll ,pair<int,int> > > adj[801][801];
ll dist[801][801];
ll mini =1600;

void dijkstra(){
	priority_queue<pair<ll,pii>, vector<pair<ll,pii> >, greater<pair<ll,pii> > > vertices;
	vertices.push(make_pair(0,start));
	while(!vertices.empty()){
		pii x=(vertices.top()).second;
		vertices.pop();
		if(!visited[x.F][x.S]){
			for(auto it=adj[x.F][x.S].begin();it!=adj[x.F][x.S].end();it++){
				ll w1;
				w1=(*it).first;
				pii other =(*it).second;
				if(dist[x.F][x.S]+w1<dist[other.F][other.S]){
					dist[other.F][other.S]=dist[x.F][x.S]+w1;
					vertices.push(make_pair(dist[other.F][other.S],other));
				}
			}
		}
		visited[x.F][x.S]=1;
	}
}

int main(){
    cin.tie(0);ios_base::sync_with_stdio(0);
    cin>>h>>w>>k;
    rep(i,0,h){
    	rep(j,0,w){
    		cin>>a[i][j];
    		if(a[i][j]=='S'){
    			start.F = i;
    			start.S = j;
    		}
    	}
    }
    
    rep(i,0,h){
    	rep(j,0,w){
			if(a[i][j]=='S' || a[i][j]=='.'){
				if(a[i+1][j]=='.'){
					adj[i][j].pb(mp(1,mp(i+1,j)));
				}
				if(a[i][j+1]=='.'){
					adj[i][j].pb(mp(1,mp(i,j+1)));
				}
				if(a[i-1][j]=='.'){
					adj[i][j].pb(mp(1,mp(i-1,j)));
				}
				if(a[i][j-1]=='.'){
					adj[i][j].pb(mp(1,mp(i,j-1)));
				}
			}
    	}
    }
        		
    rep(i,0,h){
    	rep(j,0,w){
    		dist[i][j] = 1e9;
    	}
    }
    dist[start.F][start.S] = 0;
    dijkstra();

	rep(i,0,h){
		rep(j,0,w){
			int x= i;
			int y = j;
			if(dist[i][j] <= k){
				if(mini > x){
					mini = x;
				}
				if(mini > h-1-x){
					mini = h-1-x;
				}
				if(mini > y){
					mini = y;
				}
				if(mini > w-1-y){
					mini = w-1-y;
				}
			}
		}
	}    

    if(mini == 0){
    	preturn(1);
    }
    int ans = 1;
    ans+=(mini/k);
    mini=(mini%k);
    if(mini>0){
    	ans++;
    }
    preturn(ans);	
}

Measured memory_bytes: 70528
using System;
using System.Linq;
namespace ABC095
{
    class Program
    {
        static void Main()
        {
            int[] nx = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
            int[] m = new int[nx[0]];
            for (int i = 0; i < nx[0]; i++)
                m[i] = int.Parse(Console.ReadLine());
            Array.Sort(m);
            Console.WriteLine(nx[0] + (nx[1] - m.Sum()) / m[0]);
        }
    }
}

Measured memory_bytes: 13396
#include<stdio.h>
#include<string.h>
int main(void){
    int A,B,C,D,E,x,y,cou=0,v[3];
    char S[10],W[10],s[10],X,Y;
    scanf("%d %d %d %d",&A,&B,&C,&D);
    printf("%d",(A-C)*(B-D));
    return 0;
}

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

int main(){
    string s;
    cin >> s;
    if(s=="SUN"){
        cout << 7 << endl;;
        return 0;
    }else if(s=="MON"){
        cout << 6 << endl;
        return 0;
    }else if(s=="TUE"){
        cout << 5 << endl;
        return 0;
    }else if(s=="WED"){
        cout << 4 << endl;
        return 0;
    }else if(s=="THU"){
        cout << 3 << endl;
        return 0;
    }else if(s=="FRI"){
        cout << 2 << endl;
        return 0;
    }else if(s=="SAT"){
        cout << 1 << endl;
        return 0;
    }
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int main(void) {
	char str[10001];
	int i,joi=0,ioi=0;

	while (scanf("%s", str) != EOF) {
		joi = 0;
		ioi = 0;
		for (i = 0; i < strlen(str); i++) {
			if (strncmp(&str[i], "JOI", 3) == 0)joi++;
			if (strncmp(&str[i], "IOI", 3) == 0)ioi++;
		}
		printf("%d\n%d\n", joi, ioi);
	}
	return 0;
}

Measured memory_bytes: 556
n, x, y = int(input()), list(map(int, input().split())), list(map(int, input().split()))


def dist(p):
    return pow(sum(pow(abs(a - b), p) for a, b in zip(x, y)), 1.0 / p)


for i in [1, 2, 3]:
    print(dist(i))

print(max(abs(a - b) for a, b in zip(x, y)))

Measured memory_bytes: 7820
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i = (m); i < (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " ";} cout<<endl;

ll n, at[200008];
string s;

int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	
	cin >> n;
	rep(i, 0, n){
		ll buf;
		cin >> buf;
		at[buf] = i+1;
	}
	
	set<ll, greater<ll>> l;
	set<ll> r;
	l.insert(0);
	l.insert(n+1);
	r.insert(0);
	r.insert(n+1);
	
	
	ll ans = 0;
	rep(i, 1, n+1){
		ans += (at[i]-*(l.upper_bound(at[i])))*(*(r.upper_bound(at[i]))-at[i])*i;
		l.insert(at[i]);
		r.insert(at[i]);
	}
	
	print(ans)
	return 0;
}

Measured memory_bytes: 20608
#include <bits/stdc++.h>
#define REP(i,n,N) for(int i=n;i<N;i++)
#define p(S) cout<<S<<endl
using namespace std;

int main(){
	int n,r;
	while(cin>>n>>r&&n){
		stack<int> st,tmp1,tmp2;
		int p,c;
		REP(i,1,n+1){
			st.push(i);
		}
		REP(i,0,r){
			cin>>p>>c;
			REP(j,0,p-1){
				tmp1.push(st.top());
				st.pop();
			}
			REP(j,0,c){
				tmp2.push(st.top());
				st.pop();
			}
			while(!tmp1.empty()){
				st.push(tmp1.top());
				tmp1.pop();
			}
			while(!tmp2.empty()){
				st.push(tmp2.top());
				tmp2.pop();
			}
		}
		p(st.top());
	}

	return 0;
}

Measured memory_bytes: 3084
#include <stdio.h>
#include <string.h>
#define M 1046527
int n;
char H[M][12];
int getChar(char);
 
int main(void){
    int i;
    char arr[12];
    char com[10];
    for(i=0;i<M;i++){
        H[i][0] = '\0';
    }
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%s %s", com, arr);
        if(com[0] == 'i'){
            insert(arr);
        }
        if(com[0] == 'f'){
            if(search(arr)){
                printf("yes\n");
            }
            else printf("no\n");
        }
         
    }
 
}
int h1(int key){
    return key % M;
}
 
int h2(int key){
    return 1+(key %(M -1));
}
 
long long getKey(char str[]){
    long long total=0, p = 1,i;
    for(i=0; i<strlen(str); i++){
        total += p*(getChar(str[i]));
        p *= 5;
    }
    return total;
}
int getChar(char c){
    if(c =='A') return 1;
    else if(c== 'C') return 2;
    else if(c == 'G') return 3;
    else if(c == 'T') return 4;
    else return 0;
}
 
int insert(char str[]){
    long long i,h;
    long long key;
    key = getKey(str);
    for(i=0; ;i++){
        h = (h1(key)+ i * h2(key)) % M;
        if(strcmp(H[h],str) == 0) return 1;
        else if(strlen(H[h]) == 0) {
            strcpy(H[h], str);
            return 0;
        }
    }
    return 0;
}
 
int search(char str[]){
    long long i,h;
    long long key;
    key = getKey(str);
    for(i=0; ;i++){
        h = (h1(key)+ i * h2(key)) % M;
        if(strcmp(H[h],str) == 0) return 1;
        else if(strlen(H[h]) == 0) return 0;
    }
    return 0;
}



Measured memory_bytes: 14024
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
const int md = 1e9+7;
const int mx = 200005;
int n, c[mx], x;
vector<P> vs;
priority_queue<P> pq;
long long fr[mx] = {1}, ans;

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d", &x);
        if(c[x] && c[x] != i-1) vs.push_back(P(c[x], i));
        c[x] = i;
    }
    vs.push_back(P(mx-4, mx-3));
    sort(vs.begin(), vs.end());
    int tmp = 0;
    for(auto it: vs){
        if(it.first != tmp) (fr[it.first] += fr[tmp]) %= md;
        while(!pq.empty() && -pq.top().first <= it.first){
            (fr[it.first] += fr[pq.top().second]) %= md;
            pq.pop();
        }
        pq.push(P(-it.second, it.first));
        tmp = it.first;
    }
    printf("%lld\n", fr[tmp] % md);
}

Measured memory_bytes: 4080
#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}
#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}
#[allow(dead_code)]
fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}
#[allow(dead_code)]
fn yn(result: bool) {
    if result {
        println!("Yes");
    } else {
        println!("No");
    }
}
fn main() {
    let n = read::<u32>();
    let mut ans = false;
    let mut k = 0;
    loop {
        if (n - k * 7) % 4 == 0{
            ans = true;
            break;
        }
        k += 1;
        if k * 7 > n {
            break;
        }
    }
    yn(ans);
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
#define ll long long
void solve()
{
    int d,t,s;
    cin>>d>>t>>s;
    if(s*t>=d)
        cout<<"Yes";
    else
        cout<<"No";

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


Measured memory_bytes: 3632
#define taskname "test"

#include <bits/stdc++.h>

using namespace std;

#define sz(x) (int)x.size()
#define fi first
#define se second

typedef long long lli;
typedef pair<int, int> pii;

int a, b, c;
int k;

void read_input()
{
    cin >> a >> b >> c >> k;
}

void solve()
{
    int cnt = 0;
    while(b <= a)
    {
        b *= 2;
        ++cnt;
    }
    while(c <= b)
    {
        c *= 2;
        ++cnt;
    }
    cout << (cnt <= k ? "Yes" : "No") << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    read_input();
    solve();
}



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

int main () {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  ll total = 0;
  cin >> n;
  vector<ll> v(n);
  for (int i = 0; i < n; ++i) {
    cin >> v[i];
    total += v[i];
  }
  int li = 0, ri = n-1;
  ll l = 0;
  ll r = 0;
  while (l*2 < total) {
    l += v[li++];
  }
  while (r*2 < total) {
    r += v[ri--];
  }
  cout << min(2*l-total, 2*r-total) << endl;
}



Measured memory_bytes: 1792
# AtCoder Beginner Contest 111 20180929
# Question:B
 
def main(nums):
	
	ref = nums[0]*len(nums)
	
	if int(ref) >= int(nums):
		return int(ref)
	else:
		ref2 = '1'*len(nums)
		
		return int(ref)+int(ref2)
	
nums = input()
print(main(nums))

Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define modulo 998244353
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 10000000000000000

//aのb乗
int beki(int a,int b){
	int x = 1;
	while(b!=0){
		if(b&1){
			x=mod(x*a);
		}
		a=mod(a*a);
		b>>=1;
	}
	return x;
}

//aの逆元
int gyakugen(int a){
	return beki(a,modulo-2);
}

struct combi{
	deque<int> kaijou;
	deque<int> kaijou_;
	
	combi(int n){
		kaijou_set(n);
	}
	
	void kaijou_set(int n){
		kaijou.push_back(1);
		for(int i=1;i<=n;i++){
			kaijou.push_back(mod(kaijou[i-1]*i));
		}
		
		int b=gyakugen(kaijou[n]);
		
		kaijou_.push_front(b);
		for(int i=1;i<=n;i++){
			int k=n+1-i;
			kaijou_.push_front(mod(kaijou_[0]*k));
		}
	}
	
	int combination(int n,int r){
		if(r>n)return 0;
		int a = mod(kaijou[n]*kaijou_[r]);
		a=mod(a*kaijou_[n-r]);
		return a;
	}
	
	int junretsu(int a,int b){
		int x = mod(kaijou_[a]*kaijou_[b]);
		x=mod(x*kaijou[a+b]);
		return x;
	}
	
};

int main(){
	int N;
	cin>>N;
	
	int A,B;
	cin>>A>>B;
	
	long long K;
	cin>>K;
	
	combi c(N);
	
	
	int ans = 0;
	
	for(int i=0;i<=N;i++){
		long long a = (long long)A*i;
		long long b = (long long)K-a;
		if(b<0)continue;
		if(b%B!=0)continue;
		b/=B;
		
		int k = mod(c.combination(N,i)*c.combination(N,b));
		ans = mod(ans+k);
	}
	
	cout<<ans<<endl;
	
	return 0;
}


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

namespace AtCoderPractic0717
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            int[] L = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();

            var LS = L.ToList();

            LS.Sort();

           int[] LI =  LS.ToArray();

            int sum = 0;

            for (var i = 0; i < L.Length - 1; i++)
            {
                sum += LI[i];
            }

            if (sum > LI[N-1])
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
        }
    }
}


Measured memory_bytes: 28048
#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <iomanip>
#include <bitset>

using namespace std;

typedef long long ll;

mt19937 rnd(228);

const int N = 100 + 7;

int a[N][N];
int dp[N][N];

int main()
{
#ifdef ONPC
    freopen("a.in", "r", stdin);
#endif
    int n;
    cin >> n;
    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> a[i][j];
            if (i && j) dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + a[i][j];
            if (i && !j) dp[i][j] = dp[i - 1][j] + a[i][j];
            if (!i && j) dp[i][j] = dp[i][j - 1] + a[i][j];
            if (!i && !j) dp[i][j] = a[i][j];
        }
    }
    cout << dp[1][n - 1] << '\n';
}


Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
res = sum(b)
for i in range(len(a) - 1):
  if a[i+1] == a[i] + 1:
    res += c[a[i] - 1]
print(res)

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

using namespace std;

int main(){
    int n;
    map<int, bool> a;
    
    cin >> n;
    for(int i = 0; i < n; i++){
        int t; cin >> t;
        if(a.find(t) == a.end() || !a[t]){
            a[t] = true;
        }
        else{
            a[t] = false;
        }
    }
    int ans = 0;
    for(map<int,bool>::iterator itr = a.begin(); itr != a.end(); ++itr){
        if(itr->second){
            ans++;
        }
    }
    cout << ans << endl;
	return 0;
}



Measured memory_bytes: 4992
require 'forwardable'
require 'set'

module Graph
	def add_node(label = nil)
		Node.new(label)
	end

	def add_edge(u, v, label = nil)
		e = Edge.new(u, v, label)
		u.outgoings << e
		v.incomings << e
		e
	end
	
	def del_edge(e)
		u, v = e.from, e.to
		u.outgoings.delete(e)
		v.incomings.delete(e)
		e
	end

	class Node
		def initialize(label)
			@label = label
			@outgoings = Set.new
			@incomings = Set.new
		end

		def to_nodes
			@outgoings.map(&:to)
		end

		def from_nodes
			@incomings.map(&:from)
		end

		attr_reader :height, :label
		attr_accessor :incomings, :outgoings, :height
	end

	class Edge
		def initialize(u, v, label = nil)
			@from = u	
			@to = v
			@label = label
		end
		attr_reader :from, :to, :label
	end

	def layers_from(start)
		reached = Set[*start]
		layers = [start]

		loop {
			layers << []
			layers[-2].each{|u|
				u.to_nodes.each{|v|
					next if reached.include?(v)
					reached << v
					layers[-1] << v
				}
			}	

			if layers[-1].empty?
				layers.pop
				return layers
			end
		}
	end
end

class Heap
	extend Forwardable
	def initialize
		@array = []
		@index = {}
	end

	def add(obj, key)
		@array << [obj, key]
		@index[obj] = @array.size - 1
		lift_up(@array.size - 1)
	end

	def swap(i, j)
		u = @array[i]
		v = @array[j]
		@index[u[0]], @index[v[0]] = j, i
		@array[i], @array[j] = v, u
	end

	def lift_up(i)
		return if i == 0
		j = (i - 1) / 2
		if @array[i][1] < @array[j][1]
			swap(i, j)
			lift_up(j)
		end
	end

	def del_min
		min = @array[0]
		if size > 1
			swap(0, @array.size-1)
			@array.pop
			lift_down(0)
		else
			@array.pop
		end
		@index.delete(min[0])
		min
	end

	def dec_key(obj, diff)
		i = @index[obj]
		@array[i][1] -= diff
		lift_up(i)
	end

	def min_obj
		@array[0][0]
	end

	def min_key
		@array[0][1]
	end

	def lift_down(i)
		j = 2 * i + 1
		k = j + 1
		if k >= size
			return if j >= size
			if @array[i][1] > @array[j][1]
				swap(i, j)
				lift_down(j)
			end
		else
			l = (@array[j][1] < @array[k][1] ? j : k)
			if @array[i][1] > @array[l][1]
				swap(i, l)
				lift_down(l)
			end
		end
	end

	def_delegators :@array, :empty?, :size
end

include Graph

n, m = gets.split.map(&:to_i)

nodes = (1..n).map{|i| add_node(i)}
m.times{|k|
	i, j = gets.split.map(&:to_i)
	add_edge(nodes[i-1], nodes[j-1], k+1)
}

heap = Heap.new
nodes.each{|v| heap.add(v, v.outgoings.size)}

loop {
	u, _ = heap.del_min
	u.height = 0
	unless u.outgoings.empty?
		u.height = u.to_nodes.map(&:height).max
		u.outgoings.each{|e|
			del_edge(e) if e.to.height < u.height
		}
		u.height += 1
	end

	break if heap.empty?
	u.from_nodes.each{|w|
		heap.dec_key(w, 1)
	}
}

h = nodes.map(&:height).max
roots = nodes.select{|v| v.height == h}

ans = []
Graph::layers_from(roots).each_cons(2){|l1, l2|
	if l1.size == 1 && l2.size == 1
		ans << l1[0].outgoings.to_a[0].label
	end
}

puts ans.empty? ? -1 : ans.sort

Measured memory_bytes: 178592
#include <iostream>
#include <map>
#include <cmath>
#include <queue>

using namespace std;

int main(){
    int T; cin >> T;
    while(T--){
        long long N, A, B, C, D; cin >> N >> A >> B >> C >> D;
        map<long long, long long> mp;
        mp[0] = 0;
        priority_queue<pair<long long, long long>> qu;
        qu.emplace(0, N);
        long long res = 1LL << 60;
        while(!qu.empty()){
            auto p = qu.top(); qu.pop();
            auto cur = -p.first;
            if(cur >= res) break;
            auto v = p.second;
            if(v <= 2000000000){
                res = min(res, cur + v * D);
            }
            auto check = [&](long long cost, long long value){
                if(!mp.count(value) || mp[value] > cost){
                    mp[value] = cost;
                    qu.emplace(-cost, value);
                }
            };
            for(int i=-1;i<=1;i++){
                if(v+i > 0 && (v+i)%2 == 0){
                    check(cur+abs(i)*D+A, (v+i)/2);
                }
            }
            for(int i=-2;i<=2;i++){
                if(v+i > 0 && (v+i)%3 == 0){
                    check(cur+abs(i)*D+B, (v+i)/3);
                }
            }
            for(int i=-4;i<=4;i++){
                if(v+i == 0){
                    check(cur+abs(i)*D, v+i);
                }
                if(v+i > 0 && (v+i)%5 == 0){
                    check(cur+abs(i)*D+C, (v+i)/5);
                }
            }
        }
        cout << res << endl;
    }
}

Measured memory_bytes: 4256
#include<bits/stdc++.h>
#define i64 long long
#define vi32 vector<int>
#define vi64 vector< long long>
#define  ii pair<int,int>
const  long long mod = 1e9 + 7, inf = 1e9, linf = 1 << 30; //linf = 9223372036854775807;
const long long hashmod[4] = { (int)1e9 + 2277, (int)1e9 + 5277, (int)1e9 + 8277, (int)1e9 + 9277 };
const long double EPS = 0.000000001L, pi = acos(-1);
using namespace std;
#define pb push_back
#define mp make_pair
#define N 200005
//int base = 311;
using namespace std;
int cnt[N];
vi32 pa[30];
int main()
{
    string s;
    string t;
    cin>>s>>t;
    // y/x=y^x
    // y^x<=x+y
    // y/x=
    bool x=true;
    for(auto z:s)cnt[z]++;
    for(auto z:t)if(!cnt[z])x=false;
    if(x==false)
    {
        cout<<"-1";
        return 0;
    }
    
    for(int i=0;i<s.size();i++)
    {
        pa[s[i]-'a'].pb(i);
    }
    i64 pos=-1;
    i64 ans=0;
    for(int i=0;i<t.size();i++)
    {
        int cur=t[i]-'a';
        
        auto it=upper_bound(pa[cur].begin(),pa[cur].end(),pos);
        if(it==pa[cur].end())
        {
            pos=pa[cur][0];
            ans++;
        }
        else
            pos=*it;

    }
    cout<<ans*s.size()+pos+1;

    return 0;

}




/* Written by a random fan of Mr.Siro 

Association of people who died from abandonment

Gb_H

*/


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

using namespace std;

#define YES cout << "YES" << endl;
#define NO  cout << "NO"  << endl;
#define Yes cout << "Yes" << endl;
#define No  cout << "No"  << endl;
 
#define INF INT_MAX
#define MOD 1000000007
#define PI  acos(-1)

using ll  = long long;
using ull = unsigned long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rrep(i, n) for (ll i = (n)-1; i >= 0; i--)

int main(int argc, char *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;
    cin >> n;

    vector<string> S(n);
    rep (i, n) {
        cin >> S[i];
    }

    vector<int> v(26);
    rep (i, S[0].size()) {
        v[S[0][i]-'a']++;
    }

    for (int i = 1; i < n; i++) {
        vector<int> tmp(26);
        rep (j, S[i].size()) {
            tmp[S[i][j]-'a']++;
        }
        rep (j, 26) {
            v[j] = min(v[j], tmp[j]);
        }
    }

    string ans = "";
    rep (i, 26) {
        if (v[i] > 0) {
            rep (j, v[i]) {
                ans += (i+'a');
            }
        }
    }

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

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

using namespace std;

const int N=2000+5;

int n;
int a[N];
int k;
int q;
bool f[N];


int solve(int x) {
    // cerr<<x<<":"<<endl;
    for (int i=1;i<=n;++i) {
        f[i]=!(a[i]>=x);
        // putchar(f[i]+'0');
    }
    // cerr<<endl;
    priority_queue <int> que;
    for (int l=1;l<=n;++l) {
        if (f[l]==1) {
            continue;
        }
        int r=l;
        while (r<=n&&f[r]==0) {
            ++r;
        }
        --r;
        int len=r-l+1;
        int cnt=len-k+1;
        // cerr<<l<<" "<<r<<" "<<cnt<<endl;
        if (cnt<=0) {
            l=r;
            continue;
        }
        vector <int> v;
        for (int j=l;j<=r;++j) {
            v.push_back(a[j]);
        }
        sort(v.begin(),v.end());
        for (int j=0;j<cnt;++j) {
            que.push(-v[j]);
        }
        l=r;
    }
    if (que.size()<q) {
        return -1;
    }
    for (int i=1;i<q;++i) {
        // cerr<<que.top()<<endl;
        que.pop();
    }
    return -que.top();
}

int main() {
    scanf("%d %d %d\n",&n,&k,&q);
    for (int i=1;i<=n;++i) {
        scanf("%d",&a[i]);
    }
    int ans=INT_MAX;
    for (int i=1;i<=n;++i) {
        int k=solve(a[i]);
        if (k==-1) {
            continue;
        }
        // cerr<<"ans="<<k<<" "<<a[i]<<endl;
        ans=min(k-a[i],ans);
    }
    cout<<ans<<endl;
    return 0;
}


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

int main() {
	int N, M;
	cin >> N >> M;
	vector<bool> tmp1(M, true);
	for (int i = 0; i < N; ++i) {
		int K;
		cin >> K;
		vector<bool> tmp2(M);
		for (int j = 0; j < K; ++j) {
			int A;
			cin >> A;
			tmp2[A - 1] = true;
		}
		for (int j = 0; j < M; ++j) {
			if (tmp2[j] == false) {
				tmp1[j] = false;
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < M; ++i) {
		if (tmp1[i]) ++ans;
	}
	cout << ans;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define rep(X,N) for(ll X = 0; X < (N); X++)
#define bitrep(X,N) for(ll X = 0; X < (1 << (N)); X++)
#define PI (acos(-1.0))
#define pback push_back
#define mpair make_pair
#define MODN 1000000007
#define ALL(V) (V).begin(),(V).end() 


using namespace std;

int main(){

    //2次元のいもす法を用いる

    int n,m,q;
    cin >> n >> m >> q;

    int imos[502][502] = {};

    rep(i,m){
        int l,r;
        cin >> l >> r;

        imos[1][r]++;
        imos[l + 1][r]--;
        imos[1][n + 1]--;
        imos[l + 1][n + 1]++;
    }

    for(int i = 1; i <= n; i++){
        for(int j = 2; j <= n; j++){
            imos[i][j] = imos[i][j] + imos[i][j - 1];
        }
    }

    for(int j = 1; j <= n; j++){
        for(int i = 2; i <= n; i++){
            imos[i][j] = imos[i][j] + imos[i - 1][j];
        }
    }

    rep(i,q){
        int p,qq;
        cin >> p >> qq;
        cout << imos[p][qq] << endl;
    }


    return 0;
}

Measured memory_bytes: 2048
#include <bits/stdc++.h>
using namespace std;
#define iinf 2000000000
#define linf 1000000000000000000LL
#define ulinf 10000000000000000000ull
#define MOD1 1000000007LL
#define mpr make_pair
typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned long UL;
typedef unsigned short US;
typedef pair < int , int > pii;
clock_t __stt;
inline void TStart(){__stt=clock();}
inline void TReport(){printf("\nTaken Time : %.3lf sec\n",(double)(clock()-__stt)/CLOCKS_PER_SEC);}
template < typename T > T MIN(T a,T b){return a<b?a:b;}
template < typename T > T MAX(T a,T b){return a>b?a:b;}
template < typename T > T ABS(T a){return a>0?a:(-a);}
template < typename T > void UMIN(T &a,T b){if(b<a) a=b;}
template < typename T > void UMAX(T &a,T b){if(b>a) a=b;}
int n,c[200005],s[200005],dp[200005];
int main(){
    // inputting start
    // 数据结构记得初始化！ n，m别写反！
    int i,j,k;
	scanf("%d",&n);
	for(i=0;i<n;++i){
		scanf("%d",c+i);
		--c[i];
	}
    #ifdef LOCAL
        TStart();
    #endif
    // calculation start
    // 数据结构记得初始化！ n，m别写反！
	s[c[0]]=1;
    for(i=0;i<n;++i){
		if(i) dp[i]=dp[i-1];
		if(!i || c[i]!=c[i-1]) dp[i]+=s[c[i]];
		dp[i]%=MOD1;
		if(i && c[i]!=c[i-1]){
			s[c[i]]+=dp[i-1];
			s[c[i]]%=MOD1;
		}
	}
	printf("%d\n",dp[n-1]);
    #ifdef LOCAL
        TReport();
    #endif
    return 0;
}

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

using namespace std;


long long s,n,dp[101][100001],sz[101],val[101],ans;
int main(){
      cin>>n>>s;
      for(int i=1; i<=n; i++)
            cin>>sz[i]>>val[i];
      for(int i=1; i<=n; i++){
            for(int j=1; j<=s; j++){
                  dp[i][j]=dp[i-1][j];
                  if(sz[i]<=j)
                        dp[i][j]=max(dp[i][j],val[i]+dp[i-1][j-sz[i]]);
                  ans=max(ans,dp[i][j]);
            }
      }

      cout<<ans;
      return 0;
}

Measured memory_bytes: 78336
//#include<bits/stdc++.h>
#include<iostream>
#include<vector>
#include<map>
#include <iomanip>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
//#include<unordered_map>
//#include<stack>
#include<algorithm>
#define ll long long
#define eps 1e-9
#define endl "\n"
#define PI acos(-1)
#define pb push_back
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL)
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;

int main()
{
   ll n,hp=0,sum=0;
   cin>>n;
   int fivehun=n/500;
   sum+=(fivehun*1000);
   int rem=n%500;
   int five=rem/5;
   sum+=(five*5);
   cout<<sum<<endl;
return 0;
}


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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    double d;
    cin >> n >> d;
    int c = 0;
    for (int i = 0; i < n; i++)
    {
        double x, y;
        cin >> x >> y;
        double dis = sqrt((x * x) + (y * y));
        if (dis <= d)
            c++;
    }
    cout << c;
    return 0;
}

Measured memory_bytes: 3824
#include<iostream>
#include<algorithm>
#include<bitset>
#include<cmath>
#include<complex>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<iterator>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

using namespace std;
typedef long long int ll;

int N,M;

int main(){
    cin>>N>>M;
    if(N==M)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}


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

int main(){
  int P, Q, R;
  cin >> P >> Q >> R;
  int min=P+Q;
  if(min>Q+R) min = Q+R;
  if(min>R+P) min = R+P;
  cout << min << endl;
  return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define endl "\n"
#define sz(x) ((ll)(x).size())
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define prt(x) cout << (x)
#define prtl(x) cout << (x) << endl
#define rep(i,a,b) for(ll i=a; i<b; i++)
#define rrep(i,a,b) for(ll i=a; i>b; i--)
#define mp(a, b) make_pair(a, b)
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define debug(v) cout << #v<< ": " << v <<endl;
#define fst first
#define snd second
using namespace std;
using vi = vector<int>;
using vll = vector<long long int>;
using vb = vector<bool>;
using vvb = vector<vector<bool>>;
using vc = vector<char>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<long long int>>;
using vvc = vector<vector<char>>;
using ll = long long int;
using P = pair<long long int, long long int>;
using Map = map<long long int, long long int>;
ll INF = 1LL<<60;
ll M = 1000000007;

int main(){
    ll k; cin >> k;
    vll kmod(0);
    ll m = 7%k;
    kmod.emplace_back(m);
    rep(i, 0, 10000000){
        m *= 10;
        m %= k;
        kmod.emplace_back(m);
    }
    vll mdc(0);
    ll s = 0;
    rep(i, 0, 10000001){
        s += kmod[i];
        s %= k;
        mdc.emplace_back(s);
    } 
    rep(i, 0, 10000001){
        if(mdc[i] == 0){
            prtl(i+1);
            return 0;
        }
    }
    prtl(-1);
}


Measured memory_bytes: 212636
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int K = sc.nextInt();
        int A = sc.nextInt();
        int B = sc.nextInt();
        boolean ok = false;
        for (int i = A; i <= B; i++) {
            if (i % K == 0) {
                ok = true;
            }
        }
        if (ok) {
            System.out.println("OK");
        } else {
            System.out.println("NG");
        }
        sc.close();
    }
}

Measured memory_bytes: 35836
fn read_as_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).ok();
    buf.trim()
        .split_whitespace()
        .map(|e| e.trim().parse().ok().unwrap())
        .collect()
}

fn main() {
    let (n, k) = {
        let a: Vec<u64> = read_as_vec();
        (a[0], a[1])
    };

    let m = 1000000007;

    let mut ans: u64 = 0;
    for i in k..=n + 1 {
        let min = (i * (i - 1)) / 2;
        let max = (2 * n - i + 1) * i / 2;

        let sub = max - min + 1;
        ans += sub;
        ans = ans % m;
    }
    println!("{}", ans);
}


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

using namespace std;


int main(){
    
    long int S;
    cin >> S;
    
    long int x, y;
    
    x = (1000000000-S%1000000000)%1000000000;
    
    y = (S+x)/1000000000;
    
    
    cout << 0 << " " << 0 << " " << 1000000000 << " " << 1 << " " << x << " " << y << endl;

}



Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <cmath>

#define ll long long int
#define pb push_back
#define mk make_pair
#define pq priority_queue

using namespace std;
typedef pair<int, int> P;
typedef pair<ll, int> Pl;
typedef pair<ll, ll> Pll;
const int inf = 1e9;
const ll linf = 1LL << 50;

int main(int argc, char const* argv[])
{
  int n, a, b;
  cin >> n >> a >> b;
  int res = 0;
  for(int i = 1; i <= n; i++){
    int tmp = i;
    int sum = 0;
    while(tmp){
      sum += tmp % 10;
      tmp /= 10;
    }
    if(a <= sum && sum <= b)res += i;
  }
  cout << res << endl;
	return 0;
}


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

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>
#include<iomanip>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, double> pid;
typedef pair<double, int> pdi;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

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

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

int N;
int A[300010];
int SUM[300010];

void func()
{
	priority_queue<int> pq;
	int s = 0;
	rrep(i, 0, 3 * N)
	{
		int t = INF;
		if (SZ(pq) == N)
		{
			t = pq.top();
		}
		
		if (A[i] < t)
		{
			if (SZ(pq) == N)
			{
				pq.pop();
				s -= t;
			}
			s += A[i];
			pq.push(A[i]);
		}

		if (SZ(pq) == N)
		{
			SUM[i] = s;
		}
		else
		{
			SUM[i] = INF;
		}
	}
}

int solve()
{
	int ans = -INF;
	priority_queue<int, vector<int>, greater<int>> pq;
	int s = 0;
	rep(i, 0, 3 * N - 1)
	{
		int t = 0;
		if (SZ(pq) == N)
		{
			t = pq.top();
		}

		if (A[i] > t)
		{
			if (SZ(pq) == N)
			{
				pq.pop();
				s -= t;
			}
			s += A[i];
			pq.push(A[i]);
		}

		if (SZ(pq) == N)
		{
			chmax(ans, s - SUM[i + 1]);
		}
	}

	return ans;
}

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

	cin >> N;
	rep(i, 0, 3 * N)
	{
		cin >> A[i];
	}

	func();
	cout << solve() << endl;

	return 0;
}

Measured memory_bytes: 6768
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <iomanip>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<long double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }
#define INF 1LL<<60

int main() {
    long double A, B;
    cin >> A >> B;
    printf("%lld\n", ll(floor(B*A)));
    return 0;
}

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

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

	int n;
	cin >> n;

	vector<vector<int>> a(3, vector<int>(n));

	for (int i = 0; i < n; i++)
		for (int j = 0; j < 3; j++)
			cin >> a[j][i];

	for (int i = 1; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			int t = 0;
			for (int k = 0; k < 3; k++) {
				if (j == k) continue;
				// a[i][j] = max(a[i][j], a[i][j])
				t = max(t, a[k][i - 1]);
			}
			a[j][i] += t;
		}
	}

	cout << max({a[0][n - 1], a[1][n - 1], a[2][n - 1]}) << "\n";
}

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

int main(void) {
  int n;
  vector<int> d;

  cin >> n;
  for (int i=0; i<n; i++) {
    int tmp;
    cin >> tmp;
    d.push_back(tmp);
  }

  sort(d.begin(), d.end());

  cout << d[n/2] - d[n/2-1] << endl;
  return 0;
}

Measured memory_bytes: 892
//#define _USE_MATH_DEFINES // for C++
//#include <cmath>
//#include <vector>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>


using namespace std;

int BubbleSort(char A[][3], int n){

	char buf[3];


	for (int i = 0; i < n; i++){
		for (int j = n - 1; j > i; j--){
			if (atoi(&A[j][1]) < atoi(&A[j - 1][1])){
				strcpy(buf, &A[j - 1][0]);
				strcpy(&A[j - 1][0], &A[j][0]);
				strcpy(&A[j][0], buf);
			}
		}
	}

	//??????
	printf("%s", &A[0][0]);
	for (int i = 1; i < n; i++) printf(" %s", &A[i][0]);
	printf("\n");

	return 0;
}

int SelectionSort(char A[][3],int n){
	int minj;
	char buf[3];
	
	for (int i = 0; i < n; i++){
		minj = i;
		for (int j = i; j < n; j++){
			if (atoi(&A[j][1]) < atoi(&A[minj][1])){
				minj = j;
			}
		}
		if (minj != i){
			strcpy(buf, &A[minj][0]);
			strcpy(&A[minj][0], &A[i][0]);
			strcpy(&A[i][0], buf);
		}
	}
	
	//??????
	printf("%s", &A[0][0]);
	for (int i = 1; i < n; i++) printf(" %s", &A[i][0]);
	printf("\n");

	return 0;
}

int CheckStable(char A[][3], char B[][3], int n){

	int index1, index2;

	for (int i = 0; i < n - 1; i++){
		index1 = 0;
		index2 = 0;
		if (atoi(&B[i][1]) == atoi(&B[i + 1][1])){
			for (int j = 0; j < n; j++){
				if (strcmp(&B[i][0], &A[j][0]) == 0) index1 = j;
				if (strcmp(&B[i+1][0], &A[j][0]) == 0) index2 = j;
			}
			if (index1 > index2){
				printf("Not stable\n");
				return 1;
			}
		}
	}

	printf("Stable\n");

	return 0;
}

int main(){
	
	int n;
	char A[36][3];
	char C[36][3];
	char D[36][3];

	//??\???
	scanf("%d", &n);
	for (int i = 0; i < n; i++)	scanf("%s", &A[i][0]);
	for (int i = 0; i < n; i++)	strcpy(&C[i][0], &A[i][0]);
	for (int i = 0; i < n; i++)	strcpy(&D[i][0], &A[i][0]);

	BubbleSort(C, n);
	CheckStable(A, C, n);

	SelectionSort(D, n);
	CheckStable(A, D, n);

	return 0;
}

Measured memory_bytes: 1056
/*
title:

url:
*/

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <queue>
#include <limits>
#include <string>
#include <utility>
#include <cstring>
#include <map>

using namespace std;

#define REP(i, n) for (int i = 0; i < (n); i++)
#define INF 1000000007

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

int main()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    int pre[26] = {};
    int post[26] = {};
    for (int i = 0; i < s.size(); i++)
    {
        post[s[i] - 'a']++;
    }
    int ans = 0;
    for (int i = 0; i < s.size(); i++)
    {
        int tmp_ans = 0;
        for (int j = 0; j < 26; j++)
        {
            if (pre[j] > 0 && post[j] > 0)
                tmp_ans++;
        }
        ans = max(ans, tmp_ans);
        pre[s[i] - 'a']++;
        post[s[i] - 'a']--;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

def sol():
    N, C, K = map(int, input().split())
    T = [0] * N

    for i in range(N):
        T[i] = int(input())

    T.sort(reverse=True)
    ans = 0

    nowTime = float('inf')
    nowCount = 0
    for t in T:
        if nowTime - K <= t and nowCount < C:
            nowCount += 1
            continue
        ans += 1
        nowTime = t
        nowCount = 1

    print(ans)

sol()

Measured memory_bytes: 7728
#include <iostream>
#include <stdlib.h>

using namespace std;

int main()
{
    long long int dp[100010];
    for(int i=0; i<100010; i++) dp[i] = 1LL << 60;
    int N,K;
    long long int height[100010];

    cin >> N >> K;
    for(int i=0; i<N; i++)  cin >> height[i];

    dp[0] = 0;
    dp[1] = abs(height[1] - height[0]);

    for(int j=2;j<N;j++){
            for(int k=1; k<=K && ((j-k) >= 0); k++){
                dp[j] = min(dp[j] ,dp[j-k] + abs(height[j-k] - height[j]));
            }
    }

    cout << dp[N-1];


}

Measured memory_bytes: 1792