akhauriyash/Code-Regression huggingface dataset:
//   Rishabh Agarwal
#include <bits/stdc++.h>
#define F first
#define S second
#define MAX 10000003
using namespace std;

typedef long long int ll;
const ll mod = 1e18;
const ll INF= 1e18;
long double PI=3.1415926;

ll power(ll a,ll b){
    if(b==0){
        return 1;
    }
    ll temp=power(a,b/2)%mod;
    if(b%2==0){
        return (temp*temp)%mod;
    }
    else{
        return ((a*temp)%mod*temp)%mod;
    }
}

ll gcd(ll a, ll b) 
{ 
    if (b == 0) 
        return a; 
    return gcd(b, a % b);  
      
} 

vector<ll>v;
vector<ll>::iterator it;
map<ll,ll>mp;

void primeFactors(ll n)  
{  
    // Print the number of 2s that divide n  
    while (n % 2 == 0)  
    {  
        //cout << 2 << " ";  
        mp[2]++;
        n = n/2;  
    }  
  
    // n must be odd at this point. So we can skip  
    // one element (Note i = i +2)  
    for (ll i = 3; i <= sqrt(n); i = i + 2)  
    {  
        // While i divides n, print i and divide n  
        while (n % i == 0)  
        {  
            //cout << i << " ";  
            mp[i]++;
            n = n/i;  
        }  
    }  
  
    // This condition is to handle the case when n  
    // is a prime number greater than 2  
    if (n > 2){ 
        mp[n]++; 
        //cout << n << " "; 
    } 
}  

ll dp[3001][3001];

void solve(string a, string b){
    ll an=a.length();
    ll bn=b.length();
    for(ll x=0; x<=an; x++){
        for(ll y=0; y<=bn; y++){
            dp[x][y]=0;
        }
    }
    for(ll x=1; x<=an; x++){
        for(ll y=1; y<=bn; y++){
            dp[x][y]=max(dp[x-1][y],dp[x][y-1]);
            if(a[x-1]==b[y-1]){
                if(dp[x][y]<=dp[x-1][y-1]+1){
                    dp[x][y]=dp[x-1][y-1]+1;
                }
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll t;
    //cin>>t;
    t=1;
    //ll c=1;
    while(t--){
        string s,t;
        cin>>s>>t;
        solve(s,t);
        string out="";

        ll x=s.length();
        ll y=t.length();
        while(x>0&&y>0){
            if(s[x-1]==t[y-1]){
                out+=s[x-1];
                x--;
                y--;
            }
            else{
                if(dp[x-1][y]>dp[x][y-1]){
                    x--;
                }
                else{
                    y--;
                }
            }
        }

        reverse(out.begin(),out.end());
        cout<<out<<"\n";
        mp.clear();  
        v.clear();
        //cout<<"Case #"<<c<<": "<<ans<<"\n";
        //c++;
    }
    return 0;
}


Measured memory_bytes: 74004
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
#define pb push_back
#define vi vector<int>
#define vpi vector<pair<int,int>>
#define endl "\n"
#define pii pair<int,int>
#define mii map<int,int>
#define int long long int
#define fbo find_by_order
#define ook order_of_key
#define in insert
#define F first
#define S second
#define bug(...)       __f (#__VA_ARGS__, __VA_ARGS__)
#define print(a) for(auto ws: a)cout<<ws<<" "; cout<<endl
#define print1(a,b) for(int ws=0;ws<b;ws++) {cout<<a[ws]<<" ";} cout<<endl
#define all(a) a.begin(), a.end()
#define si set<int>
#define print2(a) for(auto ws: a)cout<<"("<<ws.F<<","<<ws.S<<") "; cout<<endl

template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
	const char* comma = strchr (names + 1, ',');
	cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

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

	cout << setprecision(9) << fixed;

	int n;
	cin >> n;
	int x, y, z;
	cin >> x >> y >> z;
	int dp[n][3];
	dp[0][0] = x;
	dp[0][1] = y;
	dp[0][2] = z;
	for (int i = 1; i < n; ++i)
	{
		cin >> x >> y >> z;
		dp[i][0] = max(dp[i - 1][1] + x, dp[i - 1][2] + x);
		dp[i][1] = max(dp[i - 1][0] + y, dp[i - 1][2] + y);
		dp[i][2] = max(dp[i - 1][1] + z, dp[i - 1][0] + z);

	}
	cout << max({dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]});
	return 0;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
#define ffr(i,a,b) for(i=a;i<b;i++)
#define ffrr(i,a,b) for(i=a;i<=b;i++)
#define ll long long int
#define pf printf
#define mm(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define pii pair<ll,ll>
#define mp(a,b) make_pair(a,b)
#define mmxx 1e18

using namespace std;

int main()
{
    ll n, r, c, x, y, ilim, jlim, i, j;

    while(cin >> r >> c >> n)
    {
        map<pii,ll>mapp;
        mapp.clear();
        int mn[200005], lim[200005];
        ffrr(i,1,r)
        {
            mn[i]=c+1;
            lim[i]=1;
        }
        ffr(i,0,n)
        {
            cin >> x >> y;
            if(x<y) continue;
            mapp[mp(x,y)]=1;
            if(y<mn[x]) mn[x]=y;
            //mn[x]=min(mn[x],y);
        }
        jlim=1;
        ilim=r+1;
        //cout << mapp[mp(3,2)] << endl;

        ffrr(i,2,r)
        {
            //cout << i << " i jlim " << jlim << endl;
            if(mapp.find(mp(i,jlim))!=mapp.end())
            {
                ilim=i;
                break;
            }
            if(mapp.find(mp(i,jlim+1))==mapp.end())
            {
                jlim++;
            }

            lim[i]=jlim;
        }

        //ffrr(i,1,r) cout << mn[i] << " "; cout << "mn\n";
        //ffrr(i,1,r) cout << lim[i] << " "; cout << "lim\n";
        //cout << ilim << endl;

        ffr(i,1,ilim)
        {
            if(mn[i]==c+1) continue;
            if(mn[i]<lim[i])
            {
                //ans found
                break;
            }
        }
        cout << i-1 << endl;

    }
}


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

#define endl '\n'
#define int ll
using namespace std;
typedef long long ll;

map<int, int> odd, even;

int n;
void init();
void process();

int32_t main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    init();
    process();
    cout.flush();
    return 0;
}

void init()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        int x; cin >> x;
        if(i&1)
        {
            if(odd.count(x) == 0) odd[x] = 0;
            odd[x]++;
        }
        else 
        {
            if(even.count(x) == 0) even[x] = 0;
            even[x]++;
        }
    }
    odd[712223] = 0;
    even[712222] = 0;
}

void process()
{
    int oddmx = 712223, oddmx2 = 712223;
    int evenmx = 712222, evenmx2 = 712222;
    for(auto p:odd)
    {
        if(p.second > odd[oddmx]) oddmx2 = oddmx, oddmx = p.first;
        else if(p.second > odd[oddmx2]) oddmx2 = p.first;
    }
    for(auto p:even)
    {
        if(p.second > even[evenmx]) evenmx2 = evenmx, evenmx = p.first;
        else if(p.second > even[evenmx2]) evenmx2 = p.first;
    }

    int ans = 0;
    if(oddmx != evenmx)
    {
        ans = n - odd[oddmx] - even[evenmx];
    }
    else
    {
        ans = min(n - odd[oddmx] - even[evenmx2], n - even[evenmx] - odd[oddmx2]);
    }
    cout << ans << endl;
}



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

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

signed main(){
  string s,t;
  cin >> s >> t;
  bool ret = false;
  vector<int>idx;
  REP(i, s.size()-t.size()+1) {
    bool flag = true;
    REP(j, t.size()) {
      if(s[i+j] == '?' || s[i+j] == t[j]) continue;
      flag = false;
      break;
    }
    if(flag) ret = true, idx.push_back(i);
  }
  if(!ret) {
    cout << "UNRESTORABLE" << endl;
    return 0;
  }
  // cout << idx[0] << endl;
  vector<string>ans_candidate(idx.size());
  REP(j,idx.size()){
    ans_candidate[j]=s;
    REP(i, t.size()) {
      if(ans_candidate[j][i+idx[j]] == '?') ans_candidate[j][i+idx[j]] = t[i];
    }
    REP(i, s.size()) {
      if(ans_candidate[j][i] == '?') ans_candidate[j][i] = 'a';
    }
  }
  // cout << ans_candidate[0] << endl;
  string ans = ans_candidate[0];
  for(int i=1;i<idx.size();i++){
    if(ans > ans_candidate[i])ans = ans_candidate[i];
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include<stack>
#include <cstdlib>
//#include <string>

using namespace std;

int main(){
    stack<int> S;
    int a,b,x;
    string s;
    
    while(cin>>s){
        if(s[0]=='+'){
            a=S.top();S.pop();
            b=S.top();S.pop();
            S.push(a+b); 
        }else if(s[0]=='-'){
            b=S.top();S.pop();
            a=S.top();S.pop();
            S.push(a-b);
        }else if(s[0]=='*'){
            a=S.top();S.pop();
            b=S.top();S.pop();
            S.push(a*b);
        }else{ 
            S.push(atoi(s.c_str()));
        }
    
    }
    cout<<S.top()<<endl;
    return 0;

    
}


Measured memory_bytes: 3172
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <utility>
#include <iomanip>  // std::setprecision()
using namespace std;
using ll = long long;
#define rep(i,a,b) for(int i=(a); i<(b); i++)
#define YES cout << "YES" << endl;
#define NO cout << "NO" << endl;
#define yes cout << "Yes" << endl;
#define no cout << "No" << endl;
#define pai 3.14159265358979323846
ll gcd(ll a, ll b){if (a%b == 0)  return(b);else  return(gcd(b, a%b));}
ll lcm(ll a, ll b){return a * b / gcd(a, b);}
/* map<string,int> */
/* 大文字を小文字に変換 tolower*/
/* 小文字を大文字に変換 toupper*/
/* 辞書順 next_permutation(a.begin(),a.end()) */
 
int main() {
    ll n;
    ll b;
    map <ll,ll> a;
    cin >>n;
    ll sum = 0;
    for(ll i = 0;i<n;i++) {
        cin >> b;
        a[b]++;
        sum += b;
    }
    ll q;
    cin >> q;
    pair <ll,ll> c;
    vector <ll> ans(q);
    for(ll i = 0;i<q;i++) {
        cin >> c.first >> c.second;
        decltype(a)::iterator it = a.find(c.first);
        if (it != a.end()) {
            ll f = a[c.first];
            a[c.first] = 0;
            a[c.second] += f; 
            sum -= c.first *f;
            sum += c.second * f;
            ans[i]  = sum;
        } else {
            ans [i] = sum;
        }
    }
    for(ll i = 0;i<q;i++) {
        cout << ans[i] << endl;
    }
}

Measured memory_bytes: 8392
#include <bits/stdc++.h>
#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 rep2(i,j,n) for(int j=i;j<n;j++)
#define rep3(i,j,n) for(int j=i;j<=n;j++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define sp(n) cout << fixed << setprecision(n)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long ll;
using namespace std;
int main(void){
    int h,w;cin>>h>>w;
    int t[h][w];
    rep(i,h)rep(j,w){
        cin>>t[i][j];
        t[i][j]%=2;
    }
    queue<pair<int,int>> p1,p2;
    //横方向にずらしていく
    rep(i,h){
        rep(j,w-1){
            if(t[i][j]%2==1){
                t[i][j+1]++;
                p1.push({i,j});
                p2.push({i,j+1});
            }
        }
    }
    rep(i,h-1){
        if(t[i][w-1]%2==1){
            t[i+1][w-1]++;
            p1.push({i,w-1});
            p2.push({i+1,w-1});
        }
    }
    int res=p1.size();
    cout<<res<<endl;
    rep(i,res){
        cout<<p1.front().first+1<<" "<<p1.front().second+1<<" "<<p2.front().first+1<<" "<<p2.front().second+1<<endl;
        p1.pop();p2.pop();
    }
}

Measured memory_bytes: 6784
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <math.h>
#include <time.h>

typedef int32_t i32;
typedef int64_t i64;
typedef double f64;

void *const null=(void *)0;
i64 const llinf=4611686018427387903LL;
i64 const mod=1000000009LL;
f64 const pi=3.141592653589793;
f64 const rad=57.295779513082323;

#define CODE_

void swap(i64 *const x,i64 *const y){
    i64 t=*x;
    *x=*y;
    *y=t;
    return;
}

i32 main(void){
    i64 n,m;
    scanf("%lli%*c%lli%*c",&n,&m);
    i64 *a=(i64 *)calloc(n,sizeof(i64));
    for(i64 i=0LL;i<n;++i) scanf("%lli%*c",&a[i]);
    for(i64 k=1LL;k<=m;++k){
        for(i64 i=1LL;i<n;++i){
            i64 u=a[i-1LL],v=a[i];
            if(u-u/k*k>v-v/k*k) swap(&a[i-1LL],&a[i]);
        }
    }
    for(i64 i=0LL;i<n;++i) printf("%lli\n",a[i]);
    return 0;
}



Measured memory_bytes: 2048
n, m = map(int, input().split())

mxa = 0
mnb = n+2

for i in range(m):
    a, b = map(int, input().split())
    mxa = max(mxa, a)
    mnb = min(mnb, b+1)

if mxa > mnb:
    ans = 0
else:
    ans = mnb - mxa

print(ans)

Measured memory_bytes: 3060
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int N;
	cin >> N;
	vector<int> a(N);
	for (int i = 0; i < N; i++) cin >> a[i];
	vector<int> p(N);
	for (int i = 0; i < N; i++) p[i] = i;
	sort(p.begin(), p.end(), [&](int i, int j) {return a[i] < a[j]; });
	vector<int> ip(N);
	for (int i = 0; i < N; i++) ip[p[i]] = i;
	for (int i = 0; i < N; i++) {
		if (ip[i] * 2 < N) cout << a[p[N / 2]] << "\n";
		else cout << a[p[N / 2 - 1]] << "\n";
	}
	return 0;
}

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

int gcd(long long a,long long b){
    if(b == 0) return a;
    return gcd( b , a % b);
}

int find(string str, const string& word) {
  int count = 0;
  for (string::size_type pos = 0; (pos = str.find(word, pos)) != string::npos; pos += word.size()) {
    ++count;
  }
  return count;
}

int main(){
    int n, x;
    int d =0 ;
    int count = 0;
    cin >> n >> x;
    vector<int> l(100);
    for(int i = 0; i < n; ++i){
        cin >> l[i];
    }
    while(d <= x){
        d += l[count];
        count ++;
        if(count > n){
            break;
        }
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define ll long long
#define lld long double
#define ALL(x) x.begin(), x.end()

using namespace std;
const lld eps = (1e-40);

lld dist(lld x1, lld y1, lld x2, lld y2)
{
    return sqrtl((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

int main()
{
    int n;
    cin >> n;
    vector<lld> x(n);
    vector<lld> y(n);
    lld avgx = 0, avgy = 0;
    rep(i, n)
    {
        cin >> x[i] >> y[i];
        avgx += x[i];
        avgy += y[i];
    }
    avgx /= (lld)n;
    avgy /= (lld)n;
    lld ans = -1;
    lld p = 0.1;
    lld d, prevd;

    rep(i, 30000)
    {
        prevd = d;
        int bestid = 0;
        d = dist(avgx, avgy, x[0], y[0]);
        rep(j, n)
        {
            if (d < dist(avgx, avgy, x[j], y[j]))
            {
                d = dist(avgx, avgy, x[j], y[j]);
                bestid = j;
            }
        }
        avgx += (x[bestid] - avgx) * p;
        avgy += (y[bestid] - avgy) * p;

        p *= 0.999;
    }
    printf("%.10Lf\n", d);

    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	
	int[] bingoArr;
	

	public static void main(String[] args) {
		Main mainObj = new Main();
		mainObj.solve();
	}
	
	public void solve() {
		Scanner sc = new Scanner(System.in);
		
		bingoArr = new int[9];
		for(int i = 0; i < 9; i++) {
			bingoArr[i] = sc.nextInt();
		}
		
		int n = sc.nextInt();
		for(int i = 0; i < n; i++) {
			int hole = sc.nextInt();
			
			for(int j = 0; j < 9; j++) {
				if(bingoArr[j] == hole) {
					bingoArr[j] = -1;
					break;
				}
			}
			if(checkBingo()) {
				System.out.println("Yes");
				return;
			}
		}
		sc.close();
		System.out.println("No");
		
	}
	
	public boolean checkBingo() {
		
		//　横
		if(bingoArr[0] == -1 && bingoArr[1] == -1 && bingoArr[2] == -1) {
			return true;
		}
		if(bingoArr[3] == -1 && bingoArr[4] == -1 && bingoArr[5] == -1) {
			return true;
		}
		if(bingoArr[6] == -1 && bingoArr[7] == -1 && bingoArr[8] == -1) {
			return true;
		}
		
		// 縦
		if(bingoArr[0] == -1 && bingoArr[3] == -1 && bingoArr[6] == -1) {
			return true;
		}
		
		if(bingoArr[1] == -1 && bingoArr[4] == -1 && bingoArr[7] == -1) {
			return true;
		}
		
		if(bingoArr[2] == -1 && bingoArr[5] == -1 && bingoArr[8] == -1) {
			return true;
		}
		
		// 斜め
		if(bingoArr[0] == -1 && bingoArr[4] == -1 && bingoArr[8] == -1) {
			return true;
		}
		
		if(bingoArr[2] == -1 && bingoArr[4] == -1 && bingoArr[6] == -1) {
			return true;
		}
		
		return false;
	}
}


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

using namespace std;


void solve() {
    int n,k,q;
    cin >> n >> k >> q;
    vector<int> a(n);
    for (auto& x: a) {
        cin >> x;
    }
    int res = 2e9;
    for (int i = 0; i < n; i++) {
        int mi = a[i];
        vector<int> seg;
        vector<int> candi;
        for (int j = 0; j <= n; j++) {
            if (j == n || a[j] < mi) {
                if ((int)seg.size() >= k) {
                    sort(seg.begin(), seg.end());
                    copy(seg.begin(), seg.end()-k+1, back_inserter(candi));
                }
                seg.clear();
            } else {
                seg.emplace_back(a[j]);
            }
        }
        if ((int)candi.size() >= q) {
            sort(candi.begin(), candi.end());
            int tmp = candi[q-1] - candi[0];
            res = min(res, tmp);
        }
    }
    cout << res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    cout << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int x, c1;
int main() {
	cin >> x;
	if (x != 5 && x != 7) {
	    puts("NO");
	    return 0;
	}
	c1 += (x == 5);
	cin >> x;
	if (x != 5 && x != 7) {
	    puts("NO");
	    return 0;
	}
	c1 += (x == 5);
	cin >> x;
	if (x != 5 && x != 7) {
	    puts("NO");
	    return 0;
	}
	c1 += (x == 5);
	if (c1 != 2) {
	    puts("NO");
	    return 0;
	}
	puts("YES");
	return 0;
} 

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

using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(i) (i).begin(), (i).end()
#define rall(i) (i).begin(), (i).end(), greater<int>()
#define int long long
#define elif else if
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fst first
#define sec second
#define mod 1000000007
#define INF 10e10
template <typename T>

void print(T x)
{
	std::cout << x << " ";
}
template <typename T>

void println(T x)
{
	std::cout << x << "\n";
}

signed main(void) {
	int n, m;
	cin >> n >> m;
	vector<vector<int>>s(m);
	rep(i, m) {
		int k;
		cin >> k;
		rep(j, k) {
			int si;
			cin >> si;
			s[i].pb(si);
		}
	}
	vector<int>p;
	rep(i, m) {
		int pi;
		cin >> pi;
		p.pb(pi);
	}
	int ans = 0;
	bool unmatch = false;
	for (int bit = 0; bit < (1 << n); ++bit) {
		unmatch = false;
		rep(i, m) {//i個目の電球が付いているかを調査
			int on = 0;
			rep(j, s[i].size()) {
				if (bit & (1 << (s[i][j]-1)))on++;
			}
			if (on % 2 != p[i]) {
				unmatch = true;
				break;
			}
		}
		if (unmatch)continue;
		ans++;

	}
	print(ans);
}

Measured memory_bytes: 256
/*
You're my honeybunch, sugar plum
Pumpy-umpy-umpkin
You're my sweetie pie
You're my cuppycake, gumdrop
Snoogums, boogums, you're
The apple of my eye

And I love you so
And I want you to know
That I'm always be right here
And I want to sing
Sweet songs to you
Because you are so dear...

*/
#include<iostream>

#define boost ios::sync_with_stdio(0); cin.tie(0);
#define ll long long
#define endl '\n'
#define F first
#define S second
#define pb push_back
#define pai pair<int, int>
#define ar array

using namespace std;
int const maxn=2e9;
const ll naxn=1e9+7;
ll power(ll x, ll y){
    ll res =1;
    for(int i=0;i<y;i++){
        res = res * x %naxn;
    }
    return res;
}
void solve(){
   ll n;
   cin >>n;
   ll ans =power(10,n)-power(9,n)-power(9,n)+power(8,n);
   ans %=naxn;
   ans= (ans+naxn)%naxn;
   cout << ans << endl;
}

int main(){
   boost;
        solve();
    
}


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

const int a = 4;
const int b = 7;

int main(){
  int n; cin >> n;
  
  while(n >= 0){
    if(n % a == 0){
      cout << "Yes" << endl;
      return 0;
    }else
      n -= b;
  }
  cout << "No" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cstring>
#include <set>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <queue>
#include <deque>
#include <map>
#include <stack>
using namespace std;
#define ll long long
#define pb push_back
#define pp pair<long long,long long>
#define ppp pair<long long, pair<long long,long long> >
#define f first	
#define s second
#define pd pair<double,long long>
ll barr[100100],M=998244353;
void solveTestCase() {
	ll n,i,j,k,l,x,m;
	cin>>n>>x>>m;
	ll pre=x,sum=0;
	map<ll,ll> mp;
	mp[x]=1;
	for (i=1;i<=min(n,m);i++) {
		barr[i]=pre;
		//cout<<pre<<" ";
		sum+=pre;
		pre*=pre;
		pre%=m;
		if (mp.find(pre)!=mp.end())
			break;
		mp[pre]=i+1;
	}
	ll rem = n-i,res=0;
	for (j=mp[pre];j<=i;j++)
		res+=barr[j];
	ll len = i-mp[pre]+1;
	ll times = rem/len;
	ll mod = rem%len;
	sum+=(times*res);
	for (j=mp[pre];j<mp[pre]+mod;j++)
		sum+=barr[j];
	cout<<sum<<'\n';
}
int main() {
	ll t,n,i,j,k,l,m;
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll p;
	t=1;
	//cin>>t;
	for (ll T=1;T<=t;T++) {
		solveTestCase();
	}
	return 0;
}

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

using namespace std;

map<long long, long long> divs;
vector<long long> primes;

void generate_primes(){
  primes.push_back(2);
  for(long long i=3;i*i<=1e12;i+=2){
    bool is_prime=true;
    for(int j=0;primes[j]*primes[j]<=i;j++){
      if(i%primes[j]==0){
        is_prime=false;
        break;
      }
    }
    if(is_prime)primes.push_back(i);
  }
}

void prime_div(long long n){
  for(int i=0;i<primes.size();i++){
    while(n%primes[i]==0){
      divs[primes[i]]++;
      n/=primes[i];
    }
  }
  if(n!=1)divs[n]++;
}

int cumsum(long long n){
  int sum = 0;
  for(int i=1;;i++){
    sum += i;
    if(sum>n)return i-1;
  }
}

int main(){
  long long n;
  cin >> n;
  generate_primes();
  prime_div(n);
  long long ans=0;
  for(auto itr=divs.begin();itr!=divs.end();itr++){
    ans += cumsum(itr->second);
  }
  cout << ans << endl;
}



Measured memory_bytes: 4300
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;

class Program
{
    static void Main()
    {
        var NM = ReadLine().Split().Select(int.Parse).ToArray();
        var N = NM[0];
        var M = NM[1];
        var A = ReadLine().Split(' ').Select(int.Parse).ToArray();
        var B = new int[M];
        var C = new int[M];
        for (int i = 0; i < M; i++)
        {
            var line = ReadLine().Split(' ');
            B[i] = int.Parse(line[0]);
            C[i] = int.Parse(line[1]);
        }
        Array.Sort(A);
        Array.Sort(C, B);

        var Z = new int[A.Length];
        var a = 0;
        for (int i = M-1; i >= 0; i--)
        {
            for (int j = 0; j < B[i]; j++)
            {
                Z[a] = C[i];
                a++;
                if (a >= Z.Length) break;
            }
            if (a >= Z.Length) break;

        }

        var ans = 0L;
        for (int i = 0; i < N; i++)
        {
            ans += Max(A[i], Z[i]);
        }
        WriteLine(ans);
    }
}


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

int main()
{
	char s[5];
	scanf("%s", s);
	
	int A = s[0] - '0', B = s[1] - '0', C = s[2] - '0', D = s[3] - '0';
	int sgn, b, c, d;
	for (sgn = 0; sgn <= 7; sgn++) {
		b = (sgn / 4) * 2 - 1;
		c = ((sgn / 2) % 2) * 2 - 1;
		d = (sgn % 2) * 2 - 1;
		if (A + B * b + C * c + D * d == 7) {
			printf("%d", A);
			if (b == 1) printf("+%d", B);
			else printf("-%d", B);
			if (c == 1) printf("+%d", C);
			else printf("-%d", C);
			if (d == 1) printf("+%d=7", D);
			else printf("-%d=7", D);
			break;
		}
	}
	
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 128
import math
x = int(input())
def ok(y):
    top = 10**500
    bottom = -y//2
    while top - bottom > 1:
        b = (top + bottom)//2
        z = (b+y)**5 - b**5
        if z == x:
            print(b+y,b)
            exit(0)
        elif z > x:
            top = b
        else:
            bottom = b
    if (bottom+y)**5 - b**5 == x:
        print(bottom+y,x)
        exit(0)
    elif (top+y)**5 - b**5 == x:
        print(top+y,top)
        exit(0)
    else:
        return
i = 1
while i*i <= x:
    if x%i == 0:
        ok(i)
        ok(x//i)
    i += 1

Measured memory_bytes: 9276
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int a = sc.nextInt();
		int b = sc.nextInt();
      
      	if( a % 2 == 1 && b % 2 == 1) {
        	System.out.print("Odd");
        }
      	else {
        	System.out.print("Even");
        }
	}
}

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

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

#define ll long long
#define pi pair<int, int>
#define pll pair<ll, ll>

#define MOD 1000000007
#define INF 1000000000000000LL

using namespace std;

int main(){
  int n;cin>>n;
  vector<ll> a(n);
  rep(i, n)cin>>a[i];

  for(auto c:a)if(c==0) { cout<<-0<<endl; return 0;}

  ll result=1;
  ll MAX = 1000000000000000000;
  for(auto c:a){
    // same as result*c>MAX
    if(result>MAX/c) { cout<<-1; return 0;}
    result *= c;
  }

  cout<<result<<endl;

  return 0;
}

Measured memory_bytes: 4000
#pragma GCC optimize("Ofast")  
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
using namespace std;
#define IO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define int long long 
#define endl "\n"
#define all(x) (x).begin(),(x).end()
const int MOD = 1e9+7;
const int mxN = 2e5+3;

void solve(){
	int n,W;
	scanf("%lld %lld", &n, &W);
	vector<int> dp(W+1, 0);				// dp[0 ... W]
	
	for(int i = 0; i < n; ++i){
		int wei,val;
		scanf("%lld %lld", &wei, &val);
		// we are going backward in this for loop because we can have one type of item only once in the knapsack.
		// If we can have multiple items of same type , then we should write a for loop in forward direction
		for(int weight_al = W - wei; weight_al >= 0; --weight_al){
			dp[weight_al + wei] = max( dp[weight_al + wei] , dp[weight_al] + val);
		}
	}
	int ans = 0;
	for(int i = 0; i <= W; ++i){
		ans = max(ans , dp[i]);
	}
	printf("%lld\n", ans);
}

int32_t main(){
	IO;
	int nT = 1;
	//cin >> nT;
	for(int i = 1; i <= nT; ++i)
		solve();
	return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<string>
#include<utility>
#include<queue>
#include<tuple>
#include<stdio.h>
#define rep(i, n) for(int i=0;i<n;i++)
using namespace std;
int main(){
	int n;
	cin>>n;
	int a[n];
	rep(i, n){
		cin>>a[i];
	}
	int long long b, c=1000000;
	for(int i=1;i<=100;i++){
		b=0;
		rep(j, n){
			b+=pow((a[j]-i), 2);
		}
		if(b<c){
			c=b;
		}
	}
	cout<<c<<endl;
	return 0;
}

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

using namespace std;

#define REP(i,n) for(ll (i) = (0); (i) < (n); ++i)
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define ALL(v) v.begin(),v.end()
#define INF 1100000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007
#define Decimal fixed << setprecision(20)
#define EPS 1e-9


typedef long long ll;
typedef pair<ll, ll> P;


ll comb[51][51];
void makeComb()
{
  comb[0][0] = 1;
  for (ll i = 0; i <= 50; i++) {
    for (ll j = 0; j <= i; j++) {
      if (i == 0 || j == 0 || j == i)
        comb[i][j] = 1;
      else
        comb[i][j] = comb[i-1][j] + comb[i-1][j-1];
    }
  }
}

int main()
{
  makeComb();
  /*for (ll i = 0; i < 10; i++) {
    for (ll j = 0; j < 10; j++) {
      cout << setw(3) << comb[i][j] << ' ';
    }
    cout << endl;
  }*/

  ll N, A, B;
  cin >> N >> A >> B;
  vector<ll> v(N);
  REP(i, N) cin >> v[i];
  sort(ALL(v), greater<ll>());
  //cout << endl;
  //for (ll i = 0; i < N; i++) cout << v[i] << endl;
  //cout << endl;

  long double sum = 0;
  for (ll i = 0; i < A; i++) { sum += v[i]; }
  cout << Decimal << (sum / A) << endl;


  if (v[0] == v[A - 1]) {
    //cout << "1:" << endl;
    // v[0]の個数を調べる
    ll num = 0;
    while (v[num] == v[0]) num++;
    ll cnt = 0;

    // comb(num, i) i = A to B
    // ただし, A to B中にv[0]でないものが現れたら以降は数えない
    for (int i = A - 1; i < min(num, B); i++) {
      // 0-idxであることに注意.iではなくi+1
      //cout << num << "C" << (i + 1) << endl;
      cnt += comb[num][i + 1];
    }
    cout << cnt << endl;
  } else {
    //cout << "2:" << endl;
    // v[A-1]の個数を調べる
    int numa = 0;
    REP(i, N) if (v[i] == v[A - 1]) numa++;
    // 選ばなくてはいけないv[A-1]と同じ数の個数を調べる
    int num = 0;
    REP(i, A) if (v[i] == v[A - 1]) num++;
    cout << comb[numa][num] << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
  int N;
  cin >> N;
  char S[N];
  cin >> S;

  int i, j, k;
  int max = 0;
  int tmp;
  bool isfollow = false;
  bool isj = false;
  for(i = 1; i < N; i++){
    tmp = 0;
    for(j = 0; j < i; j++){
      // 前の確認
      if (j != 0){
        for(k = j-1; k >= 0; k--){
          if(S[j] == S[k]){
            isfollow = true;
            //cout << j << k << endl;
          }

        }
      }
      if(isfollow == false){
        for(k = i; k < N; k++){
          if(S[j] == S[k]){
            isj = true;
            break;
          }
        }
        if (isj){
          tmp++;
        }
      }
      isfollow = false;
      isj = false;
    }
    //cout << tmp << endl;
    if (tmp > max){
      max = tmp;
    }
  }

  cout << max;
  return 0;

}


Measured memory_bytes: 256
from functools import reduce
import math

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)

    # N の逆元
    # N_inv = pow(N,MOD-2,MOD)

    # nCr
    # Nの階乗 * rの階乗の逆元 * n-rの階乗の逆元
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")

    # 大きな素数
    MOD = 10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N = int(input())
    if N>999:
        print('ABD')
    else:
        print('ABC')
        
if __name__ == '__main__':
    main()


Measured memory_bytes: 3572
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<functional>
#include<iomanip>
#include<cmath>
#include<queue>
#include<limits>
#include<cassert>
#include<set>
#include<tuple>
#include<map>
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define None cout<<"None"<<endl
typedef long long ll;
using namespace std;

int main() {
	string S; cin >> S;
	int sum = 700;
	for (int i = 0; i < 3; ++i) {
		if (S[i] == 'o') sum += 100;
	}
	cout << sum << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define Hello ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define ll long long
int main()
{
    Hello
    ll n, mn = 1e12;
    cin >> n;
    for(ll i = 1; i * i <= n; i++){
        if(n % i == 0){
            ll sec = n/i;
            mn = min(mn, i + sec - 2);
        }
    }
    cout << mn;
    return 0;
}

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

#define sc second
#define fr first

#define ll long long
#define pi pair<int,int>
#define ppi pair<pi,pi>
#define mp make_pair
using namespace std;

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "


int main()
{

    ios::sync_with_stdio(0);
    cin.tie(0) , cout.tie(0);

    set<int>s;
    for(int i = 0;i < 3;i++)
    {
        int x; cin >> x;
        s.insert(x);
    }
    if(s.size() == 2)
        cout << "Yes\n";
    else
        cout << "No\n";



    return 0;
}


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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,a,b) for(int i=(a);i<(b);i++)
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second

using vint=vector<int>;
using pint=pair<int,int>;
using vpint=vector<pint>;

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

template<class A,class B>
ostream& operator<<(ostream& ost,const pair<A,B>&p){
	ost<<"{"<<p.first<<","<<p.second<<"}";
	return ost;
}

template<class T>
ostream& operator<<(ostream& ost,const vector<T>&v){
	ost<<"{";
	for(int i=0;i<v.size();i++){
		if(i)ost<<",";
		ost<<v[i];
	}
	ost<<"}";
	return ost;
}

signed main(){
	int n;cin>>n;
	string s,t;
	cin>>s>>t;
	string ans;
	rep(i,n){
		ans+=s[i];
		ans+=t[i];
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<algorithm>
#include<complex>
#include<ctype.h>
#include<iomanip>
#include<iostream>
#include<map>
#include<math.h>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<stdio.h>
#include<string>
#include<string>
#include<vector>

using namespace std;
typedef long long ll;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("Yes")
#define p_no() p("No")

const ll mod = 1e9 + 7;
const ll inf = 1e18;

ll dp[51][51][2510] = {};

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

    // input
    ll N, A;
    cin >> N >> A;

    vector<ll> X(N+1);
    X[0] = 0;
    FOR(i, 1, N+1){
        cin >> X.at(i);
    }

    // reset (必要？)
    FOR(j, 1, 51){
        FOR(k, 1, 51){
            FOR(s, 0, 2501){
                dp[j][k][s] = 0;
            }
        }
    }

    FOR(i, 0, 51){
        dp[i][0][0] = 1;
    }

    FOR(j, 1, N+1){
        FOR(k, 1, N+1){
            if(j<k){
                continue;
            }

            FOR(s, 0, N*50+1){
            //FOR(s, 0, 51){ // debug
                if(s-X[j] < 0){
                    // X[j]を足してもsには届かない場合
                    dp[j][k][s] = dp[j-1][k][s]; // stay
                }
                else{
                    ll stay = dp[j-1][k][s];
                    ll plus = dp[j-1][k-1][s-X[j]];
                    dp[j][k][s] = stay + plus;
                }
                //cout << "dp " << j << " " << k << " " << s << " " << dp[j][k][s] << endl;
            }
        }
    }

    ll sum = 0;
    FOR(k, 1, N+1){
        sum += dp[N][k][k*A];
    }

    p(sum);
    
    return 0;
}

Measured memory_bytes: 50176
#include <iostream>
#include <iomanip>
#include <ios> 
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <bitset>
#include <map>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define sz(c) ((int)(c).size())
#define mp make_pair

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
//typedef pair<int, int> P;
//typedef pair<int, pair<int, int> > PP;
//const int MAX=;



int main(){
	int N;
	cin>>N;
	int le=0, ri=N;
	int ls, rs;
	cout<<0<<endl;
	fflush(stdout);
	string S;
	cin>>S;
	if(S[0]=='V')return 0;
	if(S[0]=='M'){ls=0;rs=0;}
	if(S[0]=='F'){ls=1;rs=1;}
	while(true){
		int mi=(le+ri)/2;
		int ms;
		cout<<mi<<endl;
		fflush(stdout);
		string T;
		cin>>T;
		if(T[0]=='V') break;
		if(T[0]=='M'){
			ms=0;
		}
		if(T[0]=='F'){
			ms=1;
		}
		
		if((mi+le)%2 != (ms+ls)%2){
			ri=mi;
			rs=ms;
		}
		else{
			le=mi;
			ls=ms;
		}
	}
}

Measured memory_bytes: 852
using System;
using System.Collections.Generic;
using System.Linq;

namespace AizuOnlineJudge
{
    class Program
    {
        static void Main(string[] args)
        {
            var sep = "\n####################\n";
            var n = int.Parse(Console.ReadLine());

            var dic = new Dictionary<string, int>();

            for(var i = 0; i < n; ++i)
            {
                var arr = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
                var key = $"{arr[0]} {arr[1]} {arr[2]}";
                if (dic.ContainsKey(key))
                    dic[key] += arr[3];
                else
                    dic.Add(key, arr[3]);
            }

            var res = string.Join(sep, Enumerable.Range(1, 4).Select(
                e => string.Join("\n", Enumerable.Range(1, 3).Select(
                    f => " " + string.Join(" ", Enumerable.Range(1, 10).Select(
                        g => dic.ContainsKey($"{e} {f} {g}") ? dic[$"{e} {f} {g}"] : 0
                        ))))));
            Console.WriteLine(res);
        }
    }
}


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

ll N, K;
string S;

struct lcr {
  ll l, c, r, s, itr;
  lcr(){};
  lcr(ll L, ll C, ll R, ll I) {
    l = L;
    c = C;
    r = R;
    itr = I;
  }
  void sum() { s = l + c + r; }
};

void solve() {
  vector<lcr> p;
  ll itr = 0;
  ll tmp0 = 0, tmp1 = 0;
  for (int i = 0; i < N; i++) {
    if (S[i] == '1') {
      tmp1++;
    }
    else {
      tmp0 = 0;
      itr = i;
      while (S[i] == '0') {
        i++;
        tmp0++;
      }
      i--;
      p.push_back(lcr(tmp1, tmp0, 0, itr));

      tmp1 = 0;
    }
  }

  if (p.size() == 0) {
    cout << N << "\n";
    return;
  }

  ll n = p.size();
  p[n - 1].r = tmp1;
  for (int i = 0; i < n - 1; i++) {
    p[i].r = p[i + 1].l;
  }
  for (int i = 0; i < n; i++) {
    p[i].sum();
  }

  ll S = 0;
  if (K >= n) {
    cout << N << "\n";
    return;
  }
  else {
    S += p[0].l;
    for (int i = 0; i < K; i++) {
      S += (p[i].c + p[i].r);
    }
  }
  ll res = S;
  for (int i = 0; i + K < n; i++) {
    ll d = p[i + K].c + p[i + K].r - p[i].l - p[i].c;
    S += d;
    res = max(res, S);
  }

  cout << res << "\n";
  return;
}

int main() {
  cin >> N >> K >> S;
  solve();
  return 0;
}


Measured memory_bytes: 3988
#include <iostream>
#include <cmath>
#include <map>

const int P = (int)1e9 + 7;
const int MAXN = (int)1e4;

int a[MAXN];

void calc_factor(int x, std::map<int, int>* factor) {
  int sqrt = std::sqrt(x + 0.5);
  for (int i = 2; i <= sqrt; ++i) {
    if (x % i == 0) {
      while (x % i == 0) {
        (*factor)[i] += 1;
        x /= i;
      }
    }
  }
  if (x > 1) (*factor)[x] += 1;
}

int64_t power(int64_t x, int64_t y) {
  int64_t ans = 1;
  x %= P;
  while (y > 0) {
    if (y & 1) ans = ans * x % P;
    x = x * x % P;
    y >>= 1;
  }
  return ans;
}

int64_t inv(int64_t x) {
  return power(x, P - 2);
}

int64_t solve(int n) {
  std::map<int, int> lcm_factor;
  std::map<int, int> factor;
  for (int i = 0; i < n; ++i) {
    factor.clear();
    calc_factor(a[i], &factor);
    for (const auto& node : factor) {
      int prime = node.first;
      int num = node.second;
      // std::cout << prime << " " << num << std::endl;
      if (!lcm_factor.count(prime)) {
        lcm_factor[prime] = num;
      } else {
        if (lcm_factor[prime] < num) {
          lcm_factor[prime] = num;
        }
      }
    }
  }
  int64_t lcm = 1;
  for (const auto& node : lcm_factor) {
    int64_t cur = power(node.first, node.second);
    lcm = lcm * cur % P;
  }
  // std::cout << "lcm = " << lcm << std::endl;
  int64_t ans = 0;
  for (int i = 0; i < n; ++i) {
    ans = (ans + lcm * inv(a[i]) % P) % P;
  }
  return ans;
}

int main() {
  int n;
  std::cin >> n;
  for (int i = 0; i < n; ++i) {
    std::cin >> a[i];
  }
  std::cout << solve(n) << std::endl;
  return 0;
}


Measured memory_bytes: 768
#include<stdio.h>
#include<stdlib.h>
#include<string.h> 

int stack[100],i = 0;

void slaid(int a) 
{
  stack[i++] = a;
}

int main()
{
  int x,k;
  char s[100];
  
  while(scanf("%s", s) != EOF)
    {
      if (s[0] == '+' )
	{
	  x = stack[--i] ;
	  k = stack[--i] + x;
	  slaid(k);
	} 
      else if (s[0] == '-' )
	{
	  x = stack[--i];
	  k = stack[--i] - x;
	  slaid(k);
	} 
      else if (s[0] == '*' )
	{
	  x = stack[--i];
	  k = stack[--i] * x;
	  slaid(k);
	} 
      else 
	{
	  x = atoi(s);
	  slaid(x);
	}
    }
  
  printf("%d\n",stack[--i]);
  
  return 0;
}

Measured memory_bytes: 548
import java.io.*;
import java.util.*;

class Main {

    public static void main(String[]$) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[][] b = new int[n][n];
        int[] wait = new int[n + 1];
        wait[n] = n;
        Queue<Integer>[] deque = new Queue[n];
        for (int i = 0; i < n; i++) {
            deque[i] = new ArrayDeque<>();
            wait[i] = scanner.nextInt() - 1;
            for (int j = 2; j < n; j++) {
                deque[i].add(scanner.nextInt() - 1);
            }
        }
        int[] lastMatch = new int[n];
        int rem = n;
        while (rem > 0) {
            boolean updated = false;
            for (int i = 0; i < n; i++) {
                if (wait[wait[i]] == i) {
                    lastMatch[wait[i]] = lastMatch[i] = Math.max(lastMatch[wait[i]], lastMatch[i]) + 1;
                    updated = true;
                    if (!deque[wait[i]].isEmpty()) {
                        wait[wait[i]] = deque[wait[i]].poll();
                    } else {
                        wait[wait[i]] = n;
                        rem--;
                    }
                    if (!deque[i].isEmpty()) {

                        wait[i] = deque[i].poll();
                    } else {
                        rem--;
                    }
                }
            }
            if (!updated) {
                System.out.println(-1);
                return;
            }
        }
        Arrays.stream(lastMatch).max().ifPresent(System.out::println);
    }

}


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

public class Main {	

	private class Card {
		String mark;
		int num;
	}
	
	public static void main(String[] args) throws IOException {
		new Main().run();
	}

	private void run() throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(reader.readLine());
		Card[] cards1 = new Card[n];
		Card[] cards2 = new Card[n];
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(reader.readLine());
			cards1[i] = new Card();
			cards1[i].mark = st.nextToken();
			cards1[i].num = Integer.parseInt(st.nextToken());
			cards2[i] = cards1[i];
		}
		reader.close();

		quickSort(cards1, 0, n - 1);
		mergeSort(cards2, 0, n);
		
		if (isStable(cards1, cards2)) {
			System.out.println("Stable");
		} else {
			System.out.println("Not stable");
		}
		
		for (int i = 0; i < n; i++) {
			System.out.println(cards1[i].mark + " " + cards1[i].num);
		}
	}

	private boolean isStable(Card[] cards1, Card[] cards2) {
		for (int i = 0; i < cards1.length; i++) {
			if (cards1[i].mark != cards2[i].mark || cards1[i].num != cards2[i].num) {
				return false;
			}
		}
		return true;
	}

	private void mergeSort(Card[] cards, int left, int right) {
		if (left + 1 < right) {
			int mid = left + (right - left) / 2;
			mergeSort(cards, left, mid);
			mergeSort(cards, mid, right);
			merge(cards, left, mid, right);
		}
	}

	private void merge(Card[] cards, int left, int mid, int right) {
		int n1 = mid - left;
		int n2 = right - mid;
		Card[] L = new Card[n1+1];
		Card[] R = new Card[n2+1];
		for(int i = 0; i < n1; i ++) L[i] = cards[left+i];
		for(int i = 0; i < n2; i ++) R[i] = cards[mid+i];
		Card sentinel = new Card();
		sentinel.num = 1 << 30;
		L[n1] = sentinel;
		R[n2] = sentinel;
		int i = 0;
		int j = 0;
		for (int k = left; k < right; k++) {
			if (L[i].num <= R[j].num) {
				cards[k] = L[i++];
			} else {
				cards[k] = R[j++];
			}
		}
	}

	private void quickSort(Card[] cards, int p, int r) {
		if (p < r) {
			int q = partition(cards, p, r);
			quickSort(cards, p, q - 1);
			quickSort(cards, q + 1, r);
		}
	}

	private int partition(Card[] cards, int p, int r) {
		int x = cards[r].num;
		int i = p - 1;
		for (int j = p; j < r; j++) {
			if (cards[j].num <= x) {
				i++;
				swap(cards, i, j);
			}
		}
		swap(cards, i + 1, r);
		return i + 1;
	}
	
	private void swap(Card[] cards, int i, int j) {
		Card temp = cards[i];
		cards[i] = cards[j];
		cards[j] = temp;
	}
}



Measured memory_bytes: 80908
#include <bits/stdc++.h>
using namespace std;
#define Maxn 507
int n,p[Maxn*Maxn];
int f[Maxn][Maxn],g[Maxn][Maxn];
int dx[4],dy[4];
pair<int,int> que[Maxn*Maxn];
bool flag[Maxn][Maxn];
int main()
{
    dx[0]=0,dy[0]=-1;
    dx[1]=0,dy[1]=1;
    dx[2]=-1,dy[2]=0;
    dx[3]=1,dy[3]=0;
    scanf("%d",&n);
    for (int i=1;i<=n*n;i++)
        scanf("%d",&p[i]);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            f[i][j]=min(min(i-1,j-1),min(n-i,n-j));
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            g[i][j]=1;
    int ans=0;
    memset(flag,false,sizeof(flag));
    for (int i=1;i<=n*n;i++)
    {
        int x=(p[i]+n-1)/n;
        int y=p[i]-(x-1)*n;
        ans+=f[x][y];
        g[x][y]=0;
        int lx=0,rx=0;
        que[++rx]=make_pair(x,y);
        flag[x][y]=true;
        while (lx<rx)
        {
            ++lx;
            int nowx=que[lx].first;
            int nowy=que[lx].second;
            flag[nowx][nowy]=false;
            for (int i=0;i<4;i++)
                if (nowx+dx[i]>=1&&nowx+dx[i]<=n&&nowy+dy[i]>=1&&nowy+dy[i]<=n&&f[nowx+dx[i]][nowy+dy[i]]>f[nowx][nowy]+g[nowx][nowy])
                {
                    f[nowx+dx[i]][nowy+dy[i]]=f[nowx][nowy]+g[nowx][nowy];
                    if (!flag[nowx+dx[i]][nowy+dy[i]])
                    {
                        que[++rx]=make_pair(nowx+dx[i],nowy+dy[i]);
                        flag[nowx+dx[i]][nowy+dy[i]]=true;
                    }
                }
        }
    }
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 8988