akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define mod 998244353
#define MOD 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3fll
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
int dp[330][330];
int C[330][330];
int main()
{
	int n,k,m;
	cin>>n>>k>>m;
	C[0][0]=1;
	for(int i=1;i<330;i++)
	{
		C[i][0]=C[i][i]=1;
		for(int j=1;j<i;j++)
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%m;
	}
	for(int i=0;i<=k;i++)
		dp[0][i]=1;
	for(int i=1;i<=n;i++)
	{
		dp[i][1]=1;
		for(int j=2;j<=k;j++)
		{
			dp[i][j]=dp[i][j-1];
			for(int lsz=1;lsz<=i;lsz++)
			{
				dp[i][j]=(dp[i][j]+dp[lsz-1][j-1]*1ll*dp[i-lsz][j]%m*1ll*C[i][lsz-1]%m)%m;
			}
		}
	}
	cout<<dp[n][k]<<endl;
	return 0;
}

Measured memory_bytes: 1024
import sys

input = sys.stdin.readline


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return "\n".join("{}: {}".format(r, self.members(r)) for r in self.roots())


N, M, K = map(int, input().split())
U = UnionFind(N)
res = [0 for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    res[a - 1] -= 1
    res[b - 1] -= 1
    U.union(a - 1, b - 1)


for _ in range(K):
    c, d = map(int, input().split())
    if U.same(c - 1, d - 1):
        res[c - 1] -= 1
        res[d - 1] -= 1
for i in range(N):
    res[i] += U.size(i) - 1
print(" ".join(map(str, res)))



Measured memory_bytes: 90912
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

int main()
{
    int x = 0;
    int N;
    cin >> N;
    string S;
    cin >> S;

    int ans = 0;
    for (int i = 0; i < N;++i){
        if( S[i] == 'I' ){
            x += 1;
            ans = max(ans, x);
        }else if( S[i] == 'D'){
            x = x - 1;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
// #include <boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;

// #include <bits/extc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp> // tree
// #include <ext/pb_ds/hash_policy.hpp> // hash
// #include <ext/pb_ds/trie_policy.hpp> // trie
// #include <ext/pb_ds/priority_queue.hpp> // priority_queue
// using namespace __gnu_pbds;

#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second
#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()
#define Push push_back

using lli = long long;
using pll = pair<lli, lli>;
using Double = long double;
template<typename T>
using priority = priority_queue<T>;

const lli mod = 1E9 + 7;
const Double PI = 3.1415926535846;
const Double eps = 1e-8;

lli fastPow(lli base, lli exp, lli module = mod) {
	lli ans = 1;
	base %= module;
	while (exp) {
		if (exp & 1) ans = ans * base % module;
		base = base * base % module;
		exp >>= 1;
	}
	return ans;
}

bool millerRabin(lli n, lli a) {
	if (n < 2 or n % 2 == 0) return n == 2;
	lli u, t;
	for (u = n-1, t = 0; u & 1; u >>= 1, ++t);
	a = fastPow(a, u, n);
	if (a == 1 or a == n - 1) return true;
	for (int i = 0; i < t; ++i) {
		a = a * a % n;
		if (a == 1) return false;
		if (a == n - 1) return true;
	}
	return false;
}

void solve() {
	int n;
	cin >> n;
	cout << (n - 1) / 2 << "\n";
}

int main() {
	int t = 1;
	// cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

Measured memory_bytes: 764
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define mk make_pair
#define fi first
#define se second
#define vll vector<ll>
#define pii pair<ll,ll>
#define vvll vector< vector<ll> >
#define pb push_back
#define sz(v) (v).size()
#define inf 1e18
#define md 1000000007
#define all(v) (v).begin(),(v).end()
#define rep(i,a,b) for(ll i=a;i<b;++i)
#define tel(a){cout<<a<<"\n";}
#define tell(a,b){cout<<a<<" | "<<b<<"\n";}
#define telll(a,b,c){cout<<a<<" | "<<b<<" | "<<c<<"\n";}
#define teln(v,n){cout<<"v- ";rep(o,0,n)cout<<v[o]<<" ";cout<<"\n";}
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define tihs if(fopen("inp.txt","r"))freopen("inp.txt", "r", stdin),freopen("out.txt", "w", stdout);
using namespace std;
#define TRACE
 
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
 
ll ex(ll a,ll b){ll ans=1;while(b){if(b&1)ans=(ans*a)%md;a=(a*a)%md,b/=2;}return ans;} 
inline ll add(ll a,ll b){a=a%md+b%md;if(a>md)a%=md;return a;}
inline ll sub(ll a,ll b){a=a%md-b%md;if(a<0)a+=md;return a;}
inline ll mul(ll a,ll b){return (a%md*b%md)%md;}

#define M 200010

ll f[M],iv[M];
ll C(ll n,ll r){
	if(n<r)return 0;
	return mul(f[n],mul(iv[r],iv[n-r]));
}
#define X 5010
ll dp[X+10][X+10];
int main(){
	IOS;
	tihs;

	f[0]=1;
	rep(i,1,M)f[i]=mul(i,f[i-1]);
	iv[M-1]=ex(f[M-1],md-2);
	for(ll i=M-2;i>=0;--i)iv[i]=mul(i+1,iv[i+1]);
	
	ll n;cin>>n;
	ll a[n],b[n];
	rep(i,0,n)cin>>a[i]>>b[i];
	ll ans=0,c=2100;
	rep(i,0,n)dp[c-a[i]][c-b[i]]++;
	rep(i,0,X)rep(j,0,X)(dp[i+1][j+1]+=add(dp[i+1][j],dp[i][j+1]))%=md;
	rep(i,0,n)ans=add(ans,dp[c+a[i]][c+b[i]]);
	rep(i,0,n)ans=sub(ans,C(2*a[i]+2*b[i],2*b[i]));
	ans=mul(ans,ex(2,md-2));
	cout<<ans;


	return 0;
}

Measured memory_bytes: 203392
#define _USE_MATH_DEFINES
#include<iostream>
#include <iomanip>
#include<stdio.h>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include <queue>
#include <utility>
#include <map>
#include <set>
#include <deque>
#include <numeric>
using namespace std;

int sol(string A, string B) {
    if (A.size() > B.size())return 1;
    else if(A.size() < B.size())return -1;
    else if (A > B)return +1;
    else if (A < B)return -1;
    else return 0;
}

int main() {
    string A,B;
    cin >> A >> B;
    int ans = sol(A, B);
    if (ans==1)cout << "GREATER" << endl;
    else if (ans==-1)cout << "LESS" << endl;
    else cout << "EQUAL" << endl;

    return 0;
}

Measured memory_bytes: 256
/* 
 * Project: AtCoder Beginners Contest 095 A - Something on It
 * Author: toms74209200 <https://github.com/toms74209200>
 *
 * Created on 2020/06/02
 * Copyright (c) 2020 toms74209200
 * 
 * This software is released under the MIT License.
 * http://opensource.org/licenses/mit-license.php
 */
#include <cstdio>
#include <cstring>
using namespace std;

char s[3];

void solve() {

    if (!strcmp(s, "ooo")) {
        printf("1000\n");
    } else if (!strcmp(s, "oox")) {
        printf("900\n");
    } else if (!strcmp(s, "oxo")) {
        printf("900\n");
    } else if (!strcmp(s, "oxx")) {
        printf("800\n");
    } else if (!strcmp(s, "xoo")) {
        printf("900\n");
    } else if (!strcmp(s, "xox")) {
        printf("800\n");
    } else if (!strcmp(s, "xxo")) {
        printf("800\n");
    } else if (!strcmp(s, "xxx")) {
        printf("700\n");
    }

}

int main() {

    scanf("%s", s);

    solve();

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,k,a[55];
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;++i)
		cin>>a[i];
	sort(a+1,a+n+1);
	long long ans=0;
	for(int i=n;i>=n-k+1;--i)
		ans+=a[i];
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(c) (c).begin(),(c).end()
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define MINF(a) memset(a,0x3f,sizeof(a))
#define POW(n) (1LL<<(n))
#define IN(i,a,b) (a <= i && i <= b)
using namespace std;
template <typename T> inline bool CHMIN(T& a,T b) { if(a>b) { a=b; return 1; } return 0; }
template <typename T> inline bool CHMAX(T& a,T b) { if(a<b) { a=b; return 1; } return 0; }
template <typename T> inline void SORT(T& a) { sort(ALL(a)); }
template <typename T> inline void REV(T& a) { reverse(ALL(a)); }
template <typename T> inline void UNI(T& a) { sort(ALL(a)); a.erase(unique(ALL(a)),a.end()); }
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-10;
/* ---------------------------------------------------------------------------------------------------- */

int n,m,a;
int x[1010][110];

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

  while (cin >> n >> m >> a, n) {
    ZERO(x);
    REP(i,m) {
      int h,p,q;
      cin >> h >> p >> q;
      x[h][p] = 1;
    }
    for (int i = 1000; i >= 1; i--) {
      if (x[i][a]) {
        a++;
      } else if (a-1 >= 1 && x[i][a-1]) {
        a--;
      }
    }
    cout << a << endl;
  }

  return 0;
}


Measured memory_bytes: 3996
N, K = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]

MOD = 10**9+7

def dot(A, B):
    N = len(A)
    K = len(A[0])
    assert len(B) == K
    M = len(B[0])
    C = [[0] * M for _ in range(N)]
    for i in range(N):
        for j in range(M):
            for k in range(K):
                C[i][j] += (A[i][k] * B[k][j]) % MOD
                C[i][j] %= MOD
    return C



def mp(A, n):
    assert len(A) == len(A[0])
    B = [[0] * len(A) for _ in range(len(A))]
    for i in range(len(A)):
        B[i][i] = 1

    while n:
        n, i = divmod(n, 2)
        if i:
            B = dot(A, B)
        A = dot(A, A)

    return B


ans = sum([sum(r) % MOD for r in mp(A, K)]) % MOD
print(ans)


Measured memory_bytes: 42032
#include<stdio.h>

int main(void) {
    int balance = 100000;

    int week;
    scanf("%d", &week);

    while(week > 0) {
        balance *= 1.05;
        if(balance % 1000 > 0) balance = (balance / 1000) * 1000 + 1000;
        week--;
    }   

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

    return 0;                                                                                                                                                            
}

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

int main(){
    int n;
    cin >> n;

    vector<int> h(n);
    for(int i=0; i<n; i++){
        cin >> h[i];
    }

    int counter = 0;
    priority_queue<int> pq;
    for(int i=0; i<n-1; i++){
        if(h[i] < h[i+1]){
            pq.push(counter);
            counter = 0;
        }else{
            counter += 1;
        }
    }
    pq.push(counter);

    cout << pq.top() << endl;
    return 0;
}

Measured memory_bytes: 1276
#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <tuple>

int testcase_ends() {
  size_t N;
  int M;
  scanf("%zu %d", &N, &M);
  if (N == 0 && M == 0) return 1;

  std::vector<std::pair<int, int>> e;
  for (size_t i = 0; i < N; ++i) {
    int D, P;
    scanf("%d %d", &D, &P);
    e.emplace_back(P, D);
  }

  std::sort(e.rbegin(), e.rend());
  int res = 0;
  for (auto const& ei: e) {
    int p, d;
    std::tie(p, d) = ei;
    if (M >= d) {
      M -= d;
      continue;
    }
    d -= M;
    M = 0;
    res += p * d;
  }
  printf("%d\n", res);
  return 0;
}

int main() {
  while (!testcase_ends()) {}
}



Measured memory_bytes: 2704
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <map>
#include <utility>
#include <numeric>
#include <typeinfo>

using namespace std;

int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  for(int i=0;i<N;i++)  cin >> A.at(i);

  sort(A.begin(),A.end());
  int ans=0;
  int count=1;
  for(int i=0;i<N;i++){
    if(i<N-1 && A.at(i)==A.at(i+1)){
      count++;
      continue;
    }
    else{
      ans+=count%2;
      count=1;
    }
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
typedef pair<int,pll> P;
int main(){
  while(1){
    map<int,string> mp;
    int n,i,j;
    cin >> n;
    if(n==0){
      return 0;
    }
    vector<P> p;
    for(i=0;i<n;i++){
      string s;
      cin >> s;
      mp[i]=s;
      int win=0,lose=0;
      for(j=0;j<n-1;j++){
        int a;
        cin >> a;
        if(a==0){
          win++;
        }
        else if(a==1){
          lose++;
        }
      }
      p.push_back(make_pair(-win,pll(lose,i)));
    }
    sort(p.begin(),p.end());
    for(i=0;i<n;i++){
      cout << mp[p[i].second.second] << endl;
    }
  }
}


Measured memory_bytes: 3104
#include<iostream>
#include <algorithm>
using namespace std;
int main()
{
    int n[3], h[2], i, l, g = 0;
    for (i = 0; i < 3; i++)
    {
        cin >> n[i];
    }
    for (i = 0; i<2; i++)
    {
        cin >> h[i];
    }
    for (i = 0; i <= 3; i++)
    {
        sort(n, n + 3);
    }
    l = n[0];
    if (h[0] < h[1])
        cout << l + h[0]-50 << endl;
    else
        cout << l + h[1]-50 << endl;
    return 0;
}

Measured memory_bytes: 3044
#include <stdio.h>

int main(void){
	unsigned S, h, m, s;

	scanf("%u", &S);
	h = S/60/60;
	m = S/60 - h*60;
	s = S % 60;
	printf("%u:%u:%u\n", h, m, s);

	return 0;
}



Measured memory_bytes: 2100
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
using namespace std;
class Node{
  private:
    int n;
    int count =0;
    Node *parent;
    vector<Node> pNext;
    int pn=0;
    int pare=0;
  public:
    Node(int a){
      n=a;
    };
    void setParent(Node *par){
      parent=par;
      pare=1;
    }
    void setP(Node par){
      pNext.push_back(par);
      pn++;
    }
    /*Node* getNext1(){
      if(pn>0){
        return pNext[0];
      }else{
        return NULL;
      }
    }*/
    /*Node getNext2(){
      if(pn>1){
        return pNext[1];
      }else{
        return NULL;
      }
    }*/
    void sumCount(int n){
      count +=n;
    }
    void sumpCount(){
      if(pare==1)count += (*parent).getCount();
    }
    int getCount(){return count;}
};
int main(){
  int n,q;
  cin >>n;
  cin >>q;
  vector< Node > v;
  for(int i=0; i<n;i++){
    Node a(i);
    v.push_back(a);
  }
  int x,y;
  for(int i=1; i<n; i++){
    cin >>x >>y;
    v[x-1].setP(v[y-1]);
    v[y-1].setParent(&v[x-1]);
  }
  for(int i=0; i<q; i++){
    cin >>x >>y;
    v[x-1].sumCount(y);
  }
  for(int i=0; i<n; i++){
    v[i].sumpCount();
    cout <<v[i].getCount() <<" ";
  }
}


Measured memory_bytes: 35048
#include <stdio.h>
int main(int argc, char *argv[])
{
	char d[5];
	scanf("%s",d);
	for(int i=0;i<3;i++)
	{
		if(d[i]=='1')d[i]='9';
		else if(d[i]=='9')d[i]='1';
	}
	printf("%s",d);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPS(i, x) for (int i = 1; i <= (int)(x); i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define FORS(i, m, n) for (int i = m; i <= n; i++)
#define INF 2e9
#define MOD (1000000007)
#define EPS 1e-9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long long int lli;
int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  vector<int> H(N);
  vector<bool> flg(N, true);
  REP(i, N)
  {
    cin >> H[i];
  }
  REP(i, N)
  {
    FOR(j, i + 1, N)
    {
      if (H[i] > H[j] && flg[j])
      {
        flg[j] = false;
      }
    }
  }
  cout << (int)count(flg.begin(), flg.end(), true) << "\n";
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>

int main()
{
	int a,b;
	char s[11];
	char t[11];
	char u[11];

	scanf("%s %s\n",&s,&t);
	scanf("%d %d\n",&a,&b);
	scanf("%s",&u);
	
	if(strcmp(s,t)==0)
	{
		printf("error!");
	}
	else if (strcmp(s,u)==0)
	{
		printf("%d %d",a-1,b);
	}
	else if(strcmp(t,u)==0)
	printf("%d %d",a,b-1);
	}

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

using namespace std;
#define INF 1e18
typedef long long ll;
typedef pair<int, int> P;

int main(){
  int x,n;
  cin>>x>>n;
  if(n==0){
    cout<<x<<endl;
    return 0;
  }
  vector<int>p(n+1);
  p.at(0)=-1e9;
  for(int i=1;i<=n;i++){
    cin>>p.at(i);
  }
  int count=0;
  sort(p.begin(), p.end());
  for(int i=0;i<n+1;i++){
      if(p.at(i)<=x){
        count++;
      }
      if(p.at(i)>x){
        continue;
      }
    }
  if(p.at(count-1)!=x){
    cout<<x<<endl;
    return 0;
  }
  p.push_back(1e9);
  
  for(int i=1;i<200;i++){
    if(x-i!=p.at(count-1-i)){
      cout<<x-i<<endl;
      return 0;
    }
    if(x+i!=p.at(count-1+i)){
      cout<<x+i<<endl;
      return 0;
    }
  }
}
    
      
    
  
  
  
  



Measured memory_bytes: 3632
h, w = map(int, input().split())
a = [['#'] * (w + 2)] * 2
a[1: 1] = [list('#' + input() + '#') for _ in range(h)]
p = [(i, j) for i in range(1, h + 1) for j in range(1, w + 1) if a[i][j] == '#']
d = (-1, 0), (1, 0), (0, -1), (0, 1)
r = -1
while p:
    r += 1
    s = []
    for i, j in p:
        for di, dj in d:
            di += i
            dj += j
            if a[di][dj] == '.':
                a[di][dj] = '#'
                s.append((di, dj))
    p = s
print(r)


Measured memory_bytes: 132688
program gcd_on_blackboard
  implicit none
  integer :: n, a(100000), i, g, m
  integer :: l(0:100000), r(1:100001)
  a = 0
  l = 0
  r = 0
  read(*,*) n
  read(*,*) a(1:n)
  m = 1
  do i = 1, n
    l(i) = gcd(l(i-1),a(i-1))
  end do
  do i = n, 1, -1
    r(i) = gcd(r(i+1),a(i))
  end do
  do i = 1, n
    g = gcd(l(i),r(i+1))
    if (m.lt.g) m = g
  end do
  write(*,'(i0)') m
  stop
contains
  recursive function gcd(n,m) result(g)
    implicit none
    integer, intent(in) :: n, m
    integer :: g
    if (n.eq.0) then
      g = m
    else if (m.eq.0) then
      g = n
    else if (n.lt.m) then
      g = gcd(m,n)
    else if (mod(n,m).eq.0) then
      g = m
    else
      g = gcd(m,mod(n,m))
    end if
  end function gcd
end program gcd_on_blackboard

Measured memory_bytes: 1920
/* 	* In the name of GOD 
	* Thanks God */
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
#define F first
#define S second
const int N = 101234;
vector <int> adj[N];
bool mark[N];

void dfs(int x) {
	mark[x] = true;
	for (auto y : adj[x]) {
		if (mark[y])
			continue;
		dfs(y);
	}
}

void solve() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		u--;
		v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	int ans = -1;
	for (int i = 0; i < n; i++) {
		if (mark[i])
			continue;
		ans++;
		dfs(i);
	}
	cout << ans;
}

int32_t main() {
	int t = 1;
//	cin >> t;
	while (t--) {
		solve();
	}
}


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

int main(void){
	int n;
	cin >> n;
	int ans = 0;
	if(n / 10000 >= 1){
		ans += n / 10000 * 10000;
		n = n % 10000;
	}
	if(n / 5000 >= 1){
		ans += n / 5000 * 5000;
		n = n % 5000;
	}
	if(n / 1000 >= 1){
		ans += n / 1000 * 1000;
		n = n % 1000;
	}
	if(n / 500 >= 1){
		ans += n / 500 * 500;
		n = n % 500;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3092
n = int(input())
x, y = 1, 1
for _ in range(n):
    t, a = map(int,input().split())
    if x*a == y*t:
        continue
    elif x*a > y*t:
        y = (x//t+(x%t!=0))*a
        x = y//a*t
    else:
        x = (y//a+(y%a!=0))*t
        y = x//t*a
print(x+y)


Measured memory_bytes: 3060
# Otoshidama
n, y = map(int, input().split())
for i in range(n+1):
    for j in range(n+1-i):
        if 10000 * i + 5000 * j + 1000 * (n-i-j) == y:
            exit(print(i, j, n-i-j))
print('-1 -1 -1')


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
char s[maxn], t[maxn];
int pres[maxn], pret[maxn];
int main()
{
	scanf("%s%s", s + 1, t + 1);
	int lens = strlen(s + 1), lent = strlen(t + 1);
	for(int i = 1; i <= lens; ++i)
		if(s[i] == 'B')
			pres[i] = pres[i - 1] + 1;
		else
			pres[i] = pres[i - 1] + 2;
	for(int i = 1; i <= lent; ++i)
		if(t[i] == 'B')
			pret[i] = pret[i - 1] + 1;
		else
			pret[i] = pret[i - 1] + 2;
	int q, a, b, c, d;
	scanf("%d", &q);
	while(q--)
	{
		scanf("%d%d%d%d", &a, &b, &c, &d);
		if(abs(pres[b] - pres[a - 1] - (pret[d] - pret[c - 1])) % 3 == 0)
			puts("YES");
		else
			puts("NO");
	}
	return 0;
}
		

Measured memory_bytes: 1536
#include <iostream>
using namespace std;
int main(){
    int X,Y,i;
    cin >> X >> Y;
    if((Y%2) == 1)
        cout << "No";
    else{
        Y /= 2;
        if ((Y>=X) && (Y<=(2*X)))
            cout << "Yes";
        else{
            cout << "No";
        }
    }
    return 0;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
#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 namespace std;
using P = pair<int, int>; 
using ll = long long;
using M = map<int, int>;

int main()
{
  int n, m;
  cin >> n >> m;
  vector<tuple<ll, ll, ll>> tp;
  ll x, y, z;
  rep(i, n) {
    cin >> x >> y;
    z = x * y;
    //cout << z << endl;
    tp.push_back(make_tuple(x, y, z));
  }
  ll ans = 0;
  sort(tp.begin(), tp.end());
  rep(i, n) {
    //cout << "OK" << endl;
    //cout << get<0>(tp[i]) << endl;
    if(get<1>(tp[i]) >= m) {
      //cout << 1 << endl;
      ans += m * get<0>(tp[i]);
      break;
    }
    else{
      //cout << 2 << endl;
      ans += get<2>(tp[i]);
      m -= get<1>(tp[i]);
    }
  }
  cout << ans << endl;
  
    
  return 0;
}

Measured memory_bytes: 6424
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for(int i =0; i < n; i++){
      cin >> a.at(i);
    }
    sort(a.begin(), a.end());
  
  	int sum = 0;
    for(int i = 0; i < k; i++){
      sum += a.at(i);
    }
 
  	cout << sum << endl;
    return 0;
}

Measured memory_bytes: 3608
#include <stdio.h>

char prime[1000000];

int main(void)
{
	int a, d, n;
	int i, j;

	prime[0] = prime[1] = 1;
	for (i = 4; i < 1000000; i += 2) prime[i] = 1;
	for (i = 3; i <= 1000; i += 2){
		if (prime[i]) continue;
		for (j = i * i; j < 1000000; j += i) prime[j] = 1;
	}

	while (scanf("%d %d %d", &a, &d, &n), n){
		for (i = 0; n; i++) n -= !prime[a + d * i];
		printf("%d\n", a + d * i - d);
	}

	return 0;
}

Measured memory_bytes: 1572
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;

int Prime[1000010];   //Prime[i] = 1のときiは素数。0のときiは素数でない

void Eratosthenes(int n) {  //n未満の素数を求める

    rep(i, n) {
        Prime[i] = 1;
    }

    Prime[0] = 0;  Prime[1] = 0;
    for(int i = 2; i*i < n; i++) {
        if(Prime[i]) {
            for(int j = 2; i*j < n; j++) {
                Prime[i*j] = 0;
            }
        }
    }
}

int main() {
    ll n, p;
    cin >> n >> p;

    if(n == 1) {
        cout << p << endl;
        return 0;
    }

    ll q = p;
    
    Eratosthenes(1000000);

    ll ans = 1LL;
    for(ll i = 2; i*i <= q; i++) {
        if(Prime[i]) {
            int cnt = 0;
            while(p%i == 0) {
                p /= i;
                cnt++;
            }

            while(cnt >= n) {
                ans *= i;
                cnt -= n;
            }
        }
    }

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

Measured memory_bytes: 4096
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>

using namespace std;

typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int,int> PII;

const int INF = INT_MAX / 4;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); i++ )
#define UREP( i, m, n ) for ( ui i = (ui)( m ); i < (ui)( n ); i++ )
#define EACH( v, c ) for ( __typeof( c.front() ) &v : c )

#define ITER( c ) __typeof( (c).begin() )
#define IREP( c, it ) for ( ITER(c) it = c.begin(); it != c.end(); ++it )
#define ALL( c ) (c).begin(), (c).end()
#define RALL( c ) (c).rbegin(), (c).rend()

#define PB( n ) push_back( n )
#define MP( a, b ) make_pair( ( a ), ( b ) )
#define EXIST( c, e ) ( (c).find( e ) != (c).end() )

#define fst first
#define snd second

#define DUMP( x ) cerr << #x << " = " << ( x ) << endl
#define DEBUG( x ) cerr << __FILE__ << ":" << __LINE__ << ": " << #x << " = " << ( x ) << endl

struct Team
{
	int no, solved, pena;
	map<int,int> submitted;

	Team( int n ) : no( n ), solved( 0 ), pena( 0 )
	{
		return;
	}

	void attempt( int n )
	{
		submitted[ n ]++;
		return;
	}

	void accept( int n, int time )
	{
		solved++;
		pena += submitted[n] * 1200 + time;
		return;
	}

	void print()
	{
		cout << no << ' ' << solved << ' ' << pena << endl;
	}

	bool operator < ( const Team &b ) const
	{
		if ( solved == b.solved )
		{
			if ( pena == b.pena )
			{
				return no < b.no;
			}
			else
			{
				return pena < b.pena;
			}
		}
		else
		{
			return b.solved < solved;
		}
	}
};

int main()
{
	while ( true )
	{
		int t, p, r;
		cin >> t >> p >> r;

		if ( t == 0 && p == 0 && r == 0 )
		{
			break;
		}

		vector<Team> ts;

		REP( i, 0, t )
		{
			ts.PB( Team( i + 1 ) );
		}

		int team, prob, time;
		string code;
		REP( i, 0, r )
		{
			cin >> team >> prob >> time >> code;

			if ( code == "CORRECT" )
			{
				ts[ team - 1 ].accept( prob, time );
			}
			else
			{
				ts[ team - 1].attempt( prob );
			}
		}

		sort( ALL( ts ) );

		for ( auto &t : ts )
		{
			t.print();
		}
	}

	return 0;
}

Measured memory_bytes: 1252
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const int INF = 1 << 30;
const ll INFll = 1ll << 60;

int main() {
  int n;
  cin >> n;
  int least = INF;
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    int c;
    for (c = 0; a % 2 == 0; a /= 2) c++;
    least = min(least, c);
  }

  cout << (least == INF ? 0 : least) << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>

int w[111], v[111];
long long dp[110][100010];

int main(){
    int N, W;
    std::cin >> N >> W;
    for(int i = 1; i <= N; i++){
        std::cin >> w[i] >> v[i];
    }
    for(int i = 1; i <= N; i++){
        for(int j = 0; j <= W; j++){
            if(j-w[i] >= 0){
                dp[i][j] = std::max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
            }else{
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    std::cout << dp[N][W] << std::endl;
}


Measured memory_bytes: 79360
/*input
6
5 2 4 6 1 3
*/
fn read_line() -> String {
    let mut return_ = format!("");
    std::io::stdin().read_line(&mut return_).ok();
    return_.pop();
    return_
}

fn main() {
    read_line();
    let mut v: Vec<u16> = read_line()
        .split_whitespace()
        .map(|x| x.parse().unwrap())
        .collect();
    let mut step: u16 = 0;
    let mut min: u16;
    let mut index: usize = 0;
    let mut change: bool;
    //let mut temp: u16;
    for i in 0..v.len() - 1 {
        change = false;
        min = std::u16::MAX;
        for j in i..v.len() {
            if v[j] < min {
                change = true;
                min = v[j];
                index = j;
            }
        }
        if change && index != i {
            step = step + 1;
            //temp = v[i];
            //v[i] = v[index];
            //v[index] = temp;
            v[i] = v[i] + v[index];
            v[index] = v[i] - v[index];
            v[i] = v[i] - v[index];
        }
    }
    let mut first = true;
    for i in v {
        if first {
            first = false;
        } else {
            print!(" ");
        }
        print!("{}", i);
    }
    print!("\n");
    println!("{}", step);
}



Measured memory_bytes: 5028
AC = 0
WA = 0
TLE = 0
RE = 0

n = int(input())

for i in range(n):
  d = input()
  if d == 'AC':
    AC += 1
  elif d == 'WA':
    WA += 1
  elif d == 'TLE':
    TLE += 1
  else:
    RE += 1

print('AC x ' + str(AC))
print('WA x ' + str(WA))
print('TLE x ' + str(TLE))
print('RE x ' + str(RE))

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

int main() {
  int64_t n;
  cin >> n;
  vector<int64_t> vec(n);
  for (int i = 0; i < n; i++) {
    cin >> vec.at(i);
  }
  sort(vec.begin(), vec.end());
  int64_t k;
  k = vec.at(n/2) - vec.at(n/2-1);
  cout << k << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n,m,sum=0;
  cin>>n>>m;
  int a[m];
  for(int i=0;i<m;i++)
  {  cin>>a[i];sum+=a[i];}
  if(sum<=n)
    cout<<n-sum<<endl;
  else
    cout<<-1<<endl;
    return 0;
}

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


int main()
{
	ll n,r=0,b=0,g=0,sum=0;
	string s;
	cin>>n>>s;
	for(ll i=0;i<n;i++)
	{
		if(s[i]=='R')r++;
		else if(s[i]=='B')b++;
		else g++;
	}
	sum=r*b*g;
	for(ll i=1;i<=(n-1)/2;i++)
	{
		for(ll j=0;j<n-i-i;j++)
		{
			if(s[j]!=s[j+i]&&s[j+i]!=s[j+i+i]&&s[j+i+i]!=s[j])sum--;
		}
	}
	cout<<sum<<endl;
	return 0;
}

Measured memory_bytes: 3636
import collections


def main():
    n, q = map(int, input().split())

    dq = collections.deque()
    for i in range(n):
        s = input().split()
        name = s[0]
        time = int(s[1])
        dq.append((name, time))

    cur_time = 0
    while len(dq) > 0:
        top = dq.popleft()
        # not finish
        if top[1] > q:
            dq.append((top[0], top[1] - q))
            cur_time += q
        else:
            print(top[0] + " " + str(cur_time+top[1]))
            cur_time += top[1]


main()


Measured memory_bytes: 12532
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
#define ll long long
#define read(n) scanf("%d",&n)
#define f(i,a,b) for(int i=a;i<=b;++i)
int main()
{
	char c;
	cin>>c;
	if(c<='Z') cout<<"A";
	else cout<<"a";
	return 0;
} 

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

int main() {
	ll x,y,a,b,c;
	cin >> x >> y >> a >> b >> c;
	vector<ll> p(a), q(b), r(c);
	rep(i,a) cin >> p[i];
	rep(i,b) cin >> q[i];
	rep(i,c) cin >> r[i];
	sort(p.begin(), p.end(), greater<ll>());
	sort(q.begin(), q.end(), greater<ll>());
	sort(r.begin(), r.end(), greater<ll>());

	ll ans = 0;
	rep(i,x) ans += p[i];
	rep(i,y) ans += q[i];

	ll idx_x = x-1;
	ll idx_y = y-1;
	ll idx_z = 0;
	ll prf_x, prf_y;
	while(1) {
		if (idx_x>=0) prf_x = r[idx_z] - p[idx_x];
		else prf_x = 0;
		if (idx_y>=0) prf_y = r[idx_z] - q[idx_y];
		else prf_y = 0;
		if (max(prf_x, prf_y) > 0) {
			ans += max(prf_x, prf_y);
			if (prf_x >= prf_y) idx_x--;
			else idx_y--;
			idx_z++;
		}
		else {
			break;
		}
		if (idx_z>c-1) break;
	}
	cout << ans << endl;
	return 0;
}


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

int main () {
    int n;
    while (scanf("%d", &n) == 1) {
        map<char, int> m;
        while (n--) {
            char s[5];
            scanf("%s", s);
            m[s[0]]++;
        }
        printf("AC x %d\n", m['A']);
        printf("WA x %d\n", m['W']);
        printf("TLE x %d\n", m['T']);
        printf("RE x %d\n", m['R']);
    }
}



Measured memory_bytes: 3784
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

n, x, y = MAP()
yx = y - x + 1
lnf = x
lne = n - y + 1
#print(lnf, lne)
ans = [0 for _ in range(n + 1)]
for i in range(1, n):
    for j in range(i + 1, n + 1):
        tmp = min(j - i, abs(x - i) + abs(y - j) + 1)
        ans[tmp] += 1

for k in range(1, n):
    print(ans[k])

Measured memory_bytes: 5476
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define DEBUG(x)  cout << #x << " = " << (x) << endl;
#define SORT(x) sort(ALL(x));
#define RSORT(x) sort(RALL(x));
#define SUM(x) accumulate(ALL(x),0);
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
const int inf = 1<<30;
const ll mod = 1000000007;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//cout << fixed << setprecision(10);

ll gcd(ll a, ll b) { return b ? gcd(b,a%b) : a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

int main () {
  int N; cin >> N;
  vi W(N); rep(i,N) cin >> W[i];

  int SUM = SUM(W);
  int S1 = 0, S2;
  int ans = 100;
  rep(i,N) {
    S1 += W[i];
    S2 = SUM - S1;
    ans = min(ans,abs(S1-S2));
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
const double EPS = 1e-11;
const double PI = 2 * acos(0.0);
using ll = long long;
using ull =  unsigned long long;

#define input freopen("input.txt", "r", stdin)
#define output freopen("output.txt", "w", stdout)
#define fast_io ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
#define pf printf
#define si(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define sii(x,y) scanf("%d %d",&x,&y)
#define sll(x,y) scanf("%lld %lld",&x,&y)

#define pii pair<int,int>
#define nl '\n'
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define ALL(v) v.begin(),v.end()
#define uniq(a) a.erase(unique(a.begin(), a.end()), a.end())
#define out(x) cout <<"#x = "<<x<<endl
#define outt(x,y) cout <<"# "<<x<<" "<<y<<endl
#define mem(array,value) memset(array,value,sizeof(array))
#define MX 10005

string a,b;
int dp[3001][3001];
int lcs(int n,int m)
{
	if(n==0 or m==0 )return 0;

	if(dp[n][m]!=-1)return dp[n][m];
	if(a[n-1]==b[m-1]){
		return dp[n][m]=1+lcs(n-1,m-1);
	}
	else{
		return dp[n][m]=max(lcs(n-1,m),lcs(n,m-1));
	}
	return dp[n][m];
}
string ans="";
void print(int n,int m)
{
	if(n==0 || m==0)return;
	if(a[n-1]==b[m-1]){
		ans+=a[n-1];
		print(n-1,m-1);
	}
	else if(dp[n-1][m]>dp[n][m-1])print(n-1,m);
	else print(n,m-1);
}
int main()
{
	mem(dp,-1);
	cin >>a>>b;
	lcs(a.size(),b.size());
	print(a.size(),b.size());
	reverse(ALL(ans));
	cout <<ans<<endl;
	return 0;
}

Measured memory_bytes: 35968
#include<iostream>
using namespace std;
typedef long long ll;

const ll mod = 1000000007;

ll pow(ll a, ll b){
	return (!b ? 1 : (b & 1 ? a * pow(a, b - 1) % mod : pow((a * a) % mod, b / 2) % mod));
}

int main(){
	ll n; cin >> n;
	ll used[n] = {0};
	for(ll i = 1; i <= n; ++i){
		ll a; cin >> a;
		if(a >= n){
			cout << 0 << endl;
			return 0;
		}
		++used[a];
	}
	if((n & 1) && used[0] != 1){
		cout << 0 << endl;
		return 0;
	}
	
	for(ll i = 1; i < n; ++i){
		if(((n & 1) && (i & 1)) || (!(n & 1) && !(i & 1))){
			if(used[i]){
				cout << 0 << endl;
				return 0;
			}
		}else{
			if((((n & 1) && !(i & 1)) || (!(n & 1) && (i & 1))) && used[i] != 2){
				cout << 0 << endl;
				return 0;
			}
		}
	}
	cout << pow(2, n / 2) << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


int main(){

	char buf[1000];
	scanf("%s",buf);

	int N = 0;
	for(int i = 0; buf[i] != '\0'; i++){
		if(buf[i] >= 'a' && buf[i] <= 'z'){
			N++;
		}
	}

	char word[2];
	int table[26],tmp;
	for(int i = 0; i < 26; i++)table[i] = -1;

	int total_win = 0;

	for(int i = 0; i < N; i++){
		scanf("%s %d",word,&tmp);
		table[word[0]-'a'] = tmp;
		total_win += tmp;
	}
	if(total_win != N-1){
		printf("No\n");
		return 0;
	}

	int lose_num = 0,max_depth,depth;
	int match_num[26];
	for(int i = 0; i < 26; i++)match_num[i] = 0;

	queue<int> LEFT,RIGHT;

	int calc_left,calc_right;
	char person_left,person_right,winner;

	while(lose_num < N-1){

		max_depth = -1;
		depth = 0;

		for(int i = 0; buf[i] != '\0'; i++){
			if(buf[i] == '['){
				depth++;
				max_depth = max(max_depth,depth);
			}else if(buf[i] == ']'){
				depth--;
			}
		}

		depth = 0;
		for(int i = 0; buf[i] != '\0'; i++){
			if(buf[i] == '['){
				depth++;
				if(depth == max_depth){
					LEFT.push(i);
				}
			}else if(buf[i] == ']'){
				if(depth == max_depth){
					RIGHT.push(i);
				}
				depth--;
			}else if(buf[i] >= 'a' && buf[i] <= 'z'){
				if(depth == max_depth){
					match_num[buf[i]-'a']++;
				}
			}
		}

		while(!LEFT.empty()){
			calc_left = LEFT.front();
			LEFT.pop();
			calc_right = RIGHT.front();
			RIGHT.pop();

			person_left = '@';
			for(int i = calc_left; i <= calc_right; i++){
				if(buf[i] >= 'a' && buf[i] <= 'z'){
					if(person_left == '@'){
						person_left = buf[i];
					}else{
						person_right = buf[i];
					}
				}
			}

			if(table[person_left-'a'] == match_num[person_left-'a']-1 && table[person_right-'a'] >= match_num[person_right-'a']){
				winner = person_right;
				lose_num++;
			}else if(table[person_left-'a'] >= match_num[person_left-'a'] && table[person_right-'a'] == match_num[person_right-'a']-1){
				winner = person_left;
				lose_num++;
			}else{
				printf("No\n");
				return 0;
			}

			for(int i = calc_left; i <= calc_right; i++){
				if(buf[i] == winner){
					//Do nothing
				}else{
					buf[i] = '@';
				}
			}
		}
	}

	printf("Yes\n");

	return 0;
}

Measured memory_bytes: 3156
from math import sqrt
N=int(input())
q=int(sqrt(N*2))
if N*2!=q*q+q:print("No")
else:
    S=[list(range(1,q+1))]
    for j in range(1,q+1):S.append([j])
    last = q
    for i in range(1,q):
        r = list(range(last+1,last+1+q-i))
        S[i] += r
        for j in range(q-i):
            S[i+j+1] += [r[j]]
        last = r[-1]
    print("Yes")
    print(len(S))
    for s in S: print(len(s), " ".join(str(i)for i in s))

Measured memory_bytes: 9204
n,x=gets.split.map(&:to_i)
a=gets.split.map(&:to_i)
c=0
if a[0]>x
  c=a[0]-x
  a[0]=x
end
(n-1).times do |i|
  d=a[i]+a[i+1]-x
  if d>0
    c+=d
    a[i+1]-=d
  end
end
puts c

Measured memory_bytes: 8580
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int N=10001;
int n,m,k;
int main(){
	scanf("%d%d",&n,&m);
	if (n%m==0)	printf("%d\n",n/m);
	else printf("%d\n",n/m+1);
	return 0;
}

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

using namespace std;
using ll = long long;
namespace mod {

template <class t, int m>
class mint;

template <class t, int m>
mint<t, m> pow(const mint<t, m> &base, t exp);

template <class t, int m>
mint<t, m> inv(const mint<t, m> &n);

template <class t, int m>
class mint {
  t n_;

 public:
  mint() : n_(0) {}
  mint(t n) : n_((n % m + m) % m) {}

  mint &operator+=(const mint &rhs) {
    n_ += rhs.n_;
    if (n_ >= m) {
      n_ -= m;
    }

    return *this;
  }

  mint &operator-=(const mint &rhs) {
    n_ += m - rhs.n_;
    if (n_ >= m) {
      n_ -= m;
    }

    return *this;
  }

  mint &operator*=(const mint &rhs) {
    n_ = n_ * rhs.n_ % m;
    return *this;
  }

  mint &operator/=(const mint &rhs) { return (*this) *= inv(rhs); }

  t get() { return n_; }
};

template <class t, int m>
mint<t, m> operator-(const mint<t, m> &lhs, const mint<t, m> &rhs) {
  mint<t, m> res(lhs);
  return res -= rhs;
}

template <class t, int m>
mint<t, m> operator+(const mint<t, m> &lhs, const mint<t, m> &rhs) {
  mint<t, m> res(lhs);
  return res += rhs;
}

template <class t, int m>
mint<t, m> operator*(const mint<t, m> &lhs, const mint<t, m> &rhs) {
  mint<t, m> res(lhs);
  return res *= rhs;
}

template <class t, int m>
mint<t, m> operator/(const mint<t, m> &lhs, const mint<t, m> &rhs) {
  mint<t, m> res(lhs);
  return res /= rhs;
}

template <class t, int m>
mint<t, m> pow(const mint<t, m> &base, t exp) {
  if (exp == 0) {
    return 1;
  }

  auto a = pow(base, exp / 2);
  a *= a;
  if (exp % 2 == 1) {
    a *= base;
  }

  return a;
}

template <class t, int m>
mint<t, m> inv(const mint<t, m> &n) {
  return pow(n, static_cast<t>(m - 2));
}
}  // namespace mod

const int md = 1e9 + 7;
using mint = mod::mint<long long, md>;

int main(int argc, const char *argv[]) {
  //
  int n;
  cin >> n;

  vector<mint> va;
  mint sum = 0;
  for (int i = 0; i < n; ++i) {
    ll a;
    cin >> a;
    va.emplace_back(a);
    sum += va.back();
  }

  vector<mint> psum{0};
  partial_sum(va.begin(), va.end(), back_inserter(psum));

  mint ans = 0;
  for (int i = 0; i < n; ++i) {
    mint a = va[i];
    ans += (psum.back() - psum[i + 1]) * a;
  }

  cout << ans.get() << '\n';
  return 0;
}

Measured memory_bytes: 7992
n=int(input())
t,a=map(int,input().split())
h=list(map(int,input().split()))
ans=0
sa=float("inf")
for i in range(n):
  if abs((t-h[i]*0.006)-a)<sa:
    sa=abs((t-h[i]*0.006)-a)
    ans=i+1
print(ans)

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

const int syosu_atai[4]={5000,2500,1250,625};

int main(void) {
	char input[10000];
	char out_buf[1000];
	int seisuu,syosu;
	char* np;
	int i;
	while(1) {
		scanf("%s",input);
		if(input[0]=='-')break;
		np=strtok(input,".");
		seisuu=atoi(np);
		if(seisuu>255) {
			puts("NA");
			continue;
		}
		np=strtok(NULL,".");
		if(np==NULL)syosu=0;
		else {
			if(strlen(np)>4) {
				puts("NA");
				continue;
			}
			while(strlen(np)<4)strcat(np,"0");
			syosu=atoi(np);
		}
		for(i=0;i<8;i++) {
			out_buf[i]=(seisuu & (1<<(7-i)))?'1':'0';
		}
		out_buf[8]='.';
		for(i=0;i<4;i++) {
			if(syosu>=syosu_atai[i]) {
				out_buf[9+i]='1';
				syosu-=syosu_atai[i];
			} else out_buf[9+i]='0';
		}
		out_buf[13]=0;
		puts(syosu>0?"NA":out_buf);
	}
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define ll unsigned long long int
#define mod 1000000007
#define vec vector<long long int>
#define fi first
#define se second
#define pb push_back
int main()
{
    string s;
    cin >> s;
    cout << s[0] << s[1] << s[2];
}

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

#define ll long long
#define INF_LL 1LL << 60
#define INF 99999999
#define MOD (ll)1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, a, n) for(int i = a; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

void put_double(double obj){printf("%.12f\n",obj);};

template < typename T > std::string to_string( const T& n )
{
    std::ostringstream stm ;
    stm << n ;
    return stm.str() ;
}

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


int main()
{
    int x1, y1, x2, y2;

    cin >> x1 >> y1 >> x2 >> y2;

    int diff_x = x2 - x1;
    int diff_y = y2 - y1;

    cout << x2-diff_y << " " << y2+diff_x << " " << x2-diff_y-diff_x << " " << y2+diff_x-diff_y << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 
  int N = 0;//総人数
  //int b = 0;//宿題の個数
  //int c = 0;

  cin >> N;

  vector<int> vec(N);
  //vector<int> mem(N);//記憶用
  vector<int> output(N);//各社員番号の部下の人数

  for(int k=0; k < N-1; k++){
      cin >> vec.at(k);
      
      output.at(k) = 0;
      //c+=vec.at(k);
  }

int a=0;
    //cout << a << b << c << endl;
//m：考えている社員番号
  for(int m = 0; m < N-1; m++){
      a = vec.at(m);
      output.at(a-1) = output.at(a-1) + 1;
  }
 for(int j = 0; j < N; j++){
     cout << output.at(j) << endl;
 }

}

Measured memory_bytes: 4792
#include<iostream>
#include<string>
using namespace std;
int main(){
  int n,A=0,B=0,C=0,D=0;
  cin>>n;
  for(int i=0;i<n;i++){
    string s;
    cin>>s;
    if(s=="AC"){
    A++;
   }
 
       if(s=="WA"){
    B++;
  }

                 if(s=="TLE"){
    C++;
  }

     if(s=="RE"){
    D++;
  }
 
  }
  
   cout<<"AC"<<" x "<<A<<endl; 
    cout<<"WA"<<" x "<<B<<endl; 
             cout<<"TLE"<<" x "<<C<<endl; 
             cout<<"RE"<<" x "<<D<<endl; 
  return 0;
}         
        

Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
using pll = pair<long long, long long>;
const int INF = 1<<29;


int main(){
  int h,w;
  cin >> h >> w;
  vector<vector<int>> table(10,vector<int>(10));
  for(int i=0;i<10;i++){
    for(int j=0;j<10;j++){
      cin >> table[i][j];
    }
  }
  vector<vector<int>> a(h+1,vector<int>(w+1));
  for(int i=1;i<=h;i++){
    for(int j=1;j<=w;j++){
      cin >> a[i][j];
    }
  }
  for(int k=0;k<10;k++){
    for(int i=0;i<10;i++){
      for(int j=0;j<10;j++){
        if(table[i][j] > table[i][k] + table[k][j]){
          table[i][j] = table[i][k] + table[k][j];
        }
      }
    }
  }
  int ans = 0;
  for(int i=1;i<=h;i++){
    for(int j=1;j<=w;j++){
      if(a[i][j] != -1){
        ans += table[a[i][j]][1];
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3776
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define MD 1000000007
#define INF 1ll<<60
typedef pair<ll, ll> P;
template <typename T>
std::string tostr(const T &t){std::ostringstream os;os << t;return os.str();}
int dx[4]={1, 0, -1, 0}, dy[4]={0, 1, 0, -1};

int main(){
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    ll x=c*d/__gcd(c,d);
    x=(b/x)-((a-1)/x);
    c=(b/c)-((a-1)/c);
    d=(b/d)-((a-1)/d);
    cout<<b-a+1-(c+d-x)<<endl;
    return 0;
}

Measured memory_bytes: 256
from itertools import *

N = int(input())
An = list(map(int, input().split()))

class MyIter:

    def __init__(self, it):
        self.it = it
        self.num_negs = 0
        pass

    def __iter__(self):
        for value in self.it:
            if value < 0:
                self.num_negs += 1
                yield -value
                pass
            else:
                yield value
                pass
            pass
        pass

    pass

myiter = MyIter(An)
Bn = list(myiter)
ans = sum(Bn)

if myiter.num_negs % 2 == 1:
    ans -= 2 * min(Bn)
    pass

print(ans)


Measured memory_bytes: 14512
#include <bits/stdc++.h>
#define int long
#define ll long long
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
int gcd(int a,int b){return b ? gcd(b,a%b) : a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}

main() {
    int N; cin >> N;
    int A[N],B[N];
    rep(i,N) cin >> A[i];
    rep(i,N) cin >> B[i];
    int AS[N],BS[N];
    rep(i,N){
       if(!i) AS[i]=A[i];
       else {
           AS[i]=A[i]+AS[i-1];
       }
    }
    for(int i=N-1;i>=0;i--){
        if(i==N-1) BS[N-1-i]=B[i];
        else{
            BS[N-1-i]=B[i]+BS[N-i-2];
        }
    }
    int ans=0;
    rep(i,N){
        if(!i) ans=BS[N-1]+AS[0];
        else {
            ans=max(ans,BS[N-1-i]+AS[i]);
        } 
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256