akhauriyash/Code-Regression huggingface dataset:
import java.util.*;

public class Main {
    public void main(Scanner sc) {
        int n = sc.nextInt();
        int m = sc.nextInt();
        int a[] = new int[n];
        long sum[] = new long[n + 1];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            sum[i + 1] = sum[i] + a[i];
        }

        Map<Integer, Long> map = new HashMap<>();
        for (int i = 0; i <= n; i++) {
            int mod = (int) (sum[i] % m);
            map.compute(mod, (k, v) -> (v == null) ? 1 : v + 1);
        }

        long ans = 0;
        for (Map.Entry<Integer, Long> entry : map.entrySet()) {
            long v = entry.getValue();
            if (v >= 2) {
                ans += v * (v - 1) / 2;
            }
        }
        System.out.println(ans);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        new Main().main(sc);
        sc.close();
    }
}


Measured memory_bytes: 60128
#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <functional>
#include <utility>
#include <cassert>
#include <algorithm>
#include <functional>
using namespace std;
int main(){
    int n;cin >> n;
    string s;
    cin >> s;
    vector<int> L(n);
    vector<int> R(n);
    if(s[0]=='W'){
        R[0]=1;
    }else{
        R[0]=0;
    }
    if(s[n-1]=='E'){
        L[n-1]=1;
    }else{
        L[n-1]=0;
    }
    for(int i=1;i<n-1;i++){
        if(s[i]=='W'){
            R[i]=R[i-1]+1;
        }else{
            R[i]=R[i-1];
        }
        if(s[n-i-1]=='E'){
            L[n-i-1]=L[n-i]+1;
        }else{
            L[n-i-1]=L[n-i];
        }
    }
    if(s[n-1]=='W') R[n-1]=R[n-2]+1;
    else R[n-1]=R[n-2];
    if(s[0]=='E') L[0]=L[1]+1;
    else L[0]=L[1];
    int res=1e9;
    for(int i=0;i<n;i++){
        int k= R[i]+L[i];
        k--;
      //  cout<<L[i]<<endl;
        res = min(res,k);
    }
    cout<<res<<endl;
}

Measured memory_bytes: 3076
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define bit(n) (1<<(n))
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1;} return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1;} return 0;}
int const INF = 1001001001;

ll dp[2020][2020];

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


int N;
cin >> N;
vl A(N);
rep(i,N) cin >> A[i];

vector<pll> P(N);
rep(i,N) {
    P[i] = {A[i],i};
}
sort(P.rbegin(), P.rend());


rep(i,N) {
    for(int x = 0; x <= i; x++) {
        chmax(dp[x+1][i-x], dp[x][i-x] + P[i].first * abs(P[i].second - x));
        chmax(dp[x][i-x+1], dp[x][i-x] + P[i].first * abs(P[i].second - N + 1 + i - x));
    }
}
ll ans = 0;
for(int x = 0; x <= N; x++) {
    chmax(ans, dp[x][N-x]);
}
cout << ans << endl;
return 0;
}


Measured memory_bytes: 26328
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0)
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cout << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#else
#define dbg(...)
#endif

int n;

// pair<int, int> fizzbuzz(int x) {
//     if (x % 3 == 0 && x % 5 == 0) {
//         return make_pair(1, 1);
//     }
// }

int main() {
    // int t;

    int n;
    cin >> n;
    LL sum = 0;
    for (int i=1; i<=n; ++i) {
        if (i % 3 && i % 5) {
            sum += i;
        }
    }
    cout << sum << endl;

    return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <functional>
#include <ctime>
using namespace std;
#pragma warning(disable: 4996)
string S;
int main() {
	cin >> S;
	for (int i = 0; i < 8; i++) {
		int C = (S[0] - '0');
		for (int j = 0; j < 3; j++) {
			if ((i / (1 << j)) % 2 == 0)C -= (S[j + 1] - '0');
			else C += (S[j + 1] - '0');
		}
		if (C == 7) {
			for (int j = 0; j < 3; j++) {
				cout << S[j];
				if ((i / (1 << j)) % 2 == 0)cout << "-";
				else cout << "+";
			}
			cout << S[3]; cout << "=7" << endl; break;
		}
	}
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

class Main{
  public static void main(String[] args){
   Scanner sc = new Scanner(System.in);
   int n = sc.nextInt();
   int money;
   if(n%1000 == 0){
    money = n;
   }else{
    money = ((n/1000)+1)*1000;
   }
   System.out.println(money-n);
  }
}



Measured memory_bytes: 35632
A, B, C, D = [int(e) for e in input()]
for b in [[+B, "+"+str(B)], [-B, "-"+str(B)]]:
  for c in [[+C, "+"+str(C)], [-C, "-"+str(C)]]:
    for d in [[+D, "+"+str(D)], [-D, "-"+str(D)]]:
      if A+b[0]+c[0]+d[0] == 7:
        ans = str(A) + b[1] + c[1] + d[1] + "=7"
        print(ans)
        break
    else:
      continue
    break
  else:
    continue
  break

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

int main() {
  int A, B;
  cin >> A >> B;
  if (A == B)
    cout << "Draw" << endl;
  else if (A == 1)
    cout << "Alice" << endl;
  else if (B == 1)
    cout << "Bob" << endl;
  else if (A > B)
    cout << "Alice" << endl;
  else
    cout << "Bob" << endl;
}


Measured memory_bytes: 256
n = int(input())
dicts = {}
for i in range(n):
    k = input()
    try:dicts[k] += 1
    except:dicts.setdefault(k, 1)
s = sorted(dicts.values(), reverse=True)
m = 0
for i in dicts:m = max(m, dicts[i])

ans = []
for i in dicts:
    if(dicts[i] == m):ans.append(i)

for i in sorted(ans):
    print(i)


Measured memory_bytes: 95704
#include <bits/stdc++.h>
#define INF (1<<30)
#define MOD 1000000007
#define l_ength size
using ll = long long;
using namespace std;

int main(){
	int n; ll m;
	cin >> n >> m;
	vector<pair<ll, ll>> maxi;
	for( int i = 0; i < n; ++i ){
		ll a, b; cin >> a >> b;
		maxi.emplace_back(a, b);
	}
	sort( maxi.begin(), maxi.end() );
	ll rq = m;
	ll ans = 0;
	for( int i = 0; i < n; ++i ){
		if( m <= maxi[i].second ){
			ans += maxi[i].first*m;
			break;
		} else {
			ans += maxi[i].first*maxi[i].second;
			m -= maxi[i].second;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 2420
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(ll i=(n)-1;i>=0;i--)
#define range(i,a,n) for(ll i=(a);i<(n);i++)
#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI (3.1415926535897932384)

int dx[]={1,0,-1,0,1,-1,-1,1},dy[]={0,1,0,-1,1,1,-1,-1};
template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S sum(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
int sgn(const double&r){return (r>EPS)-(r<-EPS);} // a>0  : sgn(a)>0
int sgn(const double&a,const double&b){return sgn(a-b);} // b<=c : sgn(b,c)<=0

template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>void tf(bool b,S t,T f){if(b)puta(t);else puta(f);}
void YN(bool b){tf(b,"YES","NO");}
void Yn(bool b){tf(b,"Yes","No");}
void yn(bool b){tf(b,"yes","no");}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1;for(auto s:t){os<<(a?"":" ")<<s;a=0;}return os;}
template<class S>auto&operator>>(istream&is,vector<S>&t){for(S&a:t)cin>>a;return is;}


int main(void){
  	cin.tie(0);
  	ios::sync_with_stdio(false);
  	
    string s;
    cin>>s;
    ll len=s.size();
    //puta(len);
    rep(i,len){
        string cs(s);
        cs.erase(i,len-7);
        if(cs=="keyence"){
            puta("YES");
            return 0;
        }
        //puta(cs);
    }
    if(s=="keyence"){
        puta("YES");
        return 0;
    }
    puta("NO");
    
}


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

vector<pair<char, int>> runLengthCompress(string s) {
    char ch;
    int num = 0;
    vector<pair<char, int>> v;
    for (int i = 0; i < s.size(); i++) {
        if (i == 0) {
            ch = s[i];
            num++;
            continue;
        }
        if (ch == s[i]) {
            num++;
            continue;
        } else {
            v.push_back(make_pair(ch, num));
            ch = s[i];
            num = 1;
        }
    }
    v.push_back(make_pair(ch, num));
    return v;
}

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

    string S;
    cin >> S;
    vector<pair<char, int>> v = runLengthCompress(S);

    int countR;
    bool flg = false;
    for (int i = 0; i < v.size(); i++) {
        if (v[i].first == 'R') {
            for (int j = 1; j <= v[i].second - 1; j++) {
                if (flg) cout << " ";
                cout << 0;
                flg = true;
            }
            countR = v[i].second;
        } else {
            int countL = v[i].second;
            if (flg) cout << " ";
            int r1 = (countR + 1) / 2, r2 = countL / 2;
            int l1 = countR / 2, l2 = (countL + 1) / 2;
            cout << r1 + r2 << " " << l1 + l2;
            flg = true;
            for (int j = 1; j <= v[i].second - 1; j++) {
                cout << " " << 0;
            }
        }
    }
    cout << endl;
    return 0;
}


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

int main() {
  string S;
  cin >> S;
  int ansA = 0;
  int ansB = 0;
  
  for(int i=0; i<S.size(); i++){
    if(S.at(i)=='0'){
    if(i%2==0)ansA ++;
    else ansB ++;
    }
    if(S.at(i)=='1'){
      if(i%2==1)ansA ++;
      else ansB ++;
    }
  }
  
  cout << min(ansA, ansB) << endl;
}


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

int32_t main(){
	int d; cin>>d;
	if(d == 25){
		puts("Christmas");
	}
	else if(d == 24){
		puts("Christmas Eve");
	}
	else if( d== 23){
		puts("Christmas Eve Eve");
	}
	else{
		puts("Christmas Eve Eve Eve");
	}
}


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

int main() {
	string s;
	cin >> s;
	for (int i = 0; i < s.length() - 1; i++) {
		if (s.at(i) == s.at(i + 1)) {
			cout << "Bad" << endl;
			return 0;
		}
	}
	cout << "Good" << endl;
}

Measured memory_bytes: 256
import sys
from collections import defaultdict

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()

n = ni()
dic = defaultdict(int)
for i in range(n):
    dic[ns()] += 1
for w in ("AC", "WA", "TLE", "RE"):
    print(f"{w} x {dic[w]}")


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


int main()
{
    int n, cnt = 0;
    scanf("%d", &n);
    int p[2*n];
    rep(i,n) cin >> p[i];
    rep(i,n-2){
        if(min(p[i],p[i+2])<p[i+1] && p[i+1]<max(p[i],p[i+2])) cnt++;
    }
    printf("%d\n", cnt);
}


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

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

    int A, B, T;

    cin >> A >> B >> T;

    cout << T / A * B; 
}

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

int main(void){
    char s[6];
    scanf("%s",s);
    for (int i=0; i<strlen(s)-1; i++){
        if (s[i]=='A' && s[i+1]=='C'){
            printf("Yes\n");
            exit(0);
        }
    }
    printf("No\n");
	return 0 ;
}

Measured memory_bytes: 128
#include <cstdio>
using namespace std;
int main() {
    int N; scanf("%d", &N);
    int cnt = 0; int c[9] = {0};
    for(int i = 0, a, t; i < N; ++i) {
        scanf("%d", &a);
        t = a/400; c[t<9?t:8]++;
    }
    for(int i = 0; i < 8; i++) {
        if(c[i] > 0) cnt++;
    }
    printf("%d %d", cnt>0?cnt:1, cnt+c[8]);
}

Measured memory_bytes: 128
def get_i() #空白区切の入力を数値(整数)の配列で返す
  return gets.chomp.split(" ").map(&:to_i)
end
def get_f() #空白区切の入力を数値(実数)の配列で返す
  return gets.chomp.split(" ").map(&:to_f)
end
def get() #空白区切の入力を文字列の配列で返す
  return gets.chomp.split(" ")
end
def get_nsp() #入力されたものを一文字ずつに区切った文字列の配列で返す
  return gets.chomp.split("")
end
def yn_judge(bool,y="Yes",n="No") #boolに真偽を投げることで、trueならy、falseならnの値を出力する
  return bool ? y : n 
end
def array(size1,init=nil,size2=-1) #size2に二次元配列時の最初の要素数、size1に次の配列の大きさ、initに初期値を投げることでその配列を返す
  if size2==-1
    return Array.new(size1){init}
  else
    return Array.new(size2){Array.new(size1){init}}
  end
end

def min(a,b)
    return a>b ? b : a
end
N,A,B=get_i
if (B-A).even?
    puts (B-A)/2
else
    puts min(min(N-A,B-1),min(A+(B-A-1)/2,N-B+1+(B-A-1)/2))
end

Measured memory_bytes: 1788
using namespace std;
#include <iostream>/*{{{*/
struct Fast {Fast(){std::cin.tie(0);ios::sync_with_stdio(false);}} fast;

#include <bits/stdc++.h>

#define rep(i, x) for(int i = 0; i < (int)(x); i++)
#define reps(i,x) for(int i = 1; i <= (int)(x); i++)
#define rrep(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define rreps(i,x) for(int i=((int)(x));i>0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define RFOR(i, m, n) for(int i = m;i >= n;i--)
#define foreach(x,a) for(auto& (x) : (a) )
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fill(x,y) memset(x,y,sizeof(x))
#define pb(a) push_back(a)
// dump macro{{{
// http://www.creativ.xyz/dump-cpp-652
#define DUMPOUT cerr // 変数ダンプ先。coutかcerr
 
#define DEBUG_ // 提出時はコメントアウト
#ifdef DEBUG_
#define DEB
#else
// DEB と打つとデバッグ時以外はコメントアウトになる
#define DEB /##/
#endif
 
// 変数ダンプ用マクロ。デバッグ時以外は消滅する
// 引数はいくつでもどんな型でも可（ストリーム出力演算子があればOK）
#define dump(...) DEB DUMPOUT<<"  "; \
DUMPOUT<<#__VA_ARGS__; \
DUMPOUT<<":=> "; \
dump_func(__VA_ARGS__); DUMPOUT<<"in ["<<__LINE__<<":"<<__FUNCTION__<<"]"<<endl;
 
// デバッグ用変数ダンプ関数
void dump_func() {
}
template <class Head, class... Tail>
void dump_func(Head&& head, Tail&&... tail)
{
    DUMPOUT << head;
    if (sizeof...(Tail) == 0) {
        DUMPOUT << " ";
    }
    else {
        DUMPOUT << ", ";
    }
    dump_func(std::move(tail)...);
}
 
// vector出力
template<typename T>
ostream& operator << (ostream& os, vector<T>& vec) {
    os << "{";
    for (int i = 0; i<vec.size(); i++) {
        os << vec[i] << (i + 1 == vec.size() ? "" : ", ");
    }
    os << "}";
    return os;
}/*}}}*/
#define debug(x)                 cerr << __LINE__ << ": " << #x << " -> " << x << '\n'
#define debug2(x, y)             cerr << __LINE__ << #x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define debug3(x, y, z)          cerr << __LINE__ << #x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define debug4(a, b, c, d)       cerr << __LINE__ << #a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define debug5(a, b, c, d, e)    cerr << __LINE__ << #a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define debug6(a, b, c, d, e, f) cerr << __LINE__ << #a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
#define db_2d(d,n,m) rep(i,n){rep(j,m){ cerr << (d)[i][j] << (((j)==(m-1))?"\n":" "); }}
#define db_1d(d,n) rep(i,n){cout << d[i] << (((i)==(n-1))?"\n":" ") << __LINE__}
#define INF 999999999
#define MOD 1000000007
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long long ll;
typedef vector<long long> vll;
typedef vector<vll> vvll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<vii> vvii;
typedef tuple<int,int,int> iii;
typedef set<int> si;
typedef complex<double> pnt;
typedef vector<pnt> vpnt;
typedef priority_queue<pii,vii,greater<pii> > spq;
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};/*}}}*/

int main() {
  ll a,b,x;
  cin >>a>>b>>x;

  cout << (b/x) - (a+x-1)/x + 1 << endl;
  return 0;
}


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

int main() {
	string s;
	while (getline(cin, s), s != "END OF INPUT") {
		string res;
		s += ' ';
		replace(s.begin(), s.end(), ' ', '+');
		stringstream ss(s);
		char c;
		int cnt = 0;
		while (ss >> c) {
			if (c == '+') {
				res += to_string(cnt);
				cnt = 0;
			}
			else cnt++;
		}
		cout << res << endl;
	}
}

Measured memory_bytes: 3260
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pairSS
#define int long long
#define MOD 1000000007
int gcd(int a,int b){
  if(a==0){
    return b;
  }
  return gcd(b%a,a);
}
int lcm(int a,int b){
  return a*b/gcd(a,b);
}
int keta(int a){
  int count = 0;
  while(a!=0){
    a = a/10;
    count++;
  }
  return count;
}
signed main(){
  int n;
  cin >> n;
  float v[n];
  rep(i,n){
    cin >> v[i];
  }
  sort(v,v+n);
  float ans = (v[0]+v[1])/2;
  rep(i,n-2){
    ans = (ans+v[i+2])/2;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
/***************************************************
 * Problem Name : B.cpp
 * Problem Link :
 * OJ           :
 * Verdict      : Trying
 * Date         : 2020-01-19
 * Problem Type :
 * Author Name  : Saikat Sharma
 * University   : CSE, MBSTU
 ***************************************************/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <cstdlib>
#include <deque>
#include <stack>
#include <bitset>
#include <cassert>
#include <map>
#include <set>
#include <cassert>
#include <iomanip>
#include <random>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;

#define __FastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define __FileRead freopen ("input.txt", "r", stdin)
#define __FileWrite freopen ("output.txt", "w", stdout)
#define SET(a,v) memset(a,v,sizeof(a))
#define SZ(v) (int)v.size()
#define pii pair<int,int>
#define pil pair <int, ll>
#define pli pair <ll, int>
#define pll pair <ll, ll>
#define debug cout <<"######\n"
#define debug1(x) cout <<"### " << x << " ###\n"
#define debug2(x,y) cout <<"# " << x <<" : "<< y <<" #\n"
#define nl cout << "\n";
#define sp cout << " ";
#define sl(n) scanf("%lld", &n)
#define sf(n) scanf("%lf", &n)
#define si(n) scanf("%d", &n)
#define ss(n) scanf("%s", n)
#define pf(n) scanf("%d", n)
#define pfl(n) scanf("%lld", n)
#define all(v) v.begin(), v.end()
#define rall(v) v.begin(), v.end()
#define srt(v) sort(v.begin(), v.end())
#define r_srt(v) sort(v.rbegin(), v.rend())
#define rev(v) reverse(v.begin(), v.end())
#define Sqr(x) ((x)*(x))
#define Mod(x, m) ((((x) % (m)) + (m)) % (m))
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define pb push_back
#define mk make_pair
#define MAX 100005
#define INF 1000000009
#define MOD 1000000007

template<class T>
using min_heap = priority_queue<T, std::vector<T>, std::greater<T>>;
template<typename T>
using ordered_set  = tree<T, null_type, less<T>, rb_tree_tag,
      tree_order_statistics_node_update>;

template <typename T> string toString ( T Number ) {
    stringstream ss;
    ss << Number;
    return ss.str();
}
template<typename T> int toInt (T str) {
    stringstream ss;
    ss << str;
    int num;
    ss >> num;
    return num;
}
ll lcm (ll a, ll b) {
    return a * b / __gcd (a, b);
}
/************************************ Code Start Here ******************************************************/
int main () {
    //~ __FastIO;
    //~ cout << setprecision (10);
    //~ cout << fixed;
    int a, b;
    cin >> a >> b;

    if (a > b) swap (a, b);

    for (int i = 0; i < b; i++) {
        cout << a;
    }

    nl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdlib>
#include<cstdio>
template<int BUFSIZE>
struct ans_buf {
  char buf[BUFSIZE];
  int i;
  ans_buf(): i(0) {}
  void putZ(unsigned int v, char delim='\n') {
    unsigned int k = 1;
    while(k <= v/10) k*=10;
    for(; k>0; v%=k, k/=10) buf[i++] = (v/k)+'0';
    buf[i++] = delim;
  }
  void out() { std::fwrite(buf, 1, i, stdout); }
};
char inbuf[1<<17];
unsigned int getZ() {
  unsigned int v = 0; int c;
  while((c = getchar_unlocked()) >= '0') v=v*10+c-'0';
  return v;
}

int const MAXN = 3e5;
int const MAXA = 6.4e5;
int N, m[MAXN], d[MAXN+1];

int main() {
  std::setbuf(stdin, inbuf);
  N = getZ();
 // std::fill_n(m, N, 0);
  for(int i = 0; i < N; ++i) ++m[getZ()-1];
  //std::fill_n(d, N+1, 0);
  for(int i = 0; i < N; ++i) ++d[m[i]];
 
  ans_buf<MAXA> buf;
  int sum_D = 0, sum_iD = N, k = 1;
  for(int ans = N; ans >= 1; --ans) {
    sum_D += d[ans];
    sum_iD -= d[ans]*ans;
    int next_k = sum_iD/ans + sum_D + 1;
    for(int i = k; i < next_k; ++i) buf.putZ(ans);
    k = next_k;
  }
  while(k <= N) { buf.putZ(0); ++k; }
  buf.out();
  return 0;
}


Measured memory_bytes: 2688
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		try {
			int sec = sc.nextInt();
			int hh = sec / 3600;
			int mm = sec % 3600 / 60;
			int ss = sec % 3600 % 60;
			System.out.println(hh + ":" + mm + ":" + ss);
		} finally {
			sc.close();
		}
	}
}

Measured memory_bytes: 26208
#include<stdio.h>
int main()
{
    char ch;
    scanf("%s", &ch);
    if((ch >= 'A') && (ch <= 'Z'))
    {
        printf("A");
    }
    else if((ch >= 'a') && (ch <= 'z'))
    {
        printf("a");
    }
    return 0;
}


Measured memory_bytes: 1612
/*-------enazuma11----------------*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define pll pair<long long,long long>
#define all(v) v.begin(),v.end()
#define inc(a,n) sort(a,a+n)
#define dec(a,n) sort(a,a+n,greater<int>() )
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repr(i,a,b) for(int i=a;i>b;i--)
#define F first
#define S second
#define M 1000000007
 
/* int x[]={-1,-1,0,1,1,1,0,-1};
int y[]={0,1,1,1,0,-1,-1,-1};
*/
/* int x[]={-1,0,1,0};
int y[]={0,1,0,-1};
*/
const int N=3e5+5;
vector<ll> g[N];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int t=1;
//	cin>>t;
	while(t--){
		ll n,k;
		cin>>n>>k;
		ll a[n];
		ll i,j;
		rep(i,0,n)
		{
			cin>>a[i];
		}
		ll dp[n];
		dp[0]=0;
		rep(i,1,n)
		{
			dp[i]=1e16;
			if(i==1)
			{
				dp[i]=abs(a[i]-a[i-1]);
			}else{
				for(int j=1;j<=k;j++)
				{
					if(i-j<0)
					break;
					dp[i]=min(dp[i],dp[i-j]+abs(a[i-j]-a[i]));
				}
			}
		}
		cout<<dp[n-1]<<'\n';
	}
	return 0;
}


Measured memory_bytes: 8832
N,M=list(map(int,input().split()))

flag_list = []
for i in range(M):
    l=list(map(int,input().split()))
    flag = [False for s in range(N)]
    for j in l[1:]:
        flag[j-1]=True
    flag_list.append(flag)

p=list(map(int,input().split()))

count = 0
for i in range(2**N):
    
    flg=True
    for k in range(M):
        parit=0
        val = i
        for j in range(N):
            decode=val%2
            if flag_list[k][j]:
                parit+=decode
            val = val//2
        if parit%2!=p[k]:
            flg=False
            break
    if flg:
        count+=1

print(count)
    

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

int gcd(int a,int b){
    int q;
    int r;
    int tmp;
    if(a<b){
        tmp = a;
        a =b;
        b =tmp;
    }
    r = a % b;
    if(r != 0){
        return gcd(b,r);
    }
    else if(r==0){
        return b;
    }
}
using namespace std;
int main(){
    int x,y;
    cin >> x >> y;
    cout << gcd(x,y) <<endl;
}



Measured memory_bytes: 3084
#define _USE_MATH_DEFINES
#include<bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=0;i<b;i++)
#define REP(i,a,b) for(int i=0;i<=b;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int>>
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define MEMSET(a) memset(a,0,sizeof(a))
#define inf (1ll<<60)
#define Yes(f) cout <<(f?"Yes":"No")<<endl//fが真の場合Yesを出力、偽の場合Noを出力
#define yes(f) cout <<(f?"yes":"no")<<endl
#define YES(f) cout <<(f?"YES":"NO")<<endl
#define SORT(v) sort(all(v))
#define RSORT(v) sort(all(v),greater<int>())

using namespace std;

const int mod=1e9+7;

signed main(){
    string s;
    cin >> s;
    vi k(4);

    rep(i,4)
    {
        switch(s[i])
        {
            case '0':
            k[i]=0;
                break;
            case '1':
k[i]=1;
                break;
            case '2':
k[i]=2;
                break;
            case '3':
k[i]=3;
                break;
                case '4':
k[i]=4;
                break;
                case '5':
k[i]=5;
                break;
                case '6':
k[i]=6;
                break;
                case '7':
k[i]=7;
                break;
                case '8':
k[i]=8;
                break;
                case '9':
k[i]=9;
                break;
        }
    }

    int ans=0b00;
    string a;
    int month=0;
    month+=k[0]*10+k[1];
    //MMYYの可能性がない場合
    if(month>12||month==0)ans+=0b10;
    month=0;
    month+=k[2]*10+k[3];
    //YYMMの可能性がない場合
    if(month>12||month==0)ans+=0b01;

    if(ans==0b00)a="AMBIGUOUS";
    if(ans==0b01)a="MMYY";
    if(ans==0b10)a="YYMM";
    if(ans==0b11)a="NA";

    cout << a << endl;
}


Measured memory_bytes: 256
import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue
import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    s = list(input())

    ans = []
    for i in range(2 ** (len(s) - 1)):
        tmp = [s[0]]
        for j in range(len(s) - 1):
            if (i >> j) & 1:
                tmp.append(s[j + 1])
            else:
                tmp[-1] += s[j + 1]

        tmp_ans = 0
        for ti in tmp:
            tmp_ans += int(ti)
        ans.append(tmp_ans)

    print(sum(ans))


if __name__ == '__main__':
    main()


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

#define REP(i, s, n) for (int i = s; i < n; ++i)
#define rep(i, n) REP(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG false

int main()
{
    vector<int> n(3);
    cin>>n[0]>>n[1]>>n[2];
    SORT(n);
    if(n[0]==5&&n[1]==5&&n[2]==7){
        cout<<"YES"<<endl;
    }else{
        cout<<"NO"<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
using System;

class Program {
    static void Main() {
        for (string line; !string.IsNullOrEmpty(line = Console.ReadLine());) {
            while (!line.Contains("the") && !line.Contains("this") && !line.Contains("that")) {
                line = Caesar(line);
            }

            Console.WriteLine(line);
         }
    }

    static string Caesar(string line) {
        var chars = line.ToCharArray();

        for (int i = 0, length = chars.Length; i < length; i++) {
            var ch = chars[i];

            if (ch >= 'a' && ch <= 'y') {
                chars[i] = (char)(ch + 1);
            }
            else if (ch == 'z') {
                chars[i] = 'a';
            }
        }

        return new string(chars);
    }
}

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

int main(){
    ll n, a, b;
    cin >> n >> a >> b;
    ll c = a + b;
    ll ans = a * (n / c);
    ans += min(n%c, a);
    cout << ans << endl;
}


Measured memory_bytes: 256
import itertools
import math

n = int(input())
x = []
num = []
for i in range(n):
  x.append([int(t) for t in input().split()])
  num.append(i)

s = 0
for i in itertools.permutations(num):
  i = list(i)
  #print(x,i)
  for j in range(n-1):
    s += math.sqrt((x[i[j]][0] - x[i[j+1]][0])**2 + (x[i[j]][1] - x[i[j+1]][1])**2)
    #print(s)
s /= math.factorial(n)
print(s)

Measured memory_bytes: 9036
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>

int N, K;

int main() {
	std::cin >> N >> K;
	int ans = 1;
	for (int i = 0; i < N; i++) {
		ans = std::min(ans * 2, ans + K);
	}
	std::cout << ans << std::endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FAST ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ALL(a) a.begin(), a.end()
#define RALL(a) a.rbegin(), a.rend()
#define pb push_back
#define MOD 1000000007
#define sz5 100005
#define sz6 1000005
#define UP upper_bound
#define LB lower_bound
#define F first
#define S second
#define PI pair<int,int>
#define PL pair<ll,ll>
#define VI vector<int>
#define VL vector<ll>
#define INF 1000000000000


int main() {
    FAST

    ll n,w,la,lb;
    cin>>n>>w;
    ll wt[n+4], v[n+4];
    for(la=1;la<=n;la++)
        cin>>wt[la]>>v[la];
    
    ll dp[n*1000+3][n+3];
    for(la=0;la<=n*1000;la++)
    for(lb=0;lb<=n;lb++)
        dp[la][lb]=INF;

    ll ans=0;
    for(la=0;la<=n;la++)
        dp[0][la]=0;
    for(la=1;la<=n*1000;la++){
        for(lb=1;lb<=n;lb++){
            dp[la][lb]=dp[la][lb-1];
            if(la>=v[lb]){
                dp[la][lb]=min(dp[la][lb], wt[lb]+dp[la-v[lb]][lb-1]);
            }
            if(dp[la][lb]<=w)
                ans=max(ans, la);
        }
    }

    // for(la=0;la<=18;la++){
    //     cout<<la<<": ";
    //     for(lb=0;lb<=n;lb++)
    //         cout<<dp[la][lb]<<' ';
    //     cout<<endl;
    // }

    cout<<ans<<endl;



    return 0;
}

Measured memory_bytes: 84072
#include <iostream>
using namespace std;

int main(void){
  int n, p[31] = {1, 1, 2};
  for(int i = 3; i <= 30; i++){
    p[i] = p[i-1] + p[i-2] + p[i-3];
  }
  while(true){
    cin >> n;
    if(n == 0) break;
    int y = (p[n] / 10 / 365);
    if(p[n] % 3650 != 0) y++;
    cout << y << endl;
  }
  return 0;
}

Measured memory_bytes: 1160
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <iomanip> // setprecision
#include <complex> // complex
#include <math.h> 
#include <climits> 
#include <assert.h>
#include <random>
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
constexpr ll INF = 1e18;
constexpr int inf = 1e9;
constexpr ll mod = 1'000'000'007;
constexpr ll mod2 = 998244353;
const double PI = 3.14159265358;
const int dx[8] = {1, 0, -1, 0,1,1,-1,-1};
const int dy[8] = {0, 1, 0, -1,1,-1,1,-1};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
// ---------------------------------------------------------------------------


int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll N,A,B,C,D;
  cin >> N >> A >> B >> C >> D;
  for(ll i=1; i<=N-1; i++){
    ll mn = A + i*C - (N-1-i)*D;
    ll mx = A + i*D - (N-1-i)*C;
    if(mn <= B && B <= mx){
      cout << "YES\n";
      return 0;
    }
  }
  cout << "NO\n";
  return 0;
}

Measured memory_bytes: 3628
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
pos,neg=[],0
if sum(a)<sum(b):print(-1);exit()
ne=0
for i in range(n):
    if a[i]==b[i]:continue
    if a[i]<b[i]:neg+=-a[i]+b[i];ne+=1
    else:pos.append(a[i]-b[i])
s=0
pos.sort(reverse=1)
ans=0


for i in pos:
    if s>=neg:print(ans+ne);exit()
    s+=i
    ans+=1

print(ans+ne)

Measured memory_bytes: 19060
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define REP(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)
#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)
#define EREP(i,a) for(int i=start[(a)];i;i=e[i].next)
inline int read()
{
	int sum=0,p=1;char ch=getchar();
	while(!(('0'<=ch && ch<='9') || ch=='-'))ch=getchar();
	if(ch=='-')p=-1,ch=getchar();
	while('0'<=ch && ch<='9')sum=sum*10+ch-48,ch=getchar();
	return sum*p;
}

const int maxn=1e5+20;
const ll inf=1ll<<60;

int n;
ll D[maxn];
int p[maxn];
int sa[maxn],sz[maxn];

map<ll,int>mp;

inline void init()
{
	n=read();
	REP(i,1,n)cin>>D[i],mp[D[i]]=i,sz[i]=1;
	D[0]=inf;
}

inline bool cmp(int a,int b){ return D[a]<D[b];} 

struct node {
	int v,next;
};
node e[maxn<<1];
int cnt,start[maxn];
inline void addedge(int u,int v){ e[++cnt]=(node){v,start[u]};start[u]=cnt;}

ll dist[maxn];

void dfs(int u,int fa)
{
	sz[u]=1;
	EREP(i,u)
	{
		int v=e[i].v;
		if(v==fa)continue;
		dfs(v,u);
		sz[u]+=sz[v];
		dist[u]+=dist[v]+sz[v];
		
	}
}

int l[maxn],r[maxn],tot;

inline void doing()
{
	REP(i,1,n)p[i]=i;
	sort(p+1,p+n+1,cmp);
	REP(i,1,n)sa[p[i]]=i;
	DREP(i,n,2)
	{
		int u=p[i];
		int x=mp[D[u]-n+2*sz[u]];
		if(!x)puts("-1"),exit(0);
		sz[x]+=sz[u];
		++tot;l[tot]=x;r[tot]=u;//printf("%d %d\n",x,u);
		addedge(x,u);
		addedge(u,x);
	}
	dfs(1,0);
	if(dist[1]!=D[1])puts("-1"),exit(0);
	REP(i,1,tot)printf("%d %d\n",l[i],r[i]);
}

int main()
{
	init();
	doing();
	return 0;
}



Measured memory_bytes: 17664
#include <stdio.h>

int main(void) {
	int a;
	int ans[3]={0,0,0};
	int i,j,k;
	int flag;
	
	for(i=0;i<10;i++){
		scanf("%d",&a);
		j=0;
		flag=0;
		while((flag==0)&&(j<3)){
			if(ans[j]<a){
				for(k=2;k>j;k--){
					ans[k]=ans[k-1];
				}
				ans[j]=a;
				flag=1;
			}
			j++;
		}
	}
	
	for(i=0;i<3;i++){
		printf("%d\n",ans[i]);
	}
	
	return 0;
}

Measured memory_bytes: 600
#include <iostream>
#include <vector>

using namespace std;
using int_vec = vector<int>;
using Iterator = int_vec::iterator;


Iterator partition(Iterator begin, Iterator end, int x) {
    for (auto it = begin; it != end; ++it) {
        if (*it <= x) {
            swap(*begin++, *it);
        }
    }
    return begin-1;
}


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

    int_vec v;
    for (auto i = 0; i < n; ++i) {
        int x;
        cin >> x;
        v.push_back(x);
    }

    auto mid = partition(v.begin(), v.end(), v.back());
    auto it = v.begin();
    for (; it != v.end()-1; ++it) {
        if (it == mid) {
            cout << "[" << *it << "]" << " ";
        } else {
            cout << *it << " ";
        }
    }
    cout << *it << endl;

    return 0;
}

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


int main(void) {
int N;
scanf("%d",&N);
int array[N];
int c=0;
int count=0;
int res[N];
for (int i=0;i<N;i++){
    scanf("%d",&array[i]);
    res[i]=i+1;
}
for (int i=0;i<N;i++){
    if (array[i]!=res[i]){
        count++;
    }
}
if (count<=2){printf("YES");}
else printf("NO");
return EXIT_SUCCESS;
}


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

int main() {
    int n, m, A, B;
    cin >> n >> m;
    vector<int> vec(n);
    vector<bool> vec2(n);

    for (int i = 0; i < n; i++){
        cin >> vec.at(i);
        vec2.at(i) = vec.at(i);
    }

    for (int i = 0; i < m; i++){
        cin >> A >> B;
        if(vec.at(A-1) > vec.at(B-1)){
            vec2[B-1] = false;
        } else if(vec.at(A-1) < vec.at(B-1)){
            vec2[A-1] = false;
        } else {
            vec2[A-1] = vec2[B-1] = false;
        }
    }

    int ans = 0;
    for (int i = 0; i < n; i++){
        if(vec2[i] == true){
            ans++;
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3796
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
inline int ri()
{
	register int x=0;register bool f=0;register char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=1;ch=getchar();}
	while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();};
	return f?-x:x;
}
void wi(int x)
{
	if(x<0)	x=-x,putchar('-');
	if(x>9)	wi(x/10);
	putchar('0'+x%10);
}
const int N=3*1e5+5;
char str[N];
int sume[N],sumw[N];
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	int n=ri(),i,ans=1e9;
	scanf("%s",str+1);
	for(i=1;i<=n;i++)	sumw[i]=sumw[i-1]+(str[i]=='W');
	for(i=n;i>=1;i--)	sume[i]=sume[i+1]+(str[i]=='E');
	for(i=1;i<=n;i++)	ans=min(ans,sumw[i-1]+sume[i+1]);
	wi(ans);putchar('\n');
	return 0;
}
/*
5
WEEWW


*/


Measured memory_bytes: 2944
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1000000009LL;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int main() {
    int n; cin >> n;
    int num = 0, res;
    for(int i=1; i<10000000; i++){
        num += i;
        if(num >= n){
            res = i;
            break;
        }
    }
    for(int i=res; i>0; i--){
        if(n <= 0) break;
        if(n-i>=0){
            cout << i << ln;
            n -= i;
        }
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
using P = pair<ll, ll>;
using mat = vector<vector<ll>>;

inline void IOS() { ios::sync_with_stdio(false), cin.tie(0); }

template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
	fill((T *)array, (T *)(array + N), val);
}

const ll INF = 1e16;
const ll MOD = 1e9 + 7;
//int dx[4] = {1,0,-1,0};
//int dy[4] = {0,1,0,-1};
//ll pas[5001][5002];

ll a[3002];
ll dp[3002][3002];
ll n;

ll rec(int i, int j, bool isT){
	if(dp[i][j] != INF)return dp[i][j];
	ll &tmp = dp[i][j];
	if(i == j)return dp[i][j] = (isT ? a[i] : -a[i]);
	if(isT)tmp = max(rec(i + 1, j, false) + a[i], rec(i, j - 1, false) + a[j]);
	else   tmp = min(rec(i + 1, j, true) - a[i], rec(i, j - 1, true) - a[j]);
	return tmp;
}

signed main(){
	IOS();
	cin >> n;
	Fill(dp, INF);
	for (int i = 1;i <= n;++i) {
		cin >> a[i];
	}
	ll ans = rec(1, n, true);
	cout << ans << endl;
	
}

Measured memory_bytes: 70912
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Text;
using System.Linq;
using static System.Math;

class Program
{
    static int N;
    static int K;
    static long[] a;

    static void Main()
    {
        /* 入力の受け取り */
        int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
        N = input[0];
        K = input[1];
        a = new long[N];
        for (int i = 0; i < N; i++)
            a[i] = long.Parse(Console.ReadLine());

        /* b[i] = a[i] - Kとシフト */
        long[] b = a.Select(s => s - K).ToArray();

        /* bの累積和 */
        long[] sum = new long[N + 1];
        for (int i = 0; i < N; i++)
            sum[i + 1] = sum[i] + b[i];

        Console.WriteLine(Calc(sum));
    }

    /* i < jについて、a[i] <= a[j]なる(i,j)の組数を求める */
    public static long Calc(long[] a)
    {
        int n = a.Length;
        SortedSet<long> s = new SortedSet<long>();
        foreach (var i in a) s.Add(i);
        long[] sorted_a = s.ToArray();
        RSQ1 rsq = new RSQ1(s.Count);
        long ans = 0;
        for (int j = 0; j < n; j++)
        {
            int i = Search(sorted_a, a[j]);
            ans += rsq.Query(0, i + 1);
            rsq[i] += 1;
        }
        return ans;
    }

    /* 昇順なarrayからsを二分探索で探し、indexを返す(複数あればそのうちの1つ) */
    public static int Search(long[] array, long s)
    {
        int l = 0;
        int r = array.Length - 1;
        while (l != r)
        {
            int m = l + (r - l) / 2;
            if (array[m] == s) return m;
            if (array[m] < s) l = m + 1;
            if (array[m] > s) r = m - 1;
        }
        return l;
    }
}

struct RSQ1
{
    private int n;
    private long[] dat;
    public int Length { get; private set; }
    public long this[int i]
    {
        get
        {
            if (i < 0 || i >= this.Length)
                throw new IndexOutOfRangeException();
            return dat[i + n - 1];
        }
        set { this.Update(i, value); }
    }

    /* nを要素数として、すべて0で初期化 */
    public RSQ1(int n)
    {
        Length = n;
        this.n = 1;
        while (this.n < n) this.n *= 2;
        dat = new long[2 * this.n];
    }

    /* k番目(0-indexed)をaに変更 */
    public void Update(int k, long a)
    {
        k += n - 1;
        dat[k] = a;
        while (k > 0)
        {
            k = (k - 1) / 2;
            dat[k] = dat[k * 2 + 1] + dat[k * 2 + 2];
        }
    }

    private long Query_(int a, int b, int k, int l, int r)
    {
        if (r <= a || b <= l) return 0;
        if (a <= l && r <= b) return dat[k];
        long v1 = Query_(a, b, k * 2 + 1, l, (l + r) / 2);
        long v2 = Query_(a, b, k * 2 + 2, (l + r) / 2, r);
        return v1 + v2;
    }

    /* [a,b)の和を求める */
    public long Query(int a, int b)
    {
        return Query_(a, b, 0, 0, n);
    }
}

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

using namespace std;
typedef long long ll;

int main(){
  string S;
  cin >>S;
  int n=S.size()-1;
  ll ans=0;
  for(int i=0;i<(1<<n);++i){
    ll a=S[0]-'0';
    ll b=0;
    for (int j=0;j<n;++j){
      if (i&(1<<j)){
        b+=a;
        a=S[j+1]-'0';
      }else{
        a=a*10+S[j+1]-'0';
      }
    }
    b+=a;
    ans+=b;
  }
  cout <<ans<<endl;
}


Measured memory_bytes: 256
#include <stdio.h>
int main (void){
int a,b,i,j;
int A;
scanf("%d%d",&a,&b);
int c[a];
for(i=0;i<a;i++){
scanf("%d",&c[i]);
}
for(i=0;i<a-1;i++){
for(j=i+1;j<a;j++){
if(c[i]>c[j]){
A=c[i];
c[i]=c[j];
c[j]=A;
}}
A=0;
}
for(i=0;i<b;i++){A+=c[i];}
printf("%d",A);
return 0;
}

Measured memory_bytes: 1736
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
#%%code

def resolve():
    N=input()
    n=len(N)
    N=int(N)
    ans=set()
    numans=0
    stack=[(3,1),(5,2),(7,4)]
    row=(3,5,7)
    while (stack!=[]):
        t,u=stack.pop()
        for n,l in enumerate(row):
            neu=(t*10+l,u|(2**n))
            if neu[0]<=N:
                stack.append(neu)
                if neu[1]==7:
                    ans.add(neu[0])
    print(len(ans))
#%%submit!
resolve()

Measured memory_bytes: 42608
import numpy as np

n, k = map(int, input().split())
List = [list(map(int, input().split())) for i in range(2*k)]

ans=np.zeros(n)
n=np.array(List[1])

for i in range(1,2*k,2):
  for j in List[i]:
    ans[j-1]=ans[j-1]+1

print(np.count_nonzero(ans==0))

Measured memory_bytes: 27132
#include<bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n ; i++)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define whole(f, x, ...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x) // decltypeで型取得、引数があればva_argsのところに入れる
using namespace std;
typedef long long ll; // long longをllでかけるようにした
const int INF = 1e9;

int main(void){
    int h, n; cin >> h >> n;
    vector<int> dp(h + 1, INF);
    dp[0] = 0;
    REP(i, n){
        int a, b; cin >> a >> b;
        REP(j, h){
            int nj = min(j + a, h);
            dp[nj] = min(dp[nj], dp[j] + b);
        }
    }
    cout << dp[h] << endl;
}

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

using namespace std;

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

int main() {
  int N, X;
  cin >> N >> X;
  vector<int> x(N);
  for (int i = 0; i < N; ++i) cin >> x[i];
  sort(x.begin(), x.end());
  int ans = abs(x[0] - X);
  for (int i = 0; i < N - 1; ++i) {
    ans = gcd(ans, x[i + 1] - x[i]);
    ans = gcd(ans, abs(x[i + 1] - X));
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <functional>
#include <string>
#include <queue>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <random>
#include <unordered_map>
#include <unordered_set>
#define ll long long
#define fr(i,k,N) for(ll i=k; i<N;i++)
#define rep(i,N) for(ll i=0; i<N;i++)
#define alll(v) v.begin(),v.end()
using namespace std;
template <class X> void pr(X test){cout<<test<<endl;}
template <class X> void prr(X test){for(auto it:test){cout<<it<<endl;}cout<<endl;}
vector<ll> divv(ll n);

int main() {
    ll n,k;
    string s;
    cin>>s;
    int yy = (s[0] - '0')*10 + (s[1]-'0');
    int mm = (s[2] - '0')*10 + (s[3]-'0');
    bool a = false,b=false;
    if(1<=yy && yy<=12) a=true;
    if(1<=mm && mm<=12) b=true;

    if(a && b) pr("AMBIGUOUS");
    else if(a) pr("MMYY");
    else if(b) pr("YYMM");
    else pr("NA");
    return 0;
}

// return sorted 約数s 1 <= x <= n
vector<ll> divv(ll n) {
  vector<ll> v;
  for(ll i = 1; i*i <= n; i++) {
    if(n%i == 0) {
      v.push_back(i);
      if(i*i != n) v.push_back(n/i);
    }
  }
  sort(alll(v));
  return v;
}

class UF { // union find from https://github.com/kartikkukreja/blog-codes (MIT)
    // [usage]
    // auto uf = new UF(n);
    // uf->merge(a, b);
    // ...
public:
    int *id; // inner id
    int cnt; // number of all vartices
    int *sz; // sz[i] means size of i's set
    UF(int N)   {
        cnt = N;
        id = new int[N];
        sz = new int[N];
        for(int i=0; i<N; i++) {
            id[i] = i;
            sz[i] = 1;
        }
    }
    ~UF() {
        delete [] id;
        delete [] sz;
    }
    int find(int p) {
        int root = p;
        while (root != id[root]) root = id[root];
        while (p != root) {
            int newp = id[p];
            id[p] = root;
            p = newp;
        }
        return root;
    }
    void merge(int x, int y) {
        int i = find(x);
        int j = find(y);
        if (i == j) return;
        
        if (sz[i] < sz[j]) {
            id[i] = j;
            sz[j] += sz[i];
        } else {
            id[j] = i;
            sz[i] += sz[j];
        }
        cnt--;
    }
    bool connected(int x, int y) {
        return find(x) == find(y);
    }
    int count() {
        return cnt;
    }
};

Measured memory_bytes: 888