akhauriyash/Code-Regression huggingface dataset:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		FastScanner in = new FastScanner(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskC solver = new TaskC();
		solver.solve(1, in, out);
		out.close();
	}

	static class TaskC {
		public void solve(int testNumber, FastScanner in, PrintWriter out) {
			int n = in.nextInt();
			final int N = 100010;
			int[] a = new int[N];
			for (int i = 0; i < n; i++) {
				++a[in.nextInt() + 1];
			}
			int ans = 0;
			for (int i = 1; i + 1 < N; i++) {
				ans = Math.max(ans, a[i] + a[i - 1] + a[i + 1]);
			}
			out.println(ans);
		}

	}

	static class FastScanner {
		private BufferedReader in;
		private StringTokenizer st;

		public FastScanner(InputStream stream) {
			in = new BufferedReader(new InputStreamReader(stream));
		}

		public String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					String rl = in.readLine();
					if (rl == null) {
						return null;
					}
					st = new StringTokenizer(rl);
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return st.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

	}
}



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

n = int(input())
a = list(map(int,input().split()))

d = dict()
res = 0


d[n-1-a[-1]] = 1

for i in range(n-2,-1,-1):
    if a[i]+i in d:
        res += d[a[i] + i]
    
    if i-a[i] in d:
        d[i-a[i]] += 1
    else:
        d[i-a[i]] = 1

print(res)

Measured memory_bytes: 111268
#include<bits/stdc++.h>
using namespace std;
#define int long long
int32_t main()
{
    int n,k;
    cin>>n>>k;
    vector<int> a(n);
    if(k>n) {cout<<0; return 0;}
    for(int i=0;i<n;i++)
    {
        cin>>a[i];

    }
    sort(a.begin(),a.end());
    int sum=0;
    for(int i=0;i<n-k;i++)
    {
        sum+=a[i];
        //cout<<s[i]<<" ";
    }
    cout<<sum;
    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  string S;
  cin >> S;
  int count = 0;
  if(S.at(2)==S.at(3)){
    count++;
  }
  if(S.at(4)==S.at(5)){
    count++;
  }
  if(count == 2){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=20;
#define ll long long
#define oo 1000000000000
ll n,a[N];
ll dp(int l,int r,int x,int y){
	if(r-l<=1)return 0;
	ll ans=oo;
	for(int m=l+1;m<=r-1;++m){
		ans=min(ans,dp(l,m,x,x+y)+dp(m,r,x+y,y)+(x+y)*a[m]);
	}
	return ans;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;++i)cin>>a[i];
	cout<<a[1]+a[n]+dp(1,n,1,1);
	return 0;
} 

Measured memory_bytes: 384
import math

while True:
    try:
        m, n = map(int, raw_input().split())

        f2 = int(math.log(n, 2)) + 1
        f3 = int(math.log(n, 3)) + 1
        f5 = int(math.log(n, 5)) + 1

        c = 0
        for i in range(f2):
            for j in range(f3):
                for k in range(f5):
                    if m <= (2 ** i) * (3 ** j) * (5 ** k) <= n:
                        c += 1
        print c

    except ValueError:
        break

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

int main() {
    int64_t N,K;
    cin >> N >> K;
    
    if ( K % 2 == 0 ) {
        int64_t k2 = K / 2;
        int64_t num0 = N / K;
        int64_t num1 = N / k2 - num0;
        //cout << num0 << num1 << endl;
        cout << num0 * num0 * num0 + num1 * num1 * num1 << endl;
    } else {
        int64_t num = N / K;
        cout << num * num * num << endl;
    }
}


Measured memory_bytes: 3652
#include<iostream>
#include<iomanip>
//#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cassert>
using namespace std;
typedef long long ll;
const int Nmax = 100;
int N, X, L[Nmax];

int main(){
	cin >> N >> X;
	for(int i=0; i<N; i++) cin >> L[i];

	vector<int> cum(N);
	cum[0] = L[0];
	for(int i=1; i<N; i++) cum[i] = cum[i-1]+L[i];

	int ans = 1;
	for(int i=0; i<N; i++){
		if(cum[i] <= X) ans++;
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
#define ote(x) cout<<(x)<<endl
#define all(x) (x).begin(),(x).end()
#define rp(i,s,e) for(int i=(s);i<(e);++i)
#define rpz(i,e) rp(i,0,(e))
#define irp(i,s,e) for(int i=(s);i>(e);--i)
#define irpz(i,s) irp(i,(s),-1)
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 A,B;
string S,T,U;

void solve(){
	if(U==S) A--;
	else B--;
	cout<<A<<" "<<B<<endl;
}

int main(){
	cin>>S>>T>>A>>B>>U;
	solve();
	// printf("%f\n",solve());
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <algorithm>
#include <utility>
#define llint long long
#define inf 1e18
#define rep(x, s, t) for(llint (x) = (s); (x) < (t); (x)++)
#define Rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))

using namespace std;
typedef pair<llint, llint> P;

llint x, k, d;

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> x >> k >> d;
	x = abs(x);
	
	if(x / d >= k){
		cout << x - k * d << endl;
		return 0;
	}
	
	llint ans = inf, y = x / d;
	for(int i = -10; i <= 10; i++){
		if((y+i) >= 0 && (y+i) % 2 == k % 2) ans = min(ans, abs(x - (y+i) * d));
	}
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 3656
package main

import (
	"fmt"
)

func main() {
	var n, m int

	fmt.Scan(&n)
	s := make(map[string]int, 200)
	for i := 0; i<n; i++ {
		var key string
		fmt.Scan(&key)
		s[key]++
	}

	fmt.Scan(&m)
	for i := 0; i<m; i++ {
		var key string
		fmt.Scan(&key)
		s[key]--
	}

	max := 0
	for _, v := range s {
		if max < v {
			max = v
		}
	}
	fmt.Println(max)
}

Measured memory_bytes: 512
N = int(input())
X = input()

arr = [0 for _ in range(N+1)]
for i in range(1, N+1):
    cnt = bin(i).count('1')
    arr[i] = arr[i%cnt] + 1

x = int(X, 2)
pop = X.count('1')
plu = x % (pop+1)
mai = x % (pop-1) if pop>1 else 0

#bi = 1 << N
for i in range(N):
    #bi = bi >> 1
    if X[i] == '0':
        #res = (plu + bi % (pop+1)) % (pop+1)
        res = (plu + pow(2, N-1-i, pop+1)) % (pop+1)
    else:
        if pop == 1:
            print(0)
            continue
        #res = (mai - bi % (pop-1)) % (pop-1)
        res = (mai - pow(2, N-1-i, pop-1)) % (pop-1)
    print(arr[res] + 1)

Measured memory_bytes: 11300
//raja1999
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip> 
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >

//std::ios::sync_with_stdio(false);
ll a[200005],b[200005];
int main(){
	std::ios::sync_with_stdio(false);
	ll n,i,fl=0,ans=0,maxx=-100,minn=inf,c=0;
	cin>>n;
	rep(i,n){
		cin>>a[i]>>b[i];
		if(a[i]!=b[i]){
			fl=1;
		}
		if(a[i]>b[i]){
			c++;
			minn=min(minn,b[i]);
		}
	}	
	if(fl==0){
		cout<<0<<endl;
	}
	else{
		if(c==1){
			rep(i,n){
				if(a[i]<=b[i]){
					ans+=a[i];
				}
				else{
					ans+=a[i]-b[i];
				}		
			}
		}
		else{
			rep(i,n){
				ans+=a[i];	
			}
			ans-=minn; 
		}
		cout<<ans<<endl;
	}

} 
	

Measured memory_bytes: 640
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<string>
#include<queue>
#include<utility>
#include<cmath>

using namespace std;


int main()
{

  int N;
  cin >> N;

  vector<int> V(N);

  for(int i = 0; i < N; i++){
    cin >> V[i];
  }

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

  double sum = V[0];

  for(int i = 1; i < N; i++){
    sum = (sum + (double)V[i])/2.0;
  }


  cout << sum << endl;

  return 0;
}


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

using LL = long long;
using pli = pair<LL, int>;
using Edge = tuple<int, LL, LL>;

int n, m, s, t;
vector<LL> d1, d2;
vector<LL> ret;
vector<vector<Edge>> G;
priority_queue<pli, vector<pli>, greater<pli>> pq;

void gao1() {
  while(!pq.empty()) pq.pop();
  d1[s] = 0; pq.emplace(0, s);
  int u, v;
  LL w, tw;
  while(!pq.empty()) {
    tie(tw, u) = pq.top(); pq.pop();
    if(d1[u] < tw) continue;
    for(auto edge : G[u]) {
      tie(v, w, ignore) = edge;
      if(d1[v] > d1[u] + w) {
        d1[v] = d1[u] + w;
        pq.emplace(d1[v], v);
      }
    }
  }
}

void gao2() {
  while(!pq.empty()) pq.pop();
  d2[t] = 0; pq.emplace(0, t);
  int u, v;
  LL w, tw;
  while(!pq.empty()) {
    tie(tw, u) = pq.top(); pq.pop();
    if(d2[u] < tw) continue;
    for(auto edge : G[u]) {
      tie(v, ignore, w) = edge;
      if(d2[v] > d2[u] + w) {
        d2[v] = d2[u] + w;
        pq.emplace(d2[v], v);
      }
    }
  }
}

signed main() {
  // freopen("in", "r", stdin);
  int u, v;
  LL a, b;
  while(cin >> n >> m >> s >> t) {
    G.resize(n+1); ret.resize(n+1);
    d1.resize(n+1); d1.assign(d1.size(), numeric_limits<LL>::max());
    d2.resize(n+1); d2.assign(d2.size(), numeric_limits<LL>::max());
    for(int i = 1; i <= m; i++) {
      cin >> u >> v >> a >> b;
      G[u].emplace_back(v, a, b);
      G[v].emplace_back(u, a, b);
    }
    gao1(); gao2();
    for(int i = 1; i <= n; i++) ret[i] = d1[i] + d2[i];
    for(int i = n-1; i >= 1; i--) ret[i] = min(ret[i], ret[i+1]);
    for(int i = 1; i <= n; i++) {
      cout << (LL)1E15 - ret[i] << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 13560
def candy():
    boxNum, x = [int(i) for i in input().split()]
    ain = input()
    alist = ain.split(' ')

    s = 0
    
    for i in range(0, boxNum-1):
        if int(alist[i+1]) + int(alist[i]) > x:
            s = s + (int(alist[i+1]) + int(alist[i]) - x)
            alist[i+1] = x - int(alist[i])
            if int(alist[i+1]) < 0:
                alist[i] = int(alist[i]) + int(alist[i+1])
                alist[i+1] = 0
        
    print(s)
    
candy()

Measured memory_bytes: 19336
#include <bits/stdc++.h>
typedef long long ll;
#define REP(i,n) for(int i=0;i<n;i++)
#define ALL(x) (x).begin(),(x).end()
using namespace std;

//素因数分解
vector<pair<ll,int>> factorize(ll n){
    vector<pair<ll,int>>res;
    for(ll i=2;i*i<=n;i++){
        if(n%i)continue;
        res.emplace_back(i,0);
        while (n%i == 0)
        {
        n /= i;
        res.back().second++;
        }
        
    }
    if(n != 1) res.emplace_back(n,1);
    return res;
}

void trace(int A[],int N){
    REP(i,N){
        if(i>0)printf(" ");
        printf("%d",A[i]);
    }
    printf("\n");
}


int main(){
    int N;
    cin >> N;
    int ans = N*800 - ((N/15)*200);
    cout << ans << endl;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
//#define int long long

template <class T>
bool INRANGE(T x, T a, T b) { return a <= x && x <= b; }
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 (a > b){ a = b; return 1;}return 0;}
template <class T>
void printv(vector<T> v) {for (T t : v) {cout << t << " ";}cout << '\n';}

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define RREP(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define RFOR(i, a, b) for (int i = (a); i >= (b); --i)
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
                      << " " << __FILE__ << endl;

typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<vi> vvi;
typedef pair<int, int> pii;

vi to[2500];
vi from[2500];
bool reachable_from1[2500];
bool reachable_ToN[2500];
bool ok[2500];

void dfs(int n) {
    if (reachable_from1[n]) return;
    reachable_from1[n] = true;

    for (int u : to[n]) {
        dfs(u);
    }
}
void rdfs(int n) {
    if (reachable_ToN[n]) return;
    reachable_ToN[n] = true;

    for (int u : from[n]) {
        rdfs(u);
    }
}
const int INF = 1001001001;

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

    vector<tuple<int,int,int>> edges;

    REP(i,M) {
        int A, B, C;
        cin >> A >> B >> C;
        --A, --B;
        C -= P;
        C = -C;

        edges.emplace_back(A,B,C);
        to[A].emplace_back(B);
        from[B].emplace_back(A);
    }

    dfs(0);
    rdfs(N-1);
    
    REP(i,N) ok[i] = reachable_from1[i] and reachable_ToN[i];

    vi d(N, INF);
    d[0] = 0;
    bool upd = true;
    int step = 0;
    while (upd) {
        upd = false;
        REP(i, M){
            int a, b, c;
            tie(a, b, c) = edges[i];

            if (!ok[a] or !ok[b]) continue;

            int new_d = d[a] + c;
            if (new_d < d[b]) {
                upd = true;
                d[b] = new_d;
            }
        }

        step++;
        if (step > N) {
            cout << -1 << endl;
            return 0;
        }
    }
    int ans = max(0,-d[N-1]);
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 640
def area(x2, y2, points):
    x1 = y1 = 0
    for x, y, a in points:
        if a == 1:
            x1 = min(max(x1, x), x2)
        elif a == 2:
            x2 = max(min(x2, x), x1)
        elif a == 3:
            y1 = min(max(y1, y), y2)
        else:
            y2 = max(min(y2, y), y1)
    return (x2 - x1) * (y2 - y1)


if __name__ == '__main__':
    w, h, n = list(map(int, input().split()))
    points = [list(map(int, input().split())) for _ in range(n)]
    print(area(w, h, points))

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);

using namespace std;

namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9;

int main(){
	cin.tie(0); cin.sync_with_stdio(0);
	int n; cin >> n;
	vi v(n);
	rep(i, n) cin >> v[i];
	sort(all(v));
	v[n - 1] /= 2;
	cout << accumulate(all(v), 0) << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <map>
 
using namespace std;
int N,K;

int main()
{
  int ret;

  cin >> N >> K;

  for (ret = 0; N>0; ret++) {
    N/=K;
  }
  printf("%d\n", ret);
  return 0;
}


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

#define int long long
#define For(i, a, b) for (int i = (a); i <= static_cast<int>(b); i++)
#define Forr(i, a, b) for (int i = (a); i >= static_cast<int>(b); i--)
#define rep(i, n) For(i, 0, n - 1)
#define repall(i, arr) for (auto& i : (arr))
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define dump(x) cerr << #x << " = " << (x) << '\n'

template <typename T>
using pq = priority_queue<T>;
template <typename T>
using pqr = priority_queue<T, vector<T>, greater<T>>;
const int INF = INT_MAX / 2;
constexpr int MOD = 1e9 + 7;
using P = pair<int, int>;
using vec = vector<int>;
using mat = vector<vec>;

template <typename T1, typename T2>
ostream& operator<<(ostream& stream, const pair<T1, T2>& p) {
    return stream << p.first << " " << p.second;
}
template <typename T>
void print(const vector<vector<T>> matrix) {
    repall (vec, matrix)
        print(vec);
}
template <typename T>
void print(const vector<T> vec) {
    unsigned int len = vec.size();
    rep (i, len - 1)
        cout << vec[i] << ' ';
    cout << vec[len - 1] << '\n';
}
template <typename Arg>
void print(const Arg arg) {
    cout << arg << '\n';
}
template <typename Head, typename... Args>
void print(const Head head, const Args... args) {
    cout << head << " ";
    print(args...);
}
template <typename T>
T sum_(vector<T> vec, T init = 0) {
    return std::accumulate(all(vec), T(init));
}

void yn(bool tf) { print(tf ? "Yes" : "No"); }
void YN(bool tf) { print(tf ? "YES" : "NO"); }

template <typename T>
void init(vector<vector<T>> m) {
    repall (v, m)
        init(v);
}

template <typename T>
void init(vector<T>& v) {
    rep (i, v.size())
        cin >> v[i];
}

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
// -------------------------------------------------------------------

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

    int n;
    cin >> n;
    vec a(n);
    init(a);

    int ans = a[0];
    rep (i, n) {
        if (!i) continue;
        ans = gcd(ans, a[i]);
    }
    print(ans);

    return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>

int main(int argc, char *argv[])
{
  int i, j;

  for(i = 0; i < 9; i++)
    for(j = 0; j < 9; j++)
      {
	int pro = (i + 1) * (j + 1);
	printf("%dx%d=%d\n",i+1, j+1, pro);
      }
  return 0;
}

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

#define ff              first
#define ss              second
#define int             long long int
#define pb              push_back
#define mp12            make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pq1             priority_queue<int>
#define pqr1            priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zerobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)

void FIO(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
}

int modInv(int a,int b,int m){int res=1;a=a%m;while(b>0){if(b&1){res=(res*a)%m;}a=(a*a)%m;b=b>>1;}return res;}



void solve(){
	int n,k, i,j, ans;
    cin >> n >> k;
 
    int a[n+1];
 
    for (i = 1; i <= n; i++)
        cin >> a[i];
 
    vector<vector<int>> dp(n + 2, vector<int>(k + 2));
 
    for(j=0;j<=k;j++)
        dp[1][j]=(j>a[1])?0:1;
 
    for(i=2;i<=n;i++)
    {
        for(j=0;j<=k;j++)
        {
            if(j==0)
                dp[i][j]=dp[i-1][j];
            else
                dp[i][j] = (dp[i][j-1]+dp[i-1][j] - ( (j-a[i]-1 >=0)? dp[i-1][j-a[i]-1]:0)+mod)%mod;
        }
    }
 
    ans=dp[n][k];
    cout << ans << endl;
}
    

int32_t main()
{
    //FIO();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    solve();


    return 0;
}


Measured memory_bytes: 83920
import itertools
import copy
N = int(input())
Xs = list(map(int,input().split(" ")))
XsOrigin = copy.deepcopy(Xs)
Xs.sort()
l = int(len(Xs)/2)
left = Xs[l-1]
right =Xs[l]
for i in XsOrigin:
    if i <=left:
        print(right)
    else:
        print(left)

Measured memory_bytes: 27284
N, M, C = map(int,input().split())
B = list(map(int,input().split()))
A = [list(map(int,input().split())) for i in range(N)]

ans = 0

for i in range(N):
  abc = 0
  for j in range(M):
    abc += A[i][j] * B[j]
  else:
    abc += C
    
  if abc > 0:
    ans += 1
    
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <set>

using namespace std;

int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a % b);
}

int gcd_wo_idx(vector<int> &v, int idx) {
	int g = idx == 0 ? v[1] : v[0];
	for (int i = 0; i < v.size(); i++) {
		if (i == idx) {
			continue;
		}
		g = gcd(g, v[i]);
	}

	return g;
}

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

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

	sort(a.begin(), a.end());
	int g = gcd_wo_idx(a, -1);
	if (g > 1) {
		for (auto &x: a) {
			x /= g;
		}
	}

	int ans = g;
	ans = max(ans, g * gcd_wo_idx(a, 0));

	for (int i = 1; i < n; i++) {
		if (gcd(a[0], a[i]) == 1) {
			int tmp = gcd_wo_idx(a, i);
			ans = max(ans, tmp * g);
			break;
		}
	}

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


Measured memory_bytes: 640
#include<iostream>
#include<string>
#include<vector>
#include<map>

using namespace std;

vector<int> ans;
string migi = "yuiophjklnm";
map<char,bool> te;

void setmap(void);
int main(){
	setmap();
	while(1){
		string str;
		cin >> str;
		if(str == "#") break;
		bool now = te[str[0]];
		int count = 0;
		for(int i = 1;i < str.size();i++){
			if(now == te[str[i]]);
			else{count++;now = te[str[i]];}
		}
		ans.push_back(count);
	}
	for(int i = 0;i < ans.size();i++) cout << ans[i] << endl;
}

void setmap(void){
	for(int i = 0;i < 26;i++){
		char al = 'a' + i;
		te[al] = true;
		for(int j = 0;j < migi.size();j++){
			if(migi[j] == al){
				te[al] = false;
				break;
			}
		}
	}
}

Measured memory_bytes: 3172
import collections
n = int(input())
v = list(map(str, input().split()))
gu_row = []
ki_row = []

for i in range(n):
    if i % 2 == 0:
        gu_row.append(v[i])
    elif i % 2 == 1:
        ki_row.append(v[i])

gu_count = collections.Counter(gu_row).most_common()
ki_count = collections.Counter(ki_row).most_common()

if len(gu_count) > 1 and len(ki_count) > 1:
    if gu_count[0][0] != ki_count[0][0]:
        ans = n - gu_count[0][1] - ki_count[0][1]
    elif gu_count[0][0] == ki_count[0][0] and len(gu_count) == 1:
        ans = n - gu_count[0][1] - ki_count[1][1]
    elif gu_count[0][0] == ki_count[0][0] and len(ki_count) == 1:
        ans = n - gu_count[1][1] - ki_count[0][1]
    else:
        ans = n - max(gu_count[0][1] + ki_count[1][1], gu_count[1][1] + ki_count[0][1])
else:
    if gu_count[0][0] != ki_count[0][0]:
        ans = n - gu_count[0][1] - ki_count[0][1]
    else:
        ans = gu_count[0][1]

print(ans)

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

#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

using ll = long long;
using P = pair<int, int>;

int main() {
  int n;
  cin >> n;
  map<string, vector<pair<int, int>>> mp;
  rep(i, n) {
    string s;
    int p;
    cin >> s;
    cin >> p;
    if (mp.count(s) == 0) {
      mp[s] = vector<pair<int, int>>();
    }
    mp[s].push_back(make_pair(p, i + 1));
  }

  for (auto v:mp) {
    vector<pair<int, int>> &list = v.second;
    sort(list.begin(), list.end(), greater<>());
    for (auto item :list) {
      cout << item.second << endl;
    }
  }

  return 0;
}


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

int64_t MOD = 1000000007;
double PI = 3.141592653589793;

int main()
{
    vector<int> dp(100001, MOD);
    dp[0] = 0;
    vector<int> list{1, 6, 9, 36, 81, 216, 729, 1296, 6561, 7776, 46656, 59049};
    sort(list.begin(), list.end());
    int N;
    cin >> N;
    for (int i = 1; i <= 100000; i++)
    {
        for (int j = 0; j < 12; j++)
        {
            if (i - list[j] < 0)
                break;
            else
                dp[i] = min(dp[i], dp[i - list[j]] + 1);
        }
    }
    cout << dp[N];
}

Measured memory_bytes: 3704
N, M, X = list(map(int, input().split()))
CA = [list(map(int, input().split())) for i in range(N)]

set_list = []
for i in range(2 ** N):
    select = []
    for j in range(N):
        if ((i >> j) & 1):
            select.append(j)
    if len(select) != 0:
        set_list.append(select)
    
cost = []
for i in range(2 ** N - 1):
    cost.append(sum([CA[set_list[i][j]][0] for j in range(len(set_list[i]))]))

skill = []
for i in range(2 ** N - 1):
    tmp = [0]*M
    for j in set_list[i]:
        for k in range(M):
            tmp[k] += CA[j][k+1]
    skill.append(tmp)

pool = []
for i in range(2**N - 1):
    flag = 0
    for j in skill[i]:
        if j < X:
            flag = 1
    if flag == 0:
        pool.append(cost[i])
        

if len(pool) == 0:
	print(-1)
else:
    print(min(pool))


Measured memory_bytes: 11920
val = input().split(' ')
N = int(val[0])
A = int(val[1])
B = int(val[2].strip())

if (B - A) % 2 == 0:
    print((B-A)//2)
else:
    diff = N - B if A - 1 > N - B else A - 1
    flip = diff + 1
    distance = (B - A - 1) // 2
    print(flip + distance)


Measured memory_bytes: 3064
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <sstream>
#include <cmath>
#include <climits>
#include <set>
#include <iostream>
#include <map>
#include <functional>
#include <cstdlib>
#include <numeric>
#include <queue>
#include <complex>

using namespace std;

#define reep(i,f,n) for(int i=f; i<int(n); ++i)
#define rep(i,n) reep(i,0,n)

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef complex<double> Point;

int main()
{
	int q;
	while(scanf("%d", &q), q!=-1){
		double x = q/2.0;
		while(fabs(x*x*x-q) >= 0.00001*q)
			x = x - (x*x*x-q)/(3.0*x*x);
		printf("%f\n", x);
	}

	return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<tuple>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define Per(i,sta,n) for(int i=n-1;i>=sta;i--)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};

int n;
ll ans=0;
ll a[100010],S[100010];



void solve(){
    cin >> n;
    rep(i,n+1){
        cin >> a[i];
    }
    if(n==0){
        if(a[0]==1) cout << 1 << endl;
        else cout << -1 << endl;
        return;
    }
    if(a[0]!=0) {
        cout << -1 << endl;
        return;
    }
    per(i,n+1){
        S[i]=S[i+1]+a[i];
    }
    ll f=1;
    rep(i,n+1){
        ans+=f;
        f-=a[i];
        if(f<0){
            cout << -1 << endl;
            return;
        }
        f=min(2*f,S[i+1]);
        //cout << i << " " << S[i+1] << " " << f << endl;
    }
    cout << ans << endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(50);
    solve();
}

Measured memory_bytes: 5172
import java.util.Scanner;

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

        long [] a = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};

        int k = stdIn.nextInt();

        System.out.println(a[k-1]);


    }
}

Measured memory_bytes: 23764
#include<iostream>
#include<vector>
#include<queue>
using namespace std;

void BFS(int s, const vector<vector<int> >& G, vector<int>& D){
    queue<int> Q;
    Q.push(s);
    D[s] = 0;
    while (!Q.empty()) {
        int f = Q.front();
        for (int i = 0; i < G[f].size(); i++) {
            if (D[G[f][i]] == -1) {
                D[G[f][i]] = D[f] + 1;
                Q.push(G[f][i]);
            }
        }
        Q.pop();
    }
}

int main(){
    int n;
    cin >> n;
    vector<vector<int> > G(n + 1);
    for (int i = 0; i < n; i++) {
        int u, k;
        cin >> u >> k;
        for (int j = 0; j < k; j++) {
            int v;
            cin >> v;
            G[u].push_back(v);
        }
    }
    vector<int> D(n + 1, -1);
    BFS(1, G, D);
    for (int i = 1; i <= n; i++) {
        cout << i << " " << D[i] << endl;
    }
    return 0;
}

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

int main()
{
  int n;
  cin >> n;
  vector<int> a(n), l(n+1), r(n+1);
  rep(i,n) cin >> a[i];
  
  a.push_back(0);
  exclusive_scan(a.begin(), a.end(), l.begin(), 0,
                [](int x, int y) {return gcd(x, y); });
  exclusive_scan(a.rbegin(), a.rend(), r.rbegin(), 0,
                [](int x, int y) {return gcd(x, y); });
  
  int ans = 0;
  rep(i,n+1)
    ans = max(ans, gcd(l[i], r[i]));
  
  cout << ans << endl;
  
  //for(auto x : l) cout << x << " "; cout << endl;
  //for(auto x : r) cout << x << " "; cout << endl;
  
  return 0;
}

Measured memory_bytes: 4768
def function(numbers, K):
    ans = 'No'
    for i in range(K+1):
        A = int(numbers[0])
        B = int(numbers[1])
        C = int(numbers[2])
        B = B*2**i
        C = C*2**(K-i)
        if (B > A) & (C > B):
            ans = 'Yes'
    return ans


if __name__ == '__main__':
    numbers = input().split()
    K = int(input())
    print(function(numbers, K))

Measured memory_bytes: 9196
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.UncheckedIOException;
import java.util.StringTokenizer;

class Main{
	static long[][] ryori;
	public static void main(String[] args) {
		SC sc=new SC(System.in);
		int N=sc.nextInt();
		ryori=new long[N][3];
		long a,t;
		for(int i=0; i<N; i++) {
			t=sc.nextLong();
			a=sc.nextLong();
			ryori[i][0]=t+a;
			ryori[i][1]=t;
			ryori[i][2]=a;
		}
		q(ryori,0,N-1);
		long tkhs=0;
		long aoki=0;
		for(int i=0; i<N; i++) {
			if(i%2==0) {
				tkhs+=ryori[N-1-i][1];
			}
			else {
				aoki+=ryori[N-1-i][2];
			}
		}
		pl(tkhs-aoki);
	}
	public static void pl(Object o) {
		System.out.println(o);
	}
	public static void pl() {
		System.out.println();
	}
	public static void p(Object o) {
		System.out.print(o);
	}
	static class SC {
		private BufferedReader reader = null;
		private StringTokenizer tokenizer = null;
		public SC(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
		}
		public String next() {
			if (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new UncheckedIOException(e);
				}
			}
			return tokenizer.nextToken();
		}
		public int nextInt() {
			return Integer.parseInt(next());
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
		public double nextDouble() {
			return Double.parseDouble(next());
		}
		public String nextLine() {
			try {
				return reader.readLine();
			} catch (IOException e) {
				throw new UncheckedIOException(e);
			}
		}
	}
	static void q(long[][] d, int left, int right) {
		if (left>=right) {
			return;
		}
		long p = d[(left+right)/2][0];
		int l = left, r = right;
		long tmp,tmp1,tmp2;
		while(l<=r) {
			while(d[l][0] < p) { l++; }
			while(d[r][0] > p) { r--; }
			if (l<=r) {
				tmp = d[l][0]; d[l][0] = d[r][0]; d[r][0] = tmp;
				tmp1=d[l][1]; tmp2=d[r][1]; d[l][1]=tmp2; d[r][1]=tmp1;
				tmp1=d[l][2]; tmp2=d[r][2]; d[l][2]=tmp2; d[r][2]=tmp1;
				l++; r--;
			}
		}
		q(d, left, r);
		q(d, l, right);
	}
}

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

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

	int n, k, nn;
	cin >> n >> k;
	if(k == 1){
		cout << 0;
		return 0;
	}
	nn = n;
	n -= k;
	cout << n;

	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

long long gcd(long long a, long long b){
	long long r = a%b;
	while(r!=0){
		a = b;
		b = r;
		r = a % b;
	}
	return b;
}

int main(){
	int N;
	long long T[100];

	scanf("%d",&N);
	for(int i=0;i<N;i++){
		scanf("%lld",&T[i]);
	}

	unsigned long long lcm = T[0];
	for(int i=0;i<N-1;i++){
		unsigned long long tmp;
		if(lcm < T[i+1]){
			tmp = lcm / gcd(T[i+1],lcm) * T[i+1];
		}else{
			tmp = lcm / gcd(lcm,T[i+1]) * T[i+1];
		}
		lcm = tmp;
	}

	printf("%lld\n",lcm);

	return 0;
}


Measured memory_bytes: 128
#include <stdio.h>
 
int main(){
	int H1, H2, M1, M2, K;
	scanf("%d %d %d %d %d", &H1, &M1, &H2, &M2, &K);
	int ans = 60 * (H2 - H1) + M2 - M1 - K;
	printf("%d", ans);
	return 0;
}

Measured memory_bytes: 1720
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
//#define MOD 998244353
#define LINF (long long)4e18
#define jck 3.141592

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;



int main(){
	int N; cin >> N;
    vector<int> H(N);
    rep(i,N) cin >> H[i];
    int now = 0;
    int ans = 0;
    rep(i,N-1){
        if(H[i+1] <= H[i]) now++;
        else{
            ans = max(ans,now);
            now = 0;
        }
    }
    ans = max(ans,now);
    cout << ans << endl;
	
}



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

int main(){
    ll n;
    cin >> n;
    ll ans = 1;
    for(ll i = 1;i < n+1;i++){
        ans*=i;
        ans%=1000000007;
    }
    cout << ans << endl;
    return 0;
}


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

int main(void) {
   
   char S[100];
   
   scanf("%s",S);
   
   if (strcmp(S,"SUN") == 0) {
      printf("7\n");
   }
   else if (strcmp(S,"MON") == 0) {
      printf("6\n");
   }
   else if (strcmp(S,"TUE") == 0) {
      printf("5\n");
   }
   else if (strcmp(S,"WED") == 0) {
      printf("4\n");
   }
   else if (strcmp(S,"THU") == 0) {
      printf("3\n");
   }
   else if (strcmp(S,"FRI") == 0) {
      printf("2\n");
   }
   else if (strcmp(S,"SAT") == 0) {
      printf("1\n");
   }
   
   return 0;
}


Measured memory_bytes: 128
r, D, x0 = map(int, input().split())

x1 = r*x0 - D
x2 = r*x1 - D
x3 = r*x2 - D
x4 = r*x3 - D
x5 = r*x4 - D
x6 = r*x5 - D
x7 = r*x6 - D
x8 = r*x7 - D
x9 = r*x8 - D
x10 = r*x9 - D

print(x1)
print(x2)
print(x3)
print(x4)
print(x5)
print(x6)
print(x7)
print(x8)
print(x9)
print(x10)

Measured memory_bytes: 9144
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <deque>
using namespace std;

typedef long long ll;

struct UnionFind{
    vector<int> par;
    vector<int> rank;
    vector<ll> sizes;

    UnionFind(int N): par(N), rank(N), sizes(N){
        for(int i = 0; i < N; i++){
            par[i] = i;
            rank[i] = 0;
            sizes[i] = 1;
        }
    }

    int find(int x){
        if(par[x] == x) 
            return x;
        else 
            return par[x] = find(par[x]);
    }

    bool same(int x, int y){
        return find(x) == find(y);
    }

    void unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y)  return;
        else {
            if(rank[x] < rank[y]){
                par[x] = y;
                sizes[y] += sizes[x];
            } else {
                par[y] = x;
                sizes[x] += sizes[y];
                if(rank[x]==rank[y]) rank[x]++;
            }
        }
    }

    ll size(int x){
        return sizes[find(x)];
    }
};

int main(){
    ll N, M;
    cin >> N >> M;
    UnionFind uni(N+1);

    ll A[2][M];
    ll ans[M+1];
    ans[M] = N*(N-1)/2; 
    for(ll i = 0; i < M; i++){
        cin >> A[0][i] >> A[1][i];
    }
    for(ll i = M-1; i >= 0; i--){
        if(uni.same(A[0][i], A[1][i]))
            ans[i] = ans[i+1];
        else {
            ans[i] = ans[i+1] - uni.size(A[0][i])*uni.size(A[1][i]);
            uni.unite(A[0][i], A[1][i]);
        }
    }

    for(ll i = 1; i <= M; i++){
        cout << ans[i] << endl;
    }
}

Measured memory_bytes: 5248
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		String s = scanner.next();
		int max = 0;
		int count = 0;
		for(int i=0;i<n;i++){
			if(s.charAt(i) == 'I'){
				count++;
			}else{
				count--;
			}
			max = Math.max(max, count);
		}
		System.out.println(max);
	}

}


Measured memory_bytes: 22868
use std::io;

fn main(){
   let sv = sieve(30000);

   loop {
     let n = read_i32();
     if n == 0 {break;}

     let mut cnt: i32 = 0;

     if n % 2 == 0 {
       if n == 6 {cnt += 1;}

       let mut x: i32 = 3;

       while x <= n - 2 - x {
         if is_pn(&sv, x) && is_pn(&sv, n - 2 - x) && is_triangle(2, x, n - 2 - x) {
           cnt += 1;
         }
         x += 2;
       }
     } else {
       if n == 7 {cnt += 1;}

       let mut x: i32 = 3;

       while x <= n - 2 * x {
         let mut y: i32 = x;

         while y <= n - x - y {
           if is_pn(&sv, x) && is_pn(&sv, y) && is_pn(&sv, n - x - y) && is_triangle(x, y, n - x - y) {
             cnt += 1;
           }
           y += 2;
         }
         x += 2;
       }
     }

     println!("{}", cnt);
   }
}

fn is_pn(v: &Vec<bool>, x: i32) -> bool{
  if x < 0 {
    false
  } else {
    v[x as usize]
  }
}

fn sieve(n: usize) -> Vec<bool> {
  let mut v = vec! [true; n + 1];

  v[0] = false;
  v[1] = false;

  let mut i = 2;

  while i * i <= n {
    if v[i] {
      let mut j = i * i;
      while j <= n {
        v[j] = false;
        j += i;
      }
    }
    i += 1;
  }

  v
}

fn read_i32() -> i32{
  let mut buf = String::new();

  io::stdin().read_line(&mut buf).expect("failed to read");

  buf.trim().parse().unwrap()
}

fn is_triangle(x: i32, y: i32, z: i32) -> bool{
 let mut v: Vec<i32> = vec![x, y, z];
 v.sort();
 v[0] + v[1] > v[2]
}



Measured memory_bytes: 5048
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		City[] cities = new City[m];
		for (int i = 0; i < m; i++) {
		    cities[i] = new City(i, sc.nextInt(), sc.nextInt());
		}
		Arrays.sort(cities, new Comparator<City>() {
		    public int compare(City c1, City c2) {
		        if (c1.pref == c2.pref) {
		            return c1.year - c2.year;
		        } else {
		            return c1.pref - c2.pref;
		        }
		    }
		});
		int prev = 0;
		int count = 1;
		for (City c : cities) {
		    if (c.pref != prev) {
		        count = 1;
		        prev = c.pref;
		    } else {
		        count++;
		    }
		    c.no = count;
		}
		Arrays.sort(cities, new Comparator<City>() {
		    public int compare(City c1, City c2) {
		        return c1.id - c2.id;
		    }
		});
		StringBuilder sb = new StringBuilder();
		for (City c : cities) {
		    sb.append(c).append("\n");
		}
		System.out.print(sb);
   }
    
    static class City {
        int id;
        int pref;
        int year;
        int no;
        
        public City(int id, int pref, int year) {
            this.id = id;
            this.pref = pref;
            this.year = year;
        }
        
        public String toString() {
            return String.format("%06d%06d", pref, no);
        }
    }
}


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

int dp[1111][4100];

int main(){
	int N,M;
	cin >> N >> M;
	
	vector<int> a(M);
	vector<int> c(M);
	for(int i=0;i<M;i++){
		int x,y;
		cin >> x >> y;
		a[i]=x;
		for(int j=0;j<y;j++){
			int z;
			cin >> z;
			c[i]+=1<<(z-1);
		}
	}
	
	for(int i=0;i<1111;i++)for(int j=0;j<4100;j++)dp[i][j]=1000000000;
	
	for(int i=0;i<1111;i++)dp[i][0]=0;
	
	for(int i=0;i<M;i++)for(int j=0;j<4096;j++){
		if(dp[i][j]<1000000000){
			dp[i+1][j|c[i]]=min(dp[i][j]+a[i],dp[i+1][j|c[i]]);
		}
		dp[i+1][j]=min(dp[i][j],dp[i+1][j]);
	}
	
	if(dp[M][(1<<N)-1]==1000000000)cout << "-1" << endl;
	else cout << dp[M][(1<<N)-1] << endl;
	
	/*for(int i=0;i<=M;i++){
		for(int j=0;j<((1<<N));j++)cout << dp[i][j] << " ";
		cout << endl;
	}*/
	
	return 0;
}

Measured memory_bytes: 18176
#include <bits/stdc++.h>
using namespace std;
#define int long long int

int power(int x, int y, int p)
{
    int res = 1;      // Initialize result

    x = x % p;  // Update x if it is more than or
                // equal to p

    while (y > 0)
    {
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res*x) % p;

        // y must be even now
        y = y>>1; // y = y/2
        x = (x*x) % p;
    }
    return res;
}

int32_t main(){
	int n;
	cin>>n;
	int arr[n];
	for(int i=0; i<n; i++){
		cin>>arr[i];
	}
	int ans = 1;
	if(n%2==0){
		sort(arr, arr+n);
		for(int i=0; i<n-1; i+=2){
			if(arr[i]!=i+1 or arr[i+1]!=i+1) ans = 0;
		}
		if(ans==0) cout<<ans<<endl;
		else {
			cout<<power(2, n/2, 1000000007)<<endl;
		}
	}
	else{
		sort(arr, arr+n);
		for(int i=1; i<n-1; i+=2){
			if(arr[i]!=i+1 or arr[i+1]!=i+1) ans = 0;
		}
		if(arr[0]!=0) ans = 0;
		if(ans==0) cout<<0<<endl;
		else cout<<power(2, (n-1)/2, 1000000007)<<endl;
	}
}


Measured memory_bytes: 1024
package main

import (
	"fmt"
)

func main() {
	var n, x int
	fmt.Scan(&n, &x)
	l := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&l[i])
	}
	var d int
	for i := 0; i < n; i++ {
		d = d + l[i]
		if d > x {
			fmt.Println(i + 1)
			break
		} else if d <= x && i == n-1 {
			fmt.Println(n + 1)
		}
	}
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pull = pair<ull, ll>;
using pis = pair<int, string>;
#define INF 1000000000
#define LLINF 10000000000000000ll
#define MOD 1000000007LL

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  //cout << fixed << setprecision(15);

  int a;
  cin >> a;
  cout << a + a*a + a*a*a << endl;
}


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

int main()
{
  string s,b;
  cin>>s>>b;
  int blen=b.length();
  int len=s.length();
  int max=-1;
  bool out=0;
  
  if(blen>len)
  {
    cout<<"UNRESTORABLE"<<endl;
    out=1;
    
  }
  if(out==0){
  for(int i=0;i<len-blen+1;i++)
  {
    int j=0;
    bool jdg=1;
    for(j=0;j<blen;j++)
    {
      if(s[i+j]!='?' && s[i+j]!=b[j])
      {  
        jdg=0;
        break;
      }
    }
    
    if(jdg) max=i;
  }
    if(max==-1){
      cout<<"UNRESTORABLE"<<endl;
  	  out=1;
    }
  if(out==0){
    int j=0;
    for(int i=0;i<blen;i++){
      s[max+i]=b[j];
      j++;
    }
  
  	for(int i=0;i<len;i++)
    {
      if(s[i]=='?') s[i]='a';
    }
    cout<<s<<endl;
  }
  }
}


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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define DEBUG_ARR(v,n) cout<<#v<<":";REP(i,n)cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) { a = b; return true; }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) { a = b; return true; }
    return false;
}
template<class T>
void DEBUG_DP(T* viewdp, int ilen, int jlen){
    REP(i,ilen){
        REP(j,jlen){
            if(viewdp[i][j] != -1)
                printf("[% 4d]", viewdp[i][j]);
            else
                printf("[    ]");
        }
        puts("");
    }
}

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

int h,w;
char mz[22][22];
int cnt[22][22];

int sx, sy;
int gx, gy;
queue<pii> que;
int mx;
int ans;

void solve(){
    mx = 0;

    while(!que.empty()){
        pii p = que.front();
        que.pop();

        //DEBUG2(p.first, p.second);

        REP(i,4){
            int ny = p.first + dy[i];
            int nx = p.second + dx[i];

            if(ny<0 || ny>=h || nx<0 || nx>=w) continue;
            if(cnt[ny][nx] != INT_MAX) continue;
            if(mz[ny][nx] == '#') continue;

            chmin(cnt[ny][nx], cnt[p.first][p.second]+1);
            if(chmax(mx, cnt[ny][nx])){
                sy = ny;
                sx = nx;
            }

            //DEBUG(cnt[ny][nx]);
            //DEBUG2(ny, nx);
            que.push(make_pair(ny,nx));
        }
    }
}


int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>h>>w;
    REP(i,h)REP(j,w) cin>>mz[i][j];

    //sx=0,sy=0;
    REP(i,22) fill(cnt[i],cnt[i]+22,INT_MAX);

    REP(i,h)REP(j,w){
        if(mz[i][j]=='.'){
            sy = i;
            sx = j;
            break;
        }
    }
    cnt[sy][sx]=0;
    
    que.push(make_pair(sy,sx));
    solve();
    //DEBUG_DP(cnt,h,w);

    //DEBUG2(sy,sx);
    REP(i,22) fill(cnt[i],cnt[i]+22,INT_MAX);
    cnt[sy][sx]=0;
    que.push(make_pair(sy,sx));
    solve();
    ans = mx;

    REP(i,22) fill(cnt[i],cnt[i]+22,INT_MAX);
    cnt[sy][sx]=0;
    que.push(make_pair(sy,sx));
    solve();
    
    chmax(ans,mx);

    //DEBUG_DP(cnt,h,w);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256