akhauriyash/Code-Regression huggingface dataset:
const main = (input) => {
  input = input.split(' ');
  const N = parseInt(input[0], 10);
  const x = N*800;
  const y = Math.floor(N/15)*200;
  
  console.log(x-y);
  
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 7372
#include <bits/stdc++.h>
using namespace std;
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 int ll;

#define EPS (1e-7)
#define INF (1e9)
#define LLINF (1e18)
#define PI (acos(-1))
#define MOD (1000000007)
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

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

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    int n = s.size();
    if (n == 2)
    {
        if (s[0] == s[1])
        {
            cout << 1 << ' ' << 2 << endl;
        }
        else
        {
            cout << -1 << ' ' << -1 << endl;
        }
        return 0;
    }
    for (int i = 0; i < n - 2; i++)
    {
        map<char, int> mp;
        mp[s[i]]++;
        mp[s[i + 1]]++;
        mp[s[i + 2]]++;
        for (auto p : mp)
        {
            if (p.second >= 2)
            {
                cout << i + 1 << ' ' << i + 3 << endl;
                return 0;
            }
        }
    }
    cout << -1 << ' ' << -1 << endl;
}

Measured memory_bytes: 512
N, K = [int(_) for _ in input().split()]
P = [int(_) for _ in input().split()]

ans = 0.0
k = 0
v = 0.0
for i in range(N):
    v += (P[i] + 1) / 2
    k += 1
    if k > K:
        v -= (P[i-K] + 1) / 2
        k -= 1
    ans = max(ans, v)
print(ans)


Measured memory_bytes: 32016
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) {
        try (BufferedReader in = new BufferedReader(new InputStreamReader(System.in))){

            while (true) {
                String deck = in.readLine();
                if (deck.equals("-")) break;

                int m = Integer.parseInt(in.readLine());
                for (int i = 0; i < m; i++) {
                    int h = Integer.parseInt(in.readLine());
                    deck = deck.substring(h) + deck.substring(0, h);
                }
                System.out.println(deck);
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}



Measured memory_bytes: 24448
n = int(input())
a_input = [0]*n
b_input = [0]*n
for i in range(n):
    a_input[i],b_input[i]=map(int,input().split())

a_input=a_input[::-1]
b_input=b_input[::-1]

ans=0
for i in range(n):
    a = a_input[i]+ans
    b = b_input[i]
    tmp = a%b
    if tmp==0:
        continue
    ans+=(a//b+1)*b-a
print(ans)


Measured memory_bytes: 11636
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    x,a,b=MI()
    if a>=b:
        print("delicious")
    elif a+x>=b:
        print("safe")
    else:
        print("dangerous")

main()


Measured memory_bytes: 38588
fun main(args: Array<String>) {
    abc077b()
}

fun abc077b() {
    val n = readLine()!!.toInt()

    var max = 1
    var sqrt = 0
    while (true) {
        sqrt++
        if (sqrt * sqrt > n) break
        max = sqrt * sqrt
    }

    println(max)
}


Measured memory_bytes: 31780
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define loop(i,a,b) for(int i=a;i<b;i++)
#define test() int t;cin>>t;loop(test,1,t+1)
#define pb push_back
#define eb emplace_back
#define mkp make_pair
#define nl cout<<"\n"
#define sp cout<<" "
#define F first
#define S second
#define vi vector<int>
#define vl vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<pii>
#define vll vector<pll>
#define MOD 1000000007
#define all(x) x.begin(),x.end()

template<class C> void min_self( C &a, C b ){ a = min(a,b); }
template<class C> void max_self( C &a, C b ){ a = max(a,b); }

ll mod( ll n, ll m=MOD ){ n%=m,n+=m,n%=m;return n; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

unordered_map<long long, int, custom_hash> safe_map;

const int MAXN = 1e5+5;
const int LOGN = 21;
const ll INF = 1e14;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

int main() 
{
    fastio();

    string s;
    cin>>s;

    map<string,int>ans;
    ans["SUN"] = 7;
    ans["SAT"] = 1;
    ans["FRI"] = 2;
    ans["THU"] = 3;
    ans["WED"] = 4;
    ans["TUE"] = 5;
    ans["MON"] = 6;

    cout<<ans[s],nl;
    
    return 0;
}

Measured memory_bytes: 256
#define MOD 1000000007

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

long pow(long a, long b) {
	if (!b) return 1;
	long c = pow(a, b / 2);
	if (b % 2) c = a * c % MOD * c % MOD;
	else c = c * c % MOD;
	return c;
}

int main() {
	int X, Y;
	cin >> X >> Y;
	if ((X * 2 - Y) % 3 || (Y * 2 - X) % 3) cout << 0;
	else {
		int a = (X * 2 - Y) / 3, b = (Y * 2 - X) / 3;
		if (a < 0 || b < 0) cout << 0;
		else {
			vector<long> c(max(a + b, a) + 1, 1), d(max(a + b, a) + 1, 1);
			for (int i = 1; i <= max(a + b, a); i++) {
				c[i] = c[i - 1] * i % MOD;
				d[i] = pow(c[i], MOD - 2);
			}
			cout << c[a + b] * d[a] % MOD * d[b] % MOD;
		}
	}
}

Measured memory_bytes: 10624
#include <iostream>
using namespace std;
int main(){
    string str;
    cin >> str;
    int n=str.size();
    int flag1=0, flag2=0, flag3=0;
    for(int i=0;i<n-i-1;i++){
        if(str[i]!=str[n-i-1]) flag1=1;
    }

    for(int i=0;i<(n-1)/2-i-1;i++){
        if(str[i]!=str[(n-1)/2-i-1]) flag2=1;
    }

    for(int i=0;(n+3)/2+i-1<n-i-1;i++){
        if(str[(n+3)/2+i-1]!=str[n-i-1]) flag3=1;
    }

    if(flag1||flag2||flag3) cout << "No" << endl;
    else cout << "Yes" << endl;
    return 0;
}

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

using namespace std;

int main(){
    int n,m, x,y,suma = 0;
    vector<pair<int,int>> b;
    vector<int> a;
    cin >> n;   
    for(int i = 0; i < n; i++){
        cin >> x;
        a.push_back(x);
    }
    cin >> m;
    for(int i = 0; i < m; i++){
        cin >> x >> y;
        b.push_back(make_pair(x,y));
    }

    for(int i = 0; i < m;i++){
        for(int j = 0; j < n;j++){
            if(j == b[i].first - 1) suma += b[i].second;
            else suma += a[j];
        }
        cout << suma << endl;
        suma = 0;
    }
        
        
    return 0;
}

Measured memory_bytes: 3584
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<map>
#include<queue>
#include<deque>
#include<iomanip>
#include<tuple>
using namespace std;
typedef long long int LL;
typedef pair<int,int> P;
typedef pair<LL,int> LP;
const int INF=1<<30;
const LL MAX=1e9+7;

void array_show(int *array,int array_n,char middle=' '){
	for(int i=0;i<array_n;i++)printf("%d%c",array[i],(i!=array_n-1?middle:'\n'));
}
void array_show(LL *array,int array_n,char middle=' '){
	for(int i=0;i<array_n;i++)printf("%lld%c",array[i],(i!=array_n-1?middle:'\n'));
}
void array_show(vector<int> &vec_s,int vec_n=-1,char middle=' '){
	if(vec_n==-1)vec_n=vec_s.size();
	for(int i=0;i<vec_n;i++)printf("%d%c",vec_s[i],(i!=vec_n-1?middle:'\n'));
}
void array_show(vector<LL> &vec_s,int vec_n=-1,char middle=' '){
	if(vec_n==-1)vec_n=vec_s.size();
	for(int i=0;i<vec_n;i++)printf("%lld%c",vec_s[i],(i!=vec_n-1?middle:'\n'));
}

LL n,m;
vector<LL> v1,v2;

bool check(LL a){
	LL b,c;
	int i,j;
	c=0;
	for(i=0;i<n;i++){
		b=a/v2[i];
		if(b<v1[i])c+=v1[i]-b;
	}
	if(c<=m)return true;
	return false;
}

int main(){
	int i,j,k;
	LL a,b,c;
	cin>>n>>m;
	for(i=0;i<n;i++){
		cin>>a;
		v1.push_back(a);
	}
	sort(v1.begin(),v1.end());
	for(i=0;i<n;i++){
		cin>>a;
		v2.push_back(a);
	}
	sort(v2.rbegin(),v2.rend());
	LL z[3]={-1,(LL)1<<40};
	while(z[1]-z[0]>1){
		z[2]=(z[0]+z[1])/2;
		if(check(z[2]))z[1]=z[2];
		else z[0]=z[2];
	}
	cout<<z[1]<<endl;
}

Measured memory_bytes: 4848
#include <bits/stdc++.h>
#define rep(i,n) for(int i= 0; i < (n); i++)
using namespace std;
int main(){
    string s, t;
    cin >> s >> t;
    int cnt = 0;
    rep(a, 3){
        if(s[a] == t[a]){
            cnt += 1;
        }
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <queue>
#include <tuple>
#include <cstring>
#include <cctype>
#include <ios>
#include <iomanip>
#include <bitset>
#include <cstdlib>

#define INF 200000000
#define MOD 1000000007
//#define int long long int
#define ll long long int
#define _tilde_ ~

using namespace std;

int main()
{
    string s;
    cin >> s;
    int length = s.length();

    for(int bits = 0 ; bits < (1 << length) ; bits++)
    {
        int ans = s[0] - '0';   //C++には文字列について一文字ずつintがたにする関数が用意されていないので０を引いて再現する．
        //cout << " " << bitset<4>(bits) << endl;
        for(int i = 1;i < length ; ++i )
        {
            if(bits & (1 << i))     //論理演算に注意． == ではないよ
            {
                ans += (s[i] - '0');
                //cout << "+";
            }else{
                ans -= (s[i] - '0');
                //cout << "-";
            }
        }
        //cout << ans << endl;
        if(ans == 7)
        {
            cout << s[0];
            for(int i = 1 ; i < length;i++)
            {
                if(bits & (1 << i))     //論理演算に注意． == ではないよ
                {
                    cout << "+";
                }else{
                    cout << "-";
                }
                cout << s[i];
            }
            cout << "=7" << endl;
            return 0;
        }
    }
    //cout << "error" << endl;
    return 0;
}


Measured memory_bytes: 256
from itertools import product
S=input()
s=[]
for i in range(len(S)):
    s.append(int(S[i]))
L=len(S)-1
l=list(product([1,0],repeat=L))
a=0
for i in range(len(l)):
    t=0
    a+=s[-1]
    for j in range(L-1,-1,-1):
        if l[i][j]:
            t+=1
        else:
            t=0
        a+=s[j]*10**t
print(a)

Measured memory_bytes: 3188
def checker():
    s = input()
    if s[0] != "A":
        return 0
    if s[2:-1].count("C") != 1:
        return 0
    num = s.index("C")
    s = s[1:num] + s[num+1:]
    if s != s.lower():
        return 0
    return 1

l = ["WA", "AC"]

print(l[checker()])


Measured memory_bytes: 2940
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import *
from heapq import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

N = read()
A = reads()

c1 = sum(a % 2 == 1 for a in A)
c2 = sum(a % 4 == 2 for a in A)
c4 = sum(a % 4 == 0 for a in A)

if c1 > c4 + 1 or (c1 == c4 + 1 and c2 > 0):
  print("No")
else:
  print("Yes")


Measured memory_bytes: 62576
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
#include <bitset>
#include <string>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <list>
#include <deque>
using namespace std;
#define INF 10000000
#define LLINF 100000000000000
typedef pair<int, int> P;
typedef long long ll;
#define pb push_back
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define VSORT(v) sort(v.begin(), v.end());
#define fi first
#define se second
#define out(x) cout << x << endl;
int dx[] = { 1, 0, -1, 0 }, dy[] = { 0,1,0,-1 };
ll MOD = 1000000007;

int n;
int a[100005] = { 0 };
int ss[100005] = { 0 };
int se[100005] = { 0 };
int sl[100005] = { 0 };

int main() {
	int res = 0;
	cin >> n;
	rep(i, n) cin >> a[i];
	int s = 0;
	int now = 0;
	int cnt = 1;
	for (int i = 0; i < n - 1; i++) {
		if (a[i] != a[i + 1]) {
			cnt++;
			if (i == n - 2) {
				ss[now] = a[s];
				se[now] = a[n - 1];
				sl[now] = cnt;
				//out(sl[now]);
				now++;
			}
		}
		else {
			ss[now] = a[s];
			se[now] = a[i];
			sl[now] = cnt;
			now++;
			s = i + 1;
			cnt = 1;
			if (i == n - 2) {
				ss[now] = a[n - 1];
				se[now] = a[n - 1];
				sl[now] = 1;
				now++;
			}
		}
	}
	for (int i = 1; i < now - 1; i++) {
		int sum = 0;
		if (sl[i] % 2 == 0) {
			if (se[i - 1] != ss[i + 1]) sum = sl[i - 1] + sl[i] + sl[i + 1];
		}
		else {
			if (se[i - 1] == ss[i + 1]) sum = sl[i - 1] + sl[i] + sl[i + 1];
		}
		res = max(res, sum);
	}
	for (int i = 0; i < now; i++) {
		//cout << ss[i] << " " << se[i] << " " << sl[i] << endl;
		res = max(res, sl[i]);
	}
	for (int i = 0; i < now - 1; i++) {
		res = max(res, sl[i] + sl[i + 1]);
	}
	out(res);
	return 0;
}


Measured memory_bytes: 4092
#include <bits/stdc++.h>
#define mod 1000000007
#define mod998 998244353
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define mkp make_pair
typedef long long ll;
using namespace std;

int x;

int main() {
	cin >> x;
	puts((x < 1200) ? "ABC" : "ARC");
}

Measured memory_bytes: 256
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <utility>
#include <cmath>
#include <stdlib.h> 
#include <stdio.h>
#include <iterator>
#include <chrono>
#include <iomanip>
#include <set>
#include <map>
#include <list>
#include <iterator>
#include <deque>
#include <stack>
#include <queue>
#include <fstream>
#include <limits>
#include <unordered_map>
#include <bitset>
#include <numeric>
#include <sstream>
#include <random>
#include <cassert>

using namespace std;
#define ffor(n) for(int i = 0; i < n; i++)
#define fffor(n) for(int j = 0; j < n ; j++)
int INF = 1e9 + 7;


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

	string s;
	cin >> s;
	if (s == "RRR") cout << 3;
	else if (s == "RRS" || s == "SRR") cout << 2;
	else {
		int count = 0;
		for (auto e : s) if (e == 'R') count++;
		cout << min(count, 1);
	}
}




/*
C:\Users\User\Desktop\comp_programming\final_straw_after_this_im_switching_to_vs_code\final_straw_after_this_im_switching_to_vs_code.cpp
*/

Measured memory_bytes: 3636
#include<iostream>
#include<vector>
#include<queue>
#include<climits>
#include<map>
#include<set>
using namespace std;
#define ll long long

void dfs(int x,int y,vector<vector<char> >&mat,vector<vector<int> >&visited,int cnt)
{
	visited[x][y]=cnt;
	if(x-1>=1 && visited[x-1][y]==-1 && mat[x-1][y]=='.')
	{
		dfs(x-1,y,mat,visited,cnt);
	}
	if(x+1<mat.size() && visited[x+1][y]==-1 && mat[x+1][y]=='.')
	{
		dfs(x+1,y,mat,visited,cnt);
	}
	if(y-1>=1 && visited[x][y-1]==-1 && mat[x][y-1]=='.')
	{
		dfs(x,y-1,mat,visited,cnt);
	}
	if(y+1<mat[0].size() && visited[x][y+1]==-1 && mat[x][y+1]=='.')
	{
		dfs(x,y+1,mat,visited,cnt);
	}
	return;
}
int main()
{
	ll n,m,i,j;
	cin>>n>>m;
	ll x,y;
	cin>>x>>y;
	ll dx,dy;
	cin>>dx>>dy;
	vector<vector<char> >mat(n+1,vector<char>(m+1));
	vector<vector<int> >visited(n+1,vector<int>(m+1));
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			cin>>mat[i][j];
			visited[i][j]=-1;
		}
	}
	ll cnt=1;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			if(visited[i][j]==-1&& mat[i][j]=='.')
			{
				dfs(i,j,mat,visited,cnt);
				cnt++;
			}
		}
	}
	int req=visited[dx][dy];
	if(mat[dx][dy]=='#' || mat[x][y]=='#')
	{
		cout<<-1<<"\n";
	}
	else if(req==visited[x][y])
	{
		cout<<0<<"\n";
	}
	else
	{
		map<int,set<int> >g;
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m;j++)
			{
				int p,k;
				for(p=i-2;p<=i+2;p++)
				{
					for(k=j-2;k<=j+2;k++)
					{
						if(p<=n && p>=1 && k>=1 && k<=m && visited[p][k]!=-1)
						{
							if(visited[p][k]!=visited[i][j])
							{
								g[visited[i][j]].insert(visited[p][k]);
							}
						}
					}
				}
			}
		}
		int src=visited[x][y];
		queue<int>q;
		int depth[cnt];
		for(i=1;i<cnt;i++)
		{
			depth[i]=INT_MAX;
		}
		depth[src]=0;
		q.push(src);
		while(!q.empty())
		{
			int node=q.front();
			q.pop();
			for(auto it=g[node].begin();it!=g[node].end();it++)
			{
				if(depth[*it]==INT_MAX)
				{
					depth[*it]=depth[node]+1;
					q.push(*it);
				}
			}
			if(depth[req]!=INT_MAX)
			{
				break;
			}
		}
		if(depth[req]==INT_MAX)
		{
			cout<<-1<<"\n";
		}
		else
		cout<<depth[req]<<"\n";
	}
}

Measured memory_bytes: 48188
#include <bits/stdc++.h>
#define sz(c)       int(c.size())
#define rep(i,a,b)  for (int i=a; i<(b); ++i)
#define per(i,a,b)  for (int i=(b)-1; i>=(a); --i)
#define fore(c,...) for (auto &__VA_ARGS__:(c))
#define x first
#define y second
using namespace std;
using ll = long long;
using ld = long double;
using point = pair<ll,ll>;
using circle = pair<pair<ld,ld>,ld>;

circle circleFromTwoPoints(point p1,point p2) {
  auto x1 = p1.x;
  auto y1 = p1.y;
  auto x2 = p2.x;
  auto y2 = p2.y;
  auto dx=x2-x1;
  auto dy=y2-y1;
  auto x=x1+(ld)dx/2;
  auto y=y1+(ld)dy/2;
  return {{x,y},sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1))/2};
}

circle circleFromThreePoints(point p1,point p2,point p3) {
  auto x1 = p1.x;
  auto y1 = p1.y;
  auto x2 = p2.x;
  auto y2 = p2.y;
  auto x3 = p3.x;
  auto y3 = p3.y;

  auto a = x1 * (y2 - y3) - y1 * (x2 - x3) + x2 * y3 - x3 * y2;
  if (a==0) {
	  return {{0,0},-1};
  }

  ld b = (ld)(x1 * x1 + y1 * y1) * (y3 - y2)
        + (ld)(x2 * x2 + y2 * y2) * (y1 - y3)
        + (ld)(x3 * x3 + y3 * y3) * (y2 - y1);

  ld c = (ld)(x1 * x1 + y1 * y1) * (x2 - x3)
        + (ld)(x2 * x2 + y2 * y2) * (x3 - x1)
        + (ld)(x3 * x3 + y3 * y3) * (x1 - x2);

  ld x = -b / (2 * a);
  ld y = -c / (2 * a);

  return {{x,y},sqrt((x-x1)*(x-x1)+(y-y1)*(y-y1))};
}

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

	int n;
	cin>>n;
	vector<point> p(n);
	fore(p,i) cin>>i.first>>i.second;

	ld res=-1;
	rep(i,0,n) rep(j,i+1,n) {
		auto c=circleFromTwoPoints(p[i],p[j]);
		if (c.second<0) continue;

		ld x,y,tmp;
		tmp=c.second;
		x=c.first.x;
		y=c.first.y;
		fore(p,l) tmp=max(tmp,sqrt((x-l.x)*(x-l.x)+(y-l.y)*(y-l.y)));

		if (res<0 || res>tmp) res=tmp;
	}

	rep(i,0,n) rep(j,i+1,n) rep(k,j+1,n) {
		auto c=circleFromThreePoints(p[i],p[j],p[k]);
		if (c.second<0) continue;

		ld x,y,tmp;
		tmp=c.second;
		x=c.first.x;
		y=c.first.y;
		fore(p,l) tmp=max(tmp,sqrt((x-l.x)*(x-l.x)+(y-l.y)*(y-l.y)));

		if (res<0 || res>tmp) res=tmp;
	}

	cout<<res<<'\n';
}


Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
const char nl = '\n';
using namespace std;
using ll = long long;
using ld = long double;
const int MOD = 1e9+7;
const int N = 205, X = 1e5+10;

int n, x;
int s[N];
int dp[2][X]; // dp[i][j] = # of ways to end with j, last mod i

void add(int& a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> x;
  for (int i = 0; i < n; i++) {
    cin >> s[i];
  }
  sort(s, s + n, greater<int>());
  dp[0][x] = 1;
  for (int i = 0; i < n; i++) {
    memset(dp[1], 0, sizeof dp[1]);
    // take self
    for (int j = 0, rem = 0; j <= x; j++) {
      add(dp[1][rem], dp[0][j]);
      if (++rem == s[i]) {
        rem = 0;
      }
    }
    // don't take self
    for (int j = 0; j <= x; j++) {
      dp[1][j] = (dp[1][j] + (ll) dp[0][j] * (n - i - 1)) % MOD;
    }
    swap(dp[0], dp[1]);
  }
  int ans = 0;
  for (int i = 0; i < s[n-1]; i++) {
    ans = (ans + (ll) i * dp[0][i]) % MOD;
  }
  cout << ans << nl;
  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
#define sp(x) fixed << setprecision(x)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const int MOD = 1000000007;
//const int MOD = 998244353;
const int inf = (1<<30)-1;
const ll INF = (1LL<<60)-1;
const double pi = acos(-1.0);
const double EPS = 1e-10;
template<typename T> bool chmax(T &x, const T &y) {return (x < y)? (x = y, true) : false;};
template<typename T> bool chmin(T &x, const T &y) {return (x > y)? (x = y, true) : false;};

int main(){
    string S;
    cin >> S;
    if(S.back() == 's') S += "es";
    else S += "s";
    cout << S << endl;
}

Measured memory_bytes: 3596
/*
  AOJ #3101
  Shortest Crypt
  @kankichi57301
 */
#include <stdio.h>
#include <string.h>
#define abs(x) ((x>0)?(x):(-(x)))

int n;
char s[100001];
int ns,ew;

int main()
{
  int i;
  char c;
  ns=0;ew=0;
  scanf("%d",&n);
  scanf("%s",s);
  for(i=0;i<n;i++)
    {
      c=s[i];
      if('A'<=c && c<='M')
	ns ++;
      if('N'<=c && c<='Z')
	ns --;
      if('a'<=c && c<='m')
	ew ++;
      if('n'<=c && c<='z')
	ew --;
    }
  printf("%d\n",abs(ns)+abs(ew));
  if(ns>0)
    for(i=0;i<ns;i++)
      putchar('A');
  if(ns<0)
    for(i=0;i<-ns;i++)
      putchar('N');
  if(ew>0)
    for(i=0;i<ew;i++)
      putchar('a');
  if(ew<0)
    for(i=0;i<-ew;i++)
      putchar('n');
  putchar('\n');
  return(0);
}



Measured memory_bytes: 2108
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
#ifdef _MSC_VER
inline unsigned int __builtin_popcount(unsigned int x) { return __popcnt(x); }
#endif // _MSC_VER
#define def 0
template<class V, int NV> struct SegTree { //[l,r)
    V comp(V& l, V& r) { return l | r; };

    vector<V> val; SegTree() { val = vector<V>(NV * 2, def); }
    V get(int x, int y, int l = 0, int r = NV, int k = 1) {
        if (r <= x || y <= l)return def; if (x <= l && r <= y)return val[k];
        auto a = get(x, y, l, (l + r) / 2, k * 2); 
        auto b = get(x, y, (l + r) / 2, r, k * 2 + 1);
        return comp(a, b);
    }
    void update(int i, V v) {
        i += NV; val[i] = v;
        while (i>1) i >>= 1, val[i] = comp(val[i * 2], val[i * 2 + 1]);
    }
    void add(int i, V v) { update(i, val[i + NV] + v); }
    V operator[](int x) { return get(x, x + 1); }
};
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     @hamayanhamayan0
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/














int N; string S; int Q;
SegTree<ll, 1 << 19> st;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S >> Q;
    rep(i, 0, N) st.update(i, 1LL << (S[i] - 'a'));
    rep(_, 0, Q) {
        int t; cin >> t;
        if (t == 1) {
            int i; char c; cin >> i >> c; i--;
            st.update(i, 1LL << (c - 'a'));
        }
        else {
            int l, r; cin >> l >> r; l--;
            ll msk = st.get(l, r);
            int ans = __builtin_popcount(msk);
            printf("%d\n", ans);
        }
    }
}







Measured memory_bytes: 9364
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0,i##_max=(N);i<i##_max;++i)
#define repp(i,l,r) for(int i=(l),i##_max=(r);i<i##_max;++i)
#define per(i,N) for(int i=(N)-1;i>=0;--i)
#define perr(i,l,r) for(int i=r-1,i##_min(l);i>=i##_min;--i)
#define all(arr) (arr).begin(), (arr).end()
#define SP << " " <<
#define SPF << " "
#define SPEEDUP cin.tie(0);ios::sync_with_stdio(false);
#define MAX_I INT_MAX //1e9
#define MIN_I INT_MIN //-1e9
#define MAX_UI UINT_MAX //1e9
#define MAX_LL LLONG_MAX //1e18
#define MIN_LL LLONG_MIN //-1e18
#define MAX_ULL ULLONG_MAX //1e19
  typedef long long ll;
  typedef pair<int,int> PII;
  typedef pair<char,char> PCC;
  typedef pair<ll,ll> PLL;
  typedef pair<char,int> PCI;
  typedef pair<int,char> PIC;
  typedef pair<ll,int> PLI;
  typedef pair<int,ll> PIL; 
  typedef pair<ll,char> PLC; 
  typedef pair<char,ll> PCL; 

inline void YesNo(bool b){ cout << (b?"Yes" : "No") << endl;}
inline void YESNO(bool b){ cout << (b?"YES" : "NO") << endl;}
inline void Yay(bool b){ cout << (b?"Yay!" : ":(") << endl;}

const int N_MAX = 210, M_MAX = N_MAX*(N_MAX-1)/2, R_MAX = 8;
const int INF = 1e8;
int V,E,R;
int G[N_MAX][N_MAX];

void warshall_floyd(){
  rep(w,V)rep(v,V)rep(u,V) 
    G[v][u] = min(G[v][u],G[v][w] + G[w][u]);
}

int main(void){
  SPEEDUP
  cout << setprecision(15);
  cin >> V >> E >> R;
  vector<int> vr(R);
  rep(i,R){
    cin >> vr[i];
    --vr[i];
  }
  sort(all(vr));

  rep(v,V)rep(u,V) G[v][u] = (v==u) ? 0:INF;

  rep(i,E){
    int f,t,c;cin >> f >> t >> c;
    --f;--t;
    G[f][t] = c; 
    G[t][f] = c; 
  }
  warshall_floyd();

  ll minimum = INF;
  do{
    ll route = 0;
    rep(i,R-1){
      route += G[vr[i]][vr[i+1]];
    }
    minimum = min(route,minimum);
  }while(next_permutation(all(vr)));
  cout << minimum << endl;
  return 0;
}



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

int Exp(long long int exp_n,long long int exp_e, long long exp_mod);


int main(){
  int C[26];
  int S[26][365];
  int T[365];
  int res_do[26];
  
  int min_num=100;
  int min_c =0;
  for(int i=0;i<26;i++){
    cin >> C[i];
    if(min_num>C[i]){
      min_c=i+1;
      min_num=C[i+1];
    }
  }
  
  
  
  int max_num;
  int max_s;
  int check=26;
  
  for(int i=0;i<365;i++){
    if(check==26){
      for(int j=0;j<26;j++){
        res_do[j]=0;
      }
      check=0;
    }

    max_num = 0;
    max_s = 26;
    for(int j=0;j<26;j++){
      cin >> S[j][i];
      if(max_num<S[j][i] && res_do[j]==0){
        max_num=S[j][i];
        max_s=j;
      }
    }
    //cout << max_s <<":"<<max_num<<endl;
    T[i]=max_s;
    res_do[max_s]=1;
    check++;
  }
  
  
  
  
  for(int i=0;i<365;i++){
    cout << T[i]+1 <<endl;
  }
  
  return 0;
}


int Exp(long long int exp_n,long long int exp_e, long long int exp_mod){
  long long int exp_o = 1;
  long long int exp_x=exp_n;
  long long int exp_tmp;
  
  while(0<exp_e){
    exp_tmp = exp_e/2;
    if(exp_e - exp_tmp*2 == 1){
      exp_o = exp_o*exp_x;
      if(exp_o>exp_mod){
        exp_o=exp_o%exp_mod;
      }
    }
    
    exp_x = exp_x*exp_x;
    if(exp_x>exp_mod){
      exp_x=exp_x%exp_mod;
    }
    exp_e = exp_tmp;
  }
  return exp_o;
}


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

int main(){

  int n,t;
  cin >> n;
  vector<int> a(n,0);
  
  for(int i=0;i<n-1;i++){
  	cin >> t;
    a[t-1]++;
  }
  for(int i=0;i<n;i++){
  	cout << a[i] << endl;
  }
  return 0;
}

Measured memory_bytes: 4008
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using vi = vector<i64>;
using vvi = vector<vi>;

int main() {
    auto start = chrono::steady_clock::now();
    int n;
    cin >> n;
    vi as(n);
    for (int i = 0; i < n; i++) {
        cin >> as[i];
    }

    auto ok = [&](i64 k) {
        vi bs(as);
        __int128_t cnt = 0;
        for (int i = 0; i < bs.size(); i++) {
            bs[i] += k;
            cnt += (bs[i] - (n - 1) + n) / (n + 1);
        }
        return cnt <= k;
    };

    i64 l = -1, r = 2e18;
    while (l < r - 1) {
        i64 m = (l + r) / 2;
        if (ok(m)) {
            r = m;
        } else {
            l = m;
        }
    }
    
    i64 ans = r;
    while (r >= 0 && chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - start).count() < 1950) {
        if (ok(--r)) {
            ans = r;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int f[N];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	f[0] = 1;
	for (int i = 100; i <= 105; ++i)
		for (int j = i; j <= n; ++j)
			f[j] |= f[j - i];
	cout << f[n];
}


Measured memory_bytes: 640
N = int(input())
H = list(map(int, input().split()))
A = list(map(int, input().split()))
size = 2**N.bit_length()
seg = [0 for i in range(2*size + 1)]

def update(i, x):
  i += size
  seg[i] = x
  while 1 < i:
    i >>= 1
    seg[i] = max(seg[i<<1|0], seg[i<<1|1])

def query_(a, b, k, l, r):
  ret = 0

  a += size
  b += size
  while a < b:
    if b & 1:
      b -= 1
      ret = max(ret, seg[b])

    if a & 1:
      ret = max(ret, seg[a])
      a += 1

    a >>= 1
    b >>= 1

  return ret


def query(a, b):
  return query_(a, b, 1, 0, N)

for i in range(N):
  temp = query(0, H[i])
  update(H[i], temp+A[i])

print(query(0, N+1))

Measured memory_bytes: 147064
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(int i=int(a); i<int(b); ++i)
#define FORD(i,a,b) for(int i=int(a); i<int(b); --i)
#define REP(i,N) for(int i=0; i<int(N); ++i)
#define REPD(i,N) for(int i=0; i<int(N); --i)
#define PB push_back
#define ALL(obj) (obj).begin(), (obj).end()
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7
#define MAXR 100000 //配列の最大のrenge

int main() {
    ll N; cin >> N;
    string S; cin >> S;
    vector<int> num(N);
    num[0] = count(S.begin()+1, S.end(),'E');
    FOR(i,1,N) {
        int tmp = num[i-1];
        if (S[i] == 'E') tmp--;
        if (S[i-1] == 'W') tmp++;
        num[i] = tmp;
    }
    
    int ans = *min_element(ALL(num));
    cout << ans;
}

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

using namespace std;
int main(){
	int n,k;
	cin>>n>>k;
	int arr[n];
	for(int i=0;i<n;i++){
		cin>>arr[i];
	}
	sort(arr,arr+n);
	int sum=0;
	for(int i=0;i<k;i++){
		sum+=arr[i];
	}
	cout<<sum;
}

Measured memory_bytes: 3572
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
using ll = long long;
using pii = pair<int,int>;
using vi = vector<int>;
using vs = vector<string>;
using vpii = vector<pair<int,int>>;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};


int main(void) {
  int n;
  string s,t;
  cin >> n >> s >> t;
  string a;
  rep(i,n){
    a.push_back(s[i]);
    a.push_back(t[i]);
  }
  cout << a << endl;
  
  
         
         
  
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<sstream>
using namespace std;
string str;

int rewrite(int from, string s){

	//end位置を取得
	int end = -1;
	for (int i = from; i < (signed)s.size(); i++){
		if (i >= 1 && s[i - 1] == ']' &&s[i] == ']'){
			end = i;
			break;
		}
	}

	//右端まで来たときの処理
	if (end == -1){
		if (from == 0)
			return -1;
		else
			return rewrite(0, s);
	}

	//start位置を取得
	int start = -1;
	for (int i = end;; i--){
		if (s[i] == '[' &&s[i - 1] == '['){
			start = i;
			break;
		}
	}

	//vectorに入れる
	vector<int> v;
	int startnum = -1;
	for (int i = start; i < end; i++){
		if (s[i] == '[')
			startnum = i + 1;
		if (s[i] == ']'){
			string snum;
			for (int j = startnum; j < i; j++){
				snum = snum + s[j];
			}
			int num = atoi(snum.c_str());
			v.push_back((num + 1) / 2);
			startnum = -1;
		}
	}

	//ソート
	sort(v.begin(), v.end());

	//半分を取り出し，和を計算
	int sum = 0;
	for (int i = 0; i < ((signed)v.size() + 1) / 2; i++)
		sum += v[i];
	sum = sum * 2 - 1;
	string news = string(s.begin(), s.begin() + start);
	stringstream ss;
	ss << sum;
	news += ss.str();
	news += string(s.begin() + end, s.end());
	str = news;
	return news.size() - (s.size() - end);

}

int main()
{
	int n;
	char before = '0';
	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> str;
		int from = 0;
		while (1){
			from = rewrite(from, str);
			if (from == -1)
				break;
		}
		string ans = "";
		for (int i = 1; i < (signed)str.size() - 1; i++)
			ans += str[i];
		int ansnum = atoi(ans.c_str());
		cout << (ansnum + 1) / 2 << endl;
	}
	return 0;
}

Measured memory_bytes: 1316
#include<cstdio>
#include<algorithm> 
#include<cstring>
#define ll long long
using namespace std;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
int n;
ll ans=1;
char a[55],b[55];
int main()
{
	scanf("%d%s%s",&n,a+1,b+1);
	if(a[1]==b[1])ans*=3;
	else ans*=6;
	for(int i=2;i<=n;i++)
	{
		if(a[i]==a[i-1])continue;
		else if(a[i]==b[i]&&a[i-1]==b[i-1])ans=(ans*2)%mod;
		else if(a[i]==b[i])continue;
		else if(a[i-1]==b[i-1])ans=(ans*2)%mod;
		else ans=(ans*3)%mod;
	}
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 128
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
	// write your code her
        Scanner sc = new Scanner(System.in);
        // get a integer
        int a = sc.nextInt();
        // get two integers separated with half-width break
        int b = sc.nextInt();
        int c = sc.nextInt();
        if ((a == b + c) ||
                (b == a +c) ||
                (c == a + b)) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 9172
#include <algorithm>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <string>
#include <string.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
#define eps LDBL_EPSILON
#define moder 1000000007
#define int long long
#define ll long long
#define double long double
#define INF LLONG_MAX/3
#define P pair<int,int>
#define prique priority_queue<int,vector<int>,greater<int>>
using namespace std;
int n, a, b;
vector<int> vec[200010];
int d[200010];
void dfs(int s,int p) {
	d[s] = p;
	for (int i : vec[s]) {
		if (d[i] == INF)dfs(i, p + 1);
	}
}
signed main() {
	cin >> n;
	rep(i, n - 1) {
		cin >> a >> b;
		vec[a].push_back(b);
		vec[b].push_back(a);
	}
	fill(d + 1, d + n + 1, INF);
	dfs(1, 0);
	int cnt = 0, now;
	REP(i, n) {
		if (cnt < d[i]) {
			cnt = d[i];
			now = i;
		}
	}
	fill(d + 1, d + n + 1, INF);
	dfs(now, 0);
	int ma = 0;
	REP(i, n) {
		ma = max(ma, d[i]);
	}
	if (ma % 3 == 1)puts("Second");
	else puts("First");
	return 0;
}

Measured memory_bytes: 22144
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#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 all(a) (a).begin(),(a).end()
#define bit(k) (1LL<<(k))
#define SUM(v) accumulate(all(v), 0LL)

typedef pair<int, int> i_i;
typedef pair<ll, ll> l_l;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;
struct fast_ios{ fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; }fast_ios_;

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

#define TOSTRING(x) string(#x)
template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (T &x : vec) is >> x; return is; }
template <typename T> ostream &operator<<(ostream &os, const vector<T> &v) { os  << "["; for(auto _: v) os << _ << ", "; os << "]"; return os; };
template <typename T> ostream &operator<<(ostream &os, set<T> &st) { os << "("; for(auto _: st) { os << _ << ", "; } os << ")";return os;}
template <typename T, typename U> ostream &operator<<(ostream &os, const pair< T, U >& p){os << "{" <<p.first << ", " << p.second << "}";return os; }
template <typename T, typename U> ostream &operator<<(ostream &os, const map<T, U> &mp){ os << "["; for(auto _: mp){ os << _ << ", "; } os << "]" << endl; return os; }

#define DUMPOUT cerr
void dump_func(){ DUMPOUT << endl; }
template <class Head, class... Tail> void dump_func(Head &&head, Tail &&... tail) { DUMPOUT << head; if (sizeof...(Tail) > 0) { DUMPOUT << ", "; } dump_func(std::move(tail)...); }

#ifdef DEBUG
#define dbg(...) dump_func(__VA_ARGS__)
#define dump(...) DUMPOUT << string(#__VA_ARGS__) << ": "; dump_func(__VA_ARGS__)
#else
#define dbg(...)
#define dump(...)
#endif

const int INF = (ll)1e9;
const ll INFLL = (ll)1e18+1;
const ll MOD = 1000000007;
// const ll MOD = 998244353;
const long double PI = acos(-1.0);

/*
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const string dir = "DRUL";
*/


int main() {
    int X;
    cin >> X;
    ll L = lcm(X, 360);
    cout << L / X << endl;
}


Measured memory_bytes: 3636
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++)
#define All(v) (v).begin(), (v).end()
#define pb push_back
#define MP(a, b) make_pair((a), (b))
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int INF = 1 << 30;
const ll LINF = 1LL << 60;
const int MOD = 1e9 + 7;

int main() {
    int r;
    cin >> r;
    cout << r * r << endl;
    return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#pragma comment(linker, "/STACK:108777216")
#define _FORTIFY_SOURCE 0
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("fast-math")
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <utility>
#include <algorithm>
#include <ctime>
#include <cstdarg>
#include <sstream>
#include <functional>
using namespace std;

int const MAX_N = 512 * 1024;
long long const LL_INF = 5000000000000000000LL;

map<int, int> ms;

int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);

	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) {
		int x;
		scanf("%d", &x);
		ms[x]++;
	}

	for (int i = 0; i < m; i++) {
		int cnt, new_val;
		scanf("%d%d", &cnt, &new_val);
		map<int, int>::iterator iter = ms.begin();
		if (new_val <= iter->first) continue;
		int cnt_change = 0;
		vector<int> to_erase;
		while (iter != ms.end() && iter->first < new_val && cnt) {
			int cnt_cur = iter->second;
			if (cnt >= cnt_cur) {
				cnt_change += cnt_cur;
				to_erase.push_back(iter->first);
				cnt -= cnt_cur;
			}
			else {
				cnt_change += cnt;
				iter->second -= cnt;
				cnt = 0;
				break;
			}
			iter++;
		}
		for (int q = 0; q < (int)to_erase.size(); q++) ms.erase(ms.find(to_erase[q]));
		ms[new_val] += cnt_change;
	}
	long long sum = 0;
	for (map<int, int>::iterator iter = ms.begin(); iter != ms.end(); ++iter)
		sum += iter->first * ((long long)iter->second);
	cout << sum;
	return 0;
}


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

int main(){
  int N, K, X, Y;
  cin >> N >> K >> X >> Y;
  if (N <= K) {
  cout << N * X << endl;
  }
  else {
  cout << (K * X) + (N - K) * Y << endl;
  }
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
static const ll maxLL = (ll)1 << 62;
const int mod=1000000007;
int dy[]={-1,0,1,0};
int dx[]={0,1,0,-1};

//#define int ll


int n;

signed main(){
    cin>>n;
    
    
    
    if(n%2==1)cout<<(n/2)*(n/2+1);
    else cout<<(n/2)*(n/2)<<endl;
    return 0;
}

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

int main(){
    string str;
    stringstream ss;
    int max_num=-1,num,day,month=0;
    vector< vector<int> > data(2);

    for(auto &v:data){
        v.resize(10000);
        fill(v.begin(),v.end(),0);
    }

    while(getline(cin,str) && !str.empty()){
        ss<<str;
        ss>>num;
        ss.str("");
        ss.clear();
        data[month][num]++;
        max_num=max(max_num,num);
    }

    month++;

    while(getline(cin,str)){
        ss<<str;
        ss>>num;
        ss.clear();
        ss.str("");
        data[month][num]++;
        max_num=max(max_num,num);
    }

    for(int i=1;i<=max_num;i++){
        if(data[0][i]>0 && data[1][i]>0){
            cout<<i<<" "<<data[0][i]+data[1][i]<<endl;
        }
    }

    return 0;
}

Measured memory_bytes: 1312
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
    char n = 0;
    char pre = 0;
    for (int i=0; i<4; i++) {
        pre = n;
        cin >> n;
        if (pre == n) {
            cout << "Bad" << endl;
            return 0;
        }
    }
    cout << "Good" << endl;
    return 0;
}


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

using ll = long long;
using ld = long double;
constexpr ll inf = static_cast<ll>(1e17);
constexpr ll mod = static_cast<ll>(1e9 + 7);

int n, m;
std::vector<std::pair<int, int>> e[100005];

// --------- UnionFind木 ---------
class UnionFind {
public:
	UnionFind(int size) : data(size, -1) { }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) std::swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool findSet(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
private:
	std::vector<int> data;
};

std::map<int, bool> mp;
int main() {
	std::cin >> n >> m;

	UnionFind uf(n);
	for (int i = 0; i < m; ++i) {
		int x, y, z;
		std::cin >> x >> y >> z;

		uf.unionSet(x - 1, y - 1);
	}

	for (int i = 0; i < n; ++i)
		mp[uf.root(i)] = true;

	std::cout << mp.size() << std::endl;
	return 0;
}


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

#define ll long long
#define vi vector<int>
#define vl vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
// pll pp; -> (pp.first,pp.second)
// vector<vl> pp(n,vl(2)); sort(pp.begin(),pp.end(),[](vl a,vl b){return a[0]<b[0];});

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define RREP(i,n) for(ll (i)=(n)-1;(i)>=0;(i)--)
#define FOR(i,a,b) for(ll (i)=(a);(i)<(b);(i)++)
#define FORR(i,a,b) for(ll (i)=(b)-1;(i)>=(a);(i)--)
#define DEBUG(x) cout << #x << ": " << x << endl
#define CHMAX(a,b) a=max((a),(b))
#define CHMIN(a,b) a=min((a),(b))
/*}}}*/
int main() {
  ll n;
  cin >> n;
  string s;
  cin >> s;
  ll ans = 1;
  REP(i,n){
    if(i==0) continue;
    if(s[i-1]!=s[i]) ans++;
  }
  cout << ans<< endl;
  return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <stack>
#include <tuple>
using namespace std;
 
int main() {
    int n, balls[10]; cin >> n;
    while(n--){
        for(int i = 0; i < 10; i++) cin >> balls[i];
         
        enum {IDX, B, C};
        stack<tuple<int, int, int> > states;

        bool sortable = false;
        states.push(make_tuple(0,0,0));
        while(!states.empty()){
            tuple<int, int, int> now = states.top();
            states.pop();

            int idx = get<IDX>(now);
            if(idx < 10){
                if(get<B>(now) < balls[idx]){
                    if(idx == 9){
                        sortable = true; break;
                    }
                    states.push(make_tuple(idx+1,balls[idx],get<C>(now)));
                }
                if(get<C>(now) < balls[idx]){
                    if(idx == 9){
                        sortable = true; break;
                    }
                    states.push(make_tuple(idx+1,get<B>(now),balls[idx]));
                }
            }
        }

        if(sortable) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

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

int main() {
	vector<long> value;
	long N, K, num;

	scanf("%d %d", &N,&K);
	for (int i = 0; i < N; i++)
	{
		scanf("%d", &num);
		value.push_back(num);
	}
	sort(value.begin(), value.end());
	long delta = value[K-1] - value[0];
	for (int i = 1; i <= N-K; i++)
	{
		if (value[i + K-1] - value[i] < delta)delta = value[i + K-1] - value[i];
	}


	cout << delta << endl;

}


Measured memory_bytes: 1400
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	n, _ := strconv.Atoi(sc.Text())
	return n
}

func getFloat() float64 {
	sc.Scan()
	n, _ := strconv.ParseFloat(sc.Text(), 64)
	return n
}

func sum(n []int) int {
	a := 0
	for _, v := range n {
		a += v
	}
	return a
}

func partseFloat(s string) (n float64) {
	n, _ = strconv.ParseFloat(s, 64)
	return
}

func main() {
	sc.Split(bufio.ScanWords)
	n, t := getInt(), getInt()

	m := make([][]int, n)

	cmin := 1001
	for i := range m {
		m[i] = []int{getInt(), getInt()}
		if m[i][1] <= t && m[i][0] < cmin {
			cmin = m[i][0]
		}
	}
	if cmin == 1001 {
		fmt.Println("TLE")
	} else {
		fmt.Println(cmin)
	}
}


Measured memory_bytes: 640
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define N 2*10e5
#define precise cout<<fixed<<setprecision(10)
#pragma GCC optimize("O0")
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize ("-ffloat-store")
#define rep(i,a,b) for(int i=a;i<b;i++)
#define min3(a,b,c) min(a,min(b,c))
#define nl cout<<"\n";
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define mod 1000000007
typedef long long ll;
typedef vector<long long> vl;
typedef vector<pair<long,long>> vp;
void get(ll arr[],ll n){for(ll i=0;i<n;i++) cin>>arr[i];}
ll gcd(ll a,ll b);
ll binpow(ll a,ll b);
void solve()
{
    ll n;
    cin>>n;
    ll a[n];get(a,n);
    ll sum=0;
    rep(i,0,n) sum= (sum + a[i])%mod;
    sum = sum%mod;
    ll ans=0;
    rep(i,0,n)
    {
        ans = (ans + ((sum - a[i] + mod)%mod)*a[i])%mod;
    }
    if(ans%2==0)
    ans = ans/2;
    else
    {
        ans= ans+mod;
        ans= ans/2;
    }
    cout<<ans;   
}
int main()
{
 	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll t;
	t=1;
	//cin>>t;
	while(t--)
	{
	 	solve();
	}
	//cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
ll binpow(ll a, ll b) {
   ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}
ll gcd(ll a,ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

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

void lcs( string X, string Y, int m, int n ) 
{ 
int L[m+1][n+1]; 

for (int i=0; i<=m; i++) 
{ 
	for (int j=0; j<=n; j++) 
	{ 
	if (i == 0 || j == 0) 
		L[i][j] = 0; 
	else if (X[i-1] == Y[j-1]) 
		L[i][j] = L[i-1][j-1] + 1; 
	else
		L[i][j] = max(L[i-1][j], L[i][j-1]); 
	} 
} 

int index = L[m][n]; 


char lcs[index+1]; 
lcs[index] = '\0';  

int i = m, j = n; 
while (i > 0 && j > 0) 
{ 
	if (X[i-1] == Y[j-1]) 
	{ 
		lcs[index-1] = X[i-1];  
		i--; j--; index--;	  
	} 
 
	else if (L[i-1][j] > L[i][j-1]) 
		i--; 
	else
		j--; 
} 

cout << lcs; 
} 
int main() 
{ 

    string a,b;
    cin>>a>>b;
    
lcs(a,b,a.size(),b.size()); 
return 0; 
} 


Measured memory_bytes: 35456