akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <unordered_set>
#include <unordered_map>
#include <iomanip>
//#pragma GCC optimize("Ofast")
//#define _GLIBCXX_DEBUG
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
//#define int ll
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define irep(it, stl) for(auto it = stl.begin(); it != stl.end(); it++)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout << (ans) << '\n'
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define floatprec(dig) fixed << setprecision(dig)
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define itn int;
#define invar(typ, var) typ var; cin >> var;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
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;}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);}};
const int INF = INT_MAX / 2;
const ll LLINF = 1LL<<60;
constexpr ll MOD = 1000000007;
const double EPS = 1e-9;

signed main(void) {
  cin.tie(0); ios::sync_with_stdio(false);
  
  int L;
  cin >> L;
  
  //Nは頂点数
  //2^(N-2) 長の辺まで作る
  int N = 0;
  while((1<<N) <= L) N++;
  
  vvi edges;
  for(int i=1; i<N; i++) {
    //二進数の辺
    edges.push_back({i, i+1, 1<<(i-1)});
    edges.push_back({i, i+1, 0});
  }
  
  //現在の辺長の最大
  int now = (1<<(N-1)) - 1;
  for(int i=N-1; i>=1; i--) {
    int gain = (1<<(i-1));
    if(gain + now <= L-1) {
      edges.push_back({i, N, now + 1});
      now += gain;
    }
  }
  
  cout << N << " " << edges.size() << endl;
  
  for(int i=0; i<edges.size(); i++) {
    cout << edges[i][0] << " " << edges[i][1] << " " << edges[i][2] << endl;
  }
}

Measured memory_bytes: 256
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
//by NeighThorn
using namespace std;
const int maxn=10000+5;
int n,hd[maxn],to[maxn*2],nxt[maxn*2],w[maxn*2],cnt,maxdis[maxn],secdis[maxn];
inline void add(int s,int x,int y){
    w[cnt]=s;to[cnt]=y;nxt[cnt]=hd[x];hd[x]=cnt++;
}
inline void dfs(int root,int fa){
    for(int i=hd[root];i!=-1;i=nxt[i])
        if(to[i]!=fa){
            dfs(to[i],root);
            if(maxdis[to[i]]+w[i]>maxdis[root])
                secdis[root]=maxdis[root],maxdis[root]=maxdis[to[i]]+w[i];
            else if(maxdis[to[i]]+w[i]>secdis[root])
                secdis[root]=maxdis[to[i]]+w[i];
        }
}
inline void change(int root,int fa){
    for(int i=hd[root];i!=-1;i=nxt[i])
        if(to[i]!=fa){
            if(maxdis[root]==maxdis[to[i]]+w[i]){
                if(maxdis[to[i]]<secdis[root]+w[i])
                    secdis[to[i]]=maxdis[to[i]],maxdis[to[i]]=secdis[root]+w[i];
                else if(secdis[to[i]]<secdis[root]+w[i])
                    secdis[to[i]]=secdis[root]+w[i];
            }
            else{
                if(maxdis[to[i]]<maxdis[root]+w[i])
                    secdis[to[i]]=maxdis[to[i]],maxdis[to[i]]=maxdis[root]+w[i];
                else if(secdis[root]<secdis[root]+w[i])
                    secdis[to[i]]=maxdis[root]+w[i];
            }
            change(to[i],root);
        }
}
signed main(void){
    scanf("%d",&n);cnt=0;memset(hd,-1,sizeof(hd));
    for(int i=1,s,x,y;i<n;i++)
        scanf("%d%d%d",&x,&y,&s),add(s,x,y),add(s,y,x);
    memset(maxdis,0,sizeof(maxdis));memset(secdis,0,sizeof(secdis));
    dfs(0,-1);change(0,-1);
    for(int i=0;i<n;i++)
        printf("%d\n",maxdis[i]);
    return 0;   
}


Measured memory_bytes: 3792
mod = 10**9 + 7
N, M = map(int, input().split())


a = [True] * (N+1)
for _ in range(M):
    a[int(input())] = False


dp = [0] * (N+1)
dp[0] = 1
for i in range(N+1):
    for j in range(1, 3):
        if (i+j) > N or a[i+j] == False:
            continue
        dp[i+j] += dp[i]
        dp[i+j] %= mod

print(dp[N])


Measured memory_bytes: 7668
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)n;i++)
using Graph = vector<vector<int> >;
using GraphC = vector<vector<char> >;
typedef pair<int, int> P;
typedef int64_t ll;
const int MAX_N = 10000;
const int INF = 1000000000;


int main() {
	int N;
	cin >> N;
	vector<int> A(N);
	rep(i, N) {
		int tmp;
		cin >> tmp;
		tmp--;
		A.at(tmp) = i + 1;
	}
	rep(i, N) {
		cout << A.at(i) << " ";
	}
	return 0;
}

Measured memory_bytes: 3788
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>


using namespace std;


void security()
{
  string s;
  cin >> s;

  for (int i = 1; i < s.size(); ++i)
  {
    if (s[i - 1] == s[i])
    {
      cout << "Bad\n";
      return;
    }
  }
  cout << "Good\n";
}


void fifty_fify()
{
  string s;
  cin >> s;

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

  if (s[0] == s[1] && s[1] != s[2] && s[2] == s[3]) cout << "Yes\n";
  else cout << "No\n";
}


void dodecagon()
{
  int r;
  cin >> r;

  cout << 3 * r * r << "\n";
}


void harmony()
{
  int a, b;
  cin >> a >> b;

  if (a % 2 == b % 2) cout << (a + b) / 2 << "\n";
  else cout << "IMPOSSIBLE\n";
}


void transfer()
{
  int a, b, c;
  cin >> a >> b >> c;

  cout << max(0, c - (a - b)) << "\n";
}


void A_137()
{
  int a, b;
  cin >> a >> b;

  cout << max(a + b, max(a - b, a * b)) << "\n";
}


void red_or_not()
{
  int a;
  cin >> a;
  string s;
  cin >> s;

  if (a >= 3200) cout << s << "\n";
  else cout << "red\n";
}


void tenki()
{
  string s, t;
  cin >> s >> t;

  int cnt = 0;
  for (int i = 0; i < 3; ++i)
  {
    if (s[i] == t[i]) ++cnt;
  }
  cout << cnt << "\n";
}


void password()
{
  int n;
  cin >> n;

  cout << pow(n, 3) << "\n";
}


void uneven_numbers()
{
  int n;
  cin >> n;

  int ans = 0;
  for (int i = 1; i <= n; ++i)
  {
    string s = to_string(i);
    if (s.size() % 2 == 1) ++ans;
  }
  cout << ans << "\n";
}


void one_clue()
{
  int k, x;
  cin >> k >> x;

  for (int i = x - k + 1; i < x + k; ++i)
  {
    if (i == x + k - 1) cout << i << "\n";
    else cout << i << " ";
  }
}



void resistors_in_parallel()
{
  int n;
  cin >> n;
  vector<float> a(n);
  for (int i = 0; i < n; ++i) cin >> a[i];

  float ans = 0.0;
  for (int i = 0; i < n; ++i) ans += 1.0 / a[i];
  cout << 1.0 / ans << "\n";
}


void power_socket()
{
  int a, b;
  cin >> a >> b;

  if (b == 1) cout << 0 << "\n";

  int cnt = 1, tap = (a - 1) * cnt + 1;
  while (tap < b)
  {
    ++cnt;
    tap += a - 1;
  }
  
  cout << cnt << "\n";
}


void buffet()
{
  int n;
  cin >> n;
  vector<int> a(n), b(n), c(n - 1);
  for (int i = 0; i < n; ++i) cin >> a[i];
  for (int i = 0; i < n; ++i) cin >> b[i];
  for (int i = 0; i < n - 1; ++i) cin >> c[i];

  int ans = 0;
  for (int i = 0; i < n; ++i)
  {
    ans += b[a[i] - 1];
    if (i > 0 && a[i - 1] + 1 == a[i]) ans += c[a[i - 1] - 1];
  }
  cout << ans << "\n";
}




int main()
{
  //security();
  //fifty_fify();
  //dodecagon();
  //harmony();
  //transfer();
  //A_137();
  //red_or_not();
  //tenki();
  //password();



  uneven_numbers();
  //one_clue();
  //resistors_in_parallel();
  //power_socket();
  //buffet();
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long mod = 1e9 + 7;
vector<long long>fact(1e6 + 20);
long long bigmod(long long a, long long p){
    if(p == 0){
        return 1;
    }
    long long ans = bigmod(a, p/2);
    ans = (ans * ans) % mod;
    if(p % 2 == 1){
        ans = (ans * a) % mod;
    }
    return ans;
}
long long nCr(long long n, long long m){
    long long cur = (fact[m] * fact[n - m]) % mod;
    cur = bigmod(cur, mod - 2);
    cur = (cur * fact[n]) % mod;
    return cur;
}
int main(){
    fact[0] = 1;
    for(long long i = 1; i <= 1000000; i++){
        fact[i] = (fact[i - 1] * i) % mod;
    }
    int n;
    cin >> n;
    long long ans = 0;
    for(int i = 1; i <= n; i++){
        long long cur = nCr(n, i);
        cur = (cur * bigmod(8, n - i)) % mod;
        ans = (ans + cur) % mod;
    }
    cout << (bigmod(10, n) - bigmod(8, n) - 2 * ans + 7 * mod) % mod;
    return 0;
}

Measured memory_bytes: 11024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  int a, b;
  string s, t, u;
  cin>>s>>t>>a>>b>>u;
  if(s == u)a--;
  if(t == u)b--;
  cout<<a<<" "<<b<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <utility>
#include <functional>
#include <bitset>

using namespace std;
using lli = long long int;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0) 
{ v = vector<T>(n+o); for (lli i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> void read_n(T a[], size_t n, size_t o = 0)
{ for (lli i=o; i<n+o; ++i) cin >> a[i]; }
template<class T> T gabs(const T& x) { return max(x, -x); }
#define abs gabs

lli n, q;
string s;
int main() {
  cin >> n >> q >> s;
  vector<lli> a(n);
  for (lli i=1; i<n; ++i) {
    a[i] = a[i-1];
    if (s[i-1]=='A' && s[i] == 'C') a[i]++;
  }
  for (lli i=0; i<q; ++i) {
    lli l, r; cin >> l >> r;
    cout << a[r-1] - a[l-1] << endl;
  }
  return 0;
}


Measured memory_bytes: 1792
//include
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath> 
#include <iomanip>
#include <math.h>
#include <utility>
#include <functional>
#include <cstdlib>
//using
using namespace std;
using vl = vector <long long>;
using vs = vector <string>;
using vc = vector <char>;
using ll= long long;
using vvl = vector<vector<ll> >;
using vvc = vector<vector<char> >;
//vector<vector<char> > hyou(N, vector<char>(N));
using vd = vector <double>;
//define
//#define int long long
#define rep(i,n) for(int i=0; i<n; i++)
#define print(n) cout<<n<<endl;
#define sortp(d) sort(d.begin(),d.end()) //1234
#define sortm(d) sort(d.rbegin(),d.rend()) //4321
//素数判定　O(√A) 
bool is_prime(int x){
 if(x<=1) return false;
 for(int i=2;i*i<=x;i++)
 if(x%i==0) return false;
 return true;
 }
/*順列生成
do {
  // 順列に対する処理
} while (next_permutation(配列変数.begin(), 配列変数.end()));*/

//絶対値　abs()
//文字→数字　'0' アルファベット→数字　'a'　'A'が65番,'a'が97番だわ
//型キャスト　char('a'+1)
//reverse 回文
//if(isupper('A')){puts("Aは大文字です");}

//各位の和　
int wa(ll x)
{
ll sum = 0;
while(x!=0){
  sum += x% 10;
  x /= 10;
}
return sum;
}


//グローバル変数宣言
ll p=0,q=0,y=0;

int main()
{
  ll a,b;
  cin>>a>>b;
  rep(i,1010)
  {
    p=i*0.08;q=i*0.1;
    if (a==p&&q==b)
    {
      print(i);return 0;
    }
  }
  print(-1)
  
}


Measured memory_bytes: 3648
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string.h>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <vector>
#include <array>
#include <list>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

#define SZ 100001

#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;

map<pair<int, int>, int> square;
int H, W, N, a, b;
ll allSquare;
int res[10] = { 0, };
int r[9] = { 1, 1, 1, 0, 0, 0, -1, -1, -1 };
int c[9] = { 1, 0, -1, 1, 0, -1, 1, 0, -1 };

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

	cin >> H >> W >> N;
	for (int i = 0; i < N; ++i) {
		cin >> a >> b;
		for (int j = 0; j < 9; ++j) {
			int na = a + r[j];
			int nb = b + c[j];
			if (na <= 1 || nb <= 1 || na >= H || nb >= W) continue;
			square[{na, nb}]++;
		}
	}

	for (auto center : square) {
		res[center.second]++;
	}
	allSquare = (H - 2)*(W * 1LL - 2) - square.size();
	cout << allSquare << '\n';
	for (int i = 1; i <= 9; ++i) {
		cout << res[i] << '\n';
	}

}

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

struct Process {
  string name;
  int time;
};

int const MAX = 1000000;
int head;
int tail;
Process Q[MAX];

void initalize() {
  head = tail = 0;
}

bool isEmpty() {
  return head == tail;
}

bool isFull() {
  return head == (tail + 1) % MAX;
}

void enqueue(Process x) {
  if (isFull()) {
    cout << "エラー(オーバーフロー)" << endl;
    return;
  }
  Q[tail] = x;
  if (head + 1 == MAX) {
    head = 0;
  } else {
    tail++;
  }
}

Process denqueue() {
  if (isEmpty()) {
    cout << "エラー(アンダーフロー)" << endl;
  }
  Process x = Q[head];
  if (head + 1 == MAX) {
    head = 0;
  } else {
    head++;
  }
  return x;
}

int main() {
  int n, q;
  cin >> n >> q;
  for (int i = 0; i < n; ++i) {
    string name;
    int time;
    cin >> name >> time;
    enqueue(Process {name, time});
  }
  int elapsed_time = 0;
  while (!isEmpty()) {
    Process p = denqueue();
    if (p.time > q) {
      elapsed_time += q;
      p.time -= q;
      enqueue(p);
    } else {
      elapsed_time += p.time;
      cout << p.name << " " << elapsed_time << endl;
    }
  }
}



Measured memory_bytes: 20968
#include <bits/stdc++.h>
using namespace std;
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <algorithm>
int main() {
  long a,b,c,i,k,ans;
  cin>>a>>b>>c>>k;
 if(k%2==0){
 cout<<a-b<<endl;
 }else{
 cout<<b-a<<endl;
 }
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <map>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <set>
#include <stack>
#include <stack>
#include <list>
#include <algorithm>
#include <numeric>
#include <utility>
#include <complex>
#include <functional>

#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(){
    
    string S;
    getline(cin,S);
    rep(i, S.size()){
        if(S[i] >= 'a' && S[i] <= 'z') S[i] += 'A' - 'a';
        else if(S[i] >= 'A' && S[i] <= 'Z') S[i] += 'a' - 'A';
    }
    cout << S << endl;

    return 0;
}



Measured memory_bytes: 3208
import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		String s = scan.next();
		if(!kai(s)) {
			System.out.println("No");
			return;
		}

		if(kai(s.substring(0, (s.length() - 1) / 2))
			&& kai(s.substring((s.length() + 3) / 2 - 1, s.length()))) {
			System.out.println("Yes");
			return;
		}
		System.out.println("No");
	}
	public static boolean kai(String s) {
		int i;
		int loopCnt = (s.length() - 1) / 2;
		int length = s.length();
		if(length % 2 == 0)
			loopCnt = length / 2;

		boolean res = true;
		for(i = 0; i < loopCnt; i++) {
			if(!s.substring(i, i + 1).equals(s.substring(length - i - 1, length - i))) {
				res = false;
				break;
			}
		}
		return res;
	}
}

Measured memory_bytes: 22100
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define pll pair < ll , ll >
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define ld long double
#define endl "\n"
using namespace std;
using namespace __gnu_pbds;
ll M = 1e9 + 7;

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

int main()
{

    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin >> m >> n;
    for( int i = 0; i < n; i++)
    {
        int b;
        cin >> b;
        m-=b;
    }
    cout << max(-1,m);
}


Measured memory_bytes: 3656
#102B maximum difference
s=[[int(j) for j in input().split()] for i in range(2)]
N=s[0][0]
A=s[1]
max=0
for i in range(len(A)):
    for j in range(i,len(A)-1):
        result=A[i]-A[j+1]
        if result<0:result=result*-1
        if result>max:max=result
print(max)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long n;
    cin >> n;
    long long sum = 0;

    for (long long i = 1; i <= n; i++)
    {
        if(i%3 == 0 or i%5==0)
            continue;
        sum += i;
    }

    cout << sum << endl;
}

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

#define pb push_back
#define mp make_pair
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

bool chkmax(int &x,int y){return x<y?x=y,true:false;}
bool chkmin(int &x,int y){return x>y?x=y,true:false;}

int readint(){
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

int n,l;
int a[100005];

int main(){
	n=readint(); l=readint();
	for(int i=1;i<=n;i++) a[i]=readint();
	int opt=0;
	for(int i=1;i<n;i++) if(a[i]+a[i+1]>=l) opt=i;
	if(!opt) return printf("Impossible\n"),0;
	printf("Possible\n");
	for(int i=1;i<opt;i++) printf("%d\n",i);
	for(int i=n-1;i>opt;i--) printf("%d\n",i);
	printf("%d\n",opt);
	return 0;
}

Measured memory_bytes: 1152
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int INF = 1e9+7;
vector<ll> adj[1111111];
ll cnt = 0;
bool vis[1111111] = {false};
void dfs(ll src){
	vis[src] = true;
	++cnt;
	for(auto node:adj[src]){
		if(!vis[node]){
			dfs(node);
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	ll n,m;
	cin>>n>>m;
	set<ll> ss;
	map<pair<ll,ll>,ll> mp;
	for(int i=0;i<m;++i){
		ll u,v;
		cin>>u>>v;
		ss.insert(u);
		ss.insert(v);
		if(!mp[{u,v}]){
			adj[u].push_back(v);
			adj[v].push_back(u);
			++mp[{u,v}];
			++mp[{v,u}];
		}
	}
	if(m==0){
		cout<<1<<'\n';
		return 0;
	}
	vector<ll> an;
	for(auto i:ss){
		if(!vis[i]){
			cnt = 0;
			dfs(i);
			an.push_back(cnt);
		}
	}
	sort(an.begin(),an.end());
	ll ans = an[0];
	ll mx = an[0];
	for(int i=1;i<(int)an.size();++i){
		ans += (an[i]-mx);
		mx = max(mx,an[i]);
	}
	cout<<ans<<'\n';
	return 0;
}

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

int main() {
    int a[15];
    for (int i = 0; i < 10; i++) cin >> a[i];
    sort(a, a + 10, greater<int>());

    for (int i = 0; i < 3; i++) cout << a[i] << endl;

    return 0;
}


Measured memory_bytes: 3160
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        long b = sc.nextLong();
        long x = sc.nextLong();
        
        a--;
        
        long tmp = a / x;
        long tmp2 = b / x;
        
        if (a != -1) {
            System.out.println(tmp2 - tmp);
        } else {
            tmp2++;
            System.out.println(tmp2);
        }
    }
}

Measured memory_bytes: 22996
n,y=io.read("*n","*n")
y=y//1000
for a=0,n do
    b=((y-10*a)-(n-a))//4
    c=n-a-b
    if b>=0 and c>=0 and 10*a+5*b+c==y then
        print(a,b,c)
        return
    end
end
print(-1,-1,-1)

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

using namespace std;

typedef long long LL;
typedef pair<int,int> pi;
typedef vector<int> vi;
#define ST first
#define ND second
#define PB push_back
#define DET(a,b,c) (LL(b.x-a.x)*LL((c.y-a.y))-LL((c.x-a.x))*LL((b.y-a.y)))

const int MAXN = 200*1000+10;
const LL INF = (LL)1000*1000*1000*1000*1000*1000;
int n,m,R,log2n;
vector<pi>events[MAXN];
LL q[MAXN];
LL totals;
LL res=0;

struct Node {
    LL f,g;
};

Node T[(1<<20)];

void propagate(int x) {
    T[2*x].g+=T[x].g;
    T[2*x+1].g+=T[x].g;
    T[x].g=0;
}

void updateTf(int a) {
    while(a>1) {
        a/=2;
        T[a].f = min(T[2*a].f+T[2*a].g,T[2*a+1].f+T[2*a+1].g);
    }
}

void update(int a,int b, LL c) {
    a+=R; b+=R;
    for(int i=log2n; i>0;i--) {
        propagate(a/(1<<i));
        propagate(b/(1<<i));
    }
    int pa=a,pb=b;
    T[a].g+=c;
    if(a!=b) T[b].g+=c;
    while(a/2!=b/2) {
        if(a%2==0) T[a+1].g+=c;
        if(b%2==1) T[b-1].g+=c;
        a/=2;
        b/=2;
    }
    updateTf(pa); updateTf(pb);
}

LL query(int a,int b) {
    a+=R; b+=R;
    for(int i=log2n; i>0;i--) {
        propagate(a/(1<<i));
        propagate(b/(1<<i));
    }
    updateTf(a); updateTf(b);
    LL w = min(T[a].f+T[a].g,T[b].f+T[b].g);
    while(a/2!=b/2) {
        if(a%2==0) w=min(w,T[a+1].f+T[a+1].g);
        if(b%2==1) w=min(w,T[b-1].f+T[b-1].g);
        a/=2;
        b/=2;
    }
    return w;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    for(int i=0; i<m;i++) {
        int l,r,c;
        cin>>l>>r>>c;
        events[r].emplace_back(l,c);
        q[l]+=c;
    }
    int pom=1;
    while(pom<=n) {
        log2n++;
        pom*=2;
    }
    R = pom;
    for(int i=1; i<=n;i++) {
        for(auto p:events[i-1]) {
            update(0,p.ST-1,p.ND);
        }
        totals+=q[i];
        LL tmp = query(0,i-1);
        //cout<<totals<<" "<<tmp<<"\n";
        res=max(res,totals-tmp);
        update(i,i,tmp);
    }
    cout<<res;
}


Measured memory_bytes: 20480
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define N 100005
#define MOD 1000000007
#define dd double
#define vi vector<int>
#define vll vector<ll>
#define forr(i,n) for(ll i=0;i<n;i++)
#define revf(i,n) for(ll i=n-1;i>=0;i--)
#define REP(i,a,b) for(ll i=a;i<b;i++)
#define rep1(i,b) for(ll i=1;i<=b;i++)
#define inp(a,n) for(ll i=0;i<n;i++)cin>>a[i]
#define outp(a,n) for(ll i=0;i<n;i++)cout<<a[i]<<" "
#define outp1(a,n) for(ll i=1;i<n;i++)cout<<a[i]<<" "
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) (((a)*(b))/gcd((a),(b)))
#define pb push_back
#define mp make_pair
#define mem(x,n) memset(x,n,sizeof(x))
#define BINSC binary_search
#define BITOUT __builtin_popcount
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);
#define test ll t; cin>>t; while(t--)
#define cn cout<<"\n";
int main()
{
     fast
     ll a,b,c,d;
     cin>>a>>b>>c>>d;
     cout<<max({a*c,a*d,b*c,b*d});
}

Measured memory_bytes: 3648
#include<stdio.h>

int main(void){
    int n, k, h, cnt = 0;
    scanf("%d""%d", &n, &k);
    for(int i = 0; i < n; i++){
        scanf("%d", &h);
        if(h >= k){
            cnt ++;
        }
    }
    printf("%d\n", cnt);
    return 0;
}

Measured memory_bytes: 128
#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#include<string>
#include<cstdio>
#include<cctype>
#include<cassert>
#include<cstdlib>
#include<cstring>
#include<sstream>
#include<iostream>
#include<algorithm>

#define For(i,x,y) for (int i=x;i<y;i++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define lf else if

#define dprintf(...) fprintf(stderr,__VA_ARGS__)
using namespace std;

typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> Vi;

ll IN(){
	int c,f;ll x;
	while (!isdigit(c=getchar())&&c!='-');c=='-'?(f=1,x=0):(f=0,x=c-'0');
	while (isdigit(c=getchar())) x=(x<<1)+(x<<3)+c-'0';return !f?x:-x;
}

const int N=100000+19;

ll A[N],coef[N],ans[N];
vector<pll> V[N];
int n,q;
ll x;

int main(){
	n=IN(),q=IN();
	For(i,1,q+1){
		x=IN();
		while (*A&&x<=A[*A]) --*A;
		A[++*A]=x;
	}
	if (*A==0||A[1]>n){
		for (int i=*A+1;i>1;i--) A[i]=A[i-1];
		A[1]=n;
		++*A;
	}
	coef[*A]=1;
	for (int i=*A;i>1;i--){
		coef[i-1]+=coef[i]*(A[i]/A[i-1]);
		if (A[i]%A[i-1]!=0) V[i].pb(mp(A[i]%A[i-1],coef[i]));
		for (pll u:V[i]){
			coef[i-1]+=(u.fi/A[i-1])*u.se;
			int v=lower_bound(A+1,A+*A+1,u.fi%A[i-1])-A;
			V[v].pb(mp(u.fi%A[i-1],u.se));
		}
	}
	for (pll u:V[1]) ans[u.fi]+=u.se;
	for (int i=n;i;i--) ans[i]+=ans[i+1];
	For(i,1,A[1]+1) ans[i]+=coef[1];
	For(i,1,n+1) printf("%lld\n",ans[i]);
}

Measured memory_bytes: 24416
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {

		Scanner scanner = new Scanner(System.in);
		String[] temp1 = scanner.nextLine().split(" ");
		int n = Integer.parseInt(temp1[0]);
		int m = Integer.parseInt(temp1[1]);

		int ans = 0;
		int temp = 0;
		//m/n
		int a1 = (int) Math.floor(m / n);

		//mの約数
		for(int i = a1; i > 0; i--) {
			temp = m;
			if(temp % i == 0) {
				ans = i;
				break;
			}
		}
		System.out.println(ans);
	}
}



Measured memory_bytes: 23636
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include <algorithm> 
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repR(i,n) for(ll i=n;i>=0;i--)
#define all(v)(v).begin(),(v).end()
#define rall(v)(v).rbegin(),(v).rend()
#define F first
#define S second
#define pb push_back
#define pu push
#define COUT(x) cout<<(x)<<endl
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,vector<ll>,greater<ll>>
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define mp make_pair
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define sz(x) (ll)(x).size()
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll MOD = 1000000007LL;
const ll INF = 1LL << 60;
using vll = vector<ll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvll = vector<vll>;
using vstr = vector<string>;
using pll = pair<ll, ll>;
using vc = vector<char>;
using vvc = vector<vc>;
template<class T> inline bool chmax(T& a, T b) { 
if (a < b) { a = b; return true; } return false; 
}
template<class T> inline bool chmin(T& a, T b) {
 if (a > b) { a = b; return true; } return false; 
 }
ll dx[4]={0,1,0,-1};
ll dy[4]={1,0,-1,0};
int main(){
  ll n,k;
  cin>>n>>k;
  if(n%k==0){
    COUT(0);
  }
  else{
    n%=k;
    ll ans=min(k-n,n);
    COUT(ans);
  }
}

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

int main() {

	int n; cin >> n;
	string s;
	map<string, int> count;
	for (int i = 0; i < n; i++) {
		cin >> s;
		count[s]++;
	}

	int max_cnt = 0;
	for (auto& it : count)
		max_cnt = max(max_cnt, it.second);

	for (auto& it : count)
		if (it.second == max_cnt)
			cout << it.first << endl;
}

Measured memory_bytes: 25216
use std::io;

fn main() {
    let mut input = String::new();
    io::stdin().read_line(&mut input).ok();
    let input = input.trim();
    let len = input.len();

    let mut input = input.chars();

    let mut i = 0;
    let mut countC = 0;
    let mut countU = 0;
    let mut ans = true;

    loop {
        i += 1;
        let buf = input.next();
        if let None = buf {
            break;
        }
        let buf = buf.unwrap();

        if i == 1 && buf != 'A' {
            ans = false;
            break;
        }
        if i >= 3 && i <= len - 1 {
            if buf == 'C' {
                countC += 1;
            }
        }
        if buf.is_uppercase() {
            countU += 1;
        }
    }
    if ans && countC == 1 && countU == 2 {
        println!("AC");
    } else {
        println!("WA");
    }
}

Measured memory_bytes: 4352
#include <iostream>
#include <algorithm>
#include <functional>
#include<vector>
#include<math.h>
#include<bitset>
#include<string>
#include <deque>
#include<queue>
#include<map>

using namespace std;
vector<int> G[100008];
long long int fene[100008], sune[100008];
void serchfene(long long int X) {
	for (int i = 0; i < G[X].size(); i++) {
		if (fene[G[X][i]] > fene[X] + 1) {
			fene[G[X][i]] = fene[X]+1;
			serchfene(G[X][i]);
		
		}
	}
}

void serchsune(long long int X) {
	for (int i = 0; i < G[X].size(); i++) {
		if (sune[G[X][i]] > sune[X] + 1) {
			sune[G[X][i]] = sune[X]+1;
			serchsune(G[X][i]);
		}
	}
}

int main() {
	long long int N;
	cin >> N;
	int a, b;

	for (int i = 0; i < N-1; i++) {
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	fene[1] = 0;
	sune[N] = 0;
	
	for (int i = 2; i <= N; i++) {
		fene[i] = 10000000;
	}
	for (int i = 1; i < N; i++) {
		sune[i] = 10000000;
	}

	serchfene(1);

	serchsune(N);


	long long int Y = 0;

	for (int i = 1; i <= N; i++) {
		
		if (fene[i] > sune[i]) {
			Y++;
		}
		else if (fene[i] == sune[i]) {
			Y--;
		}
		else {
			Y--;
		}
	}

	if (Y<0) {
		cout << "Fennec" << endl;
	}
	else {
		cout << "Snuke" << endl;
	}

	return 0;
}

Measured memory_bytes: 11904
import sys
import math
from fractions import gcd
# import queue
# from collections import Counter
# from itertools import accumulate
from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())

## 数値
 =  int(sys.stdin.readline())
 =  map(int, sys.stdin.readline().split())
 =  list(map(int, sys.stdin.readline().split()))
 =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""


N =  int(sys.stdin.readline())
L =  list(map(int, sys.stdin.readline().split()))

target = reduce(lcm, L) - 1

print(sum([target % l for l in L]))

Measured memory_bytes: 67160
#include <bits/stdc++.h>
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
#define fi first
#define se second

using namespace std;
typedef pair <int, int> pii;

int arr[301010], brr[301010];
vector <int> ta, tb;

map <int, vector <int> > g;

set <int> chk;
int dfs(int k) {
	if(chk.find(k) != chk.end()) return 0;
	chk.insert(k);
	int ret = 0;
	for(auto i : g[k]) {
		if(i == k) continue;
		ret++;
		ret += dfs(i);
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> arr[i];
		arr[0] ^= arr[i];
		ta.eb(arr[i]);
	}
	ta.eb(arr[0]);
	for(int i = 1; i <= n; i++) {
		cin >> brr[i];
		brr[0] ^= brr[i];
		tb.eb(brr[i]);
	}
	tb.eb(brr[0]);
	sort(all(ta));
	sort(all(tb));

	for(int i = 0; i <= n; i++) {
		if(ta[i] != tb[i]) {
			cout << -1;
			return 0;
		}
	}
	for(int i = 0; i <= n; i++) {
		g[brr[i]].eb(arr[i]);
	}
	int ans = max(1, dfs(arr[0])) - 1;
	if(arr[0] == brr[0] && ans != 0) ans++;
	for(int i = 1; i <= n; i++) {
		if(arr[i] != brr[i] && chk.find(arr[i]) == chk.end()) ans += dfs(arr[i]) + 1;
	}
	cout << ans;
}

Measured memory_bytes: 25208
#include<stdio.h>
int main()
{
	int x;
	int i,c=0;
	scanf("%d",&x);
	while(1){
		for(i=1;i<=x;i++){
			if(x%i==0){
				c++;
			}
		}
		if(c==2){
			break;
		}
		else{
			c=0;
			x++;
		}
	}
	printf("%d\n",x);
	return 0;
}

Measured memory_bytes: 1700
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <numeric>

using namespace std;

int main(){

  int n, t;
  cin >> n >> t;

  int c, tt;
  int ans = 1001;
  for (int i =0; i < n; i++){
    cin >> c >> tt;
    if (tt <= t){
      if (c < ans){
        ans = c;
      }
    }
  }
  if (ans == 1001){
    cout << "TLE" << endl;
    return 0;
  }

  cout << ans << endl;

  return 0;
}


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


int main(){
  int N;
  cin >> N;
  vector<tuple<string, int, int>> restaurant(N);

  
  for(int i = 0; i < N; i++){
    string city;
    int score;
    cin >> city >> score;
    score = -score;
    restaurant.at(i) = make_tuple(city, score, i + 1);
  }

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

  /*
  for(auto c: restaurant){
    cout << get<0>(c) << " " << get<1>(c) << " " << get<2>(c) << endl;
  }
  */
 
 for(int i = 0; i < N; i++){
   string name;
   int score;
   int index;
   tie(name, score, index) = restaurant.at(i);
   cout << index << endl;
 }

}

Measured memory_bytes: 256
#include<stdio.h>
#include<algorithm>
int A[100];
void trace(int N)
{
	for(int i=0;i<N;i++)
	{
		if(i>0)
		printf(" ");
		printf("%d",A[i]);

	}
	printf("\n");
}
void instertionSort(int N)
{
	int j,i,v;
	for(i=1;i<N;i++)
	{
		v=A[i];
		j=i-1;
		while(j>=0&&A[j]>v)
		{
			A[j+1]=A[j];
			j--;
		}
		A[j+1]=v;
		trace(N);
	}
}
int main()
{
	int N,i,j;

	scanf("%d",&N);
	for(int i=0;i<N;i++)	scanf("%d",&A[i]);
	trace(N);
	instertionSort(N);
	return 0;
}

Measured memory_bytes: 2748
#include <iostream>
#include <map>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <climits>
#include <stack>
#include <queue>
#include <set>
#include <cctype>
#include <bitset>
#include <type_traits>

#include <list>
using namespace std;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define YES(j) cout << (j ? "YES" : "NO") << endl;
#define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
#define yes(j) std::cout << (j ? "yes" : "no") << endl;

int main(void)
{
    int r;
    cin >> r;
    if (r < 1200)
    {
        cout << "ABC" << endl;
    }
    else if (r < 2800)
    {
        cout << "ARC" << endl;
    }
    else
    {
        cout << "AGC" << endl;
    }
}

Measured memory_bytes: 256
#include<stdio.h>
long long SUM(int d,long long n){
	return d*n*(n+1)/2;
}
int main(void){
	long long n,thr,fiv,fif;
	scanf("%lld", &n);
	thr=n/3;
	fiv=n/5;
	fif=n/15;
	printf("%lld",SUM(1,n)-SUM(3,thr)-SUM(5,fiv)+SUM(15,fif));
	return 0;
}


Measured memory_bytes: 1680
#include <bits/stdc++.h>
#include <vector>
#include <numeric>
#define PI 3.14159265358979323846
#define MAXINF (1e18L)
#define INF (1e9L)
#define EPS (1e-9)
#define MOD ((ll)(1e9+7))
#define REP(i, n) for(int i=0;i<int(n);++i)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define ALL(v) (v.begin(),v.end())
#define FIND(v,x) (binary_search(ALL(v),(x)))
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v));reverse(ALL(v))
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define pb push_back
#define fi first
#define se second
using namespace std;
template<class A>void pr(A a){cout << (a) << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;pr(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;pr(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;pr(b,c,d);}
template<class T> inline bool chmin(T& a, T b){return a>b ? a=b, true : false;}
template<class T> inline bool chmax(T& a, T b){return a<b ? a=b, true : false;}
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;

int main(void)
{
    ll n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) {
        int a_;
        cin >> a_;
        a[i] = a_ * 2;
    }
    auto y = [n](ll n_){
        ll aa = 0;
        if(n_ == -1) aa = n-1;
        else if(n_ == n) aa = 0;
        else if(n_ == n+1) aa == 1;
        else aa = n_;
        return aa;
    };

    vector<ll> ans(n, 0);
    REP(i, n){
        ans[0] += a[i] * ((i % 2) ? -1 : 1);
    }
    ans[0] /= 2;
    Rep(i, 1, n){
        ans[i] = a[y(i-1)] - ans[i-1];
    }
    REP(i, n){
        cout << ans[i] << " ";
    }
    cout << endl;

}

Measured memory_bytes: 2944
#include<bits/stdc++.h>
using namespace std;
int g,p,win,lose;
int main()
{
	string s;
	cin>>s;
	for(int i=0;i<s.length();i++)
	{
		if(g==p)
		{
			g++;
			if(s[i]=='p') lose++;
		}
		else
		{
			p++;
			if(s[i]=='g') win++;
		}
	}
	cout<<win-lose<<endl;
}

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

public class Main {

	BufferedReader br;
	PrintWriter out;
	StringTokenizer st;
	boolean eof;

	void solve() throws IOException {
		int n = nextInt();
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt() - 1;
		}
		int ans = 0;
		for (int i = 0; i < n; i++) {
			if (i < a[i] && a[a[i]] == i) {
				ans++;
			}
		}
		out.println(ans);
	}

	Main() throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		solve();
		out.close();
	}

	public static void main(String[] args) throws IOException {
		new Main();
	}

	String nextToken() {
		while (st == null || !st.hasMoreTokens()) {
			try {
				st = new StringTokenizer(br.readLine());
			} catch (Exception e) {
				eof = true;
				return null;
			}
		}
		return st.nextToken();
	}

	String nextString() {
		try {
			return br.readLine();
		} catch (IOException e) {
			eof = true;
			return null;
		}
	}

	int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}
}

Measured memory_bytes: 22252
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
using namespace std;
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define all(a) a.begin(),a.end()
#define rall(c) (c).rbegin(),(c).rend()
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll inf=1e9+7;
const ll mod=1e9+7;
int main(){
    ll k;cin>>k;
    vector<vector<ll> >dp(k+1,vector<ll>(10));
    rep(i,10){
        dp[0][i]=1;
    }
    REP(i,1,k+1){
        rep(j,10){
            if(j==0){
                dp[i][j]=dp[i-1][0]+dp[i-1][1];
            }
            else if(j==9){
                dp[i][j]=dp[i-1][8]+dp[i-1][9];
            }else{
                dp[i][j]=dp[i-1][j-1]+dp[i-1][j]+dp[i-1][j+1];
            }
        }
    }
    vector<vector<ll> >dpsum(k+1,vector<ll>(10));
    ll sum=0;
    ll now=0;
    ll d=0;
    ll last=0;
    bool f=0;
    string ans="";
    rep(i,k+1){
        if(i>0)dpsum[i][0]=dpsum[i-1][9];
        else dpsum[i][0]=1;
        REP(j,1,10){
            sum+=dp[i][j];
            dpsum[i][j]=sum;
            if(sum>=k){
                last=sum-dp[i][j],now=i-1,d=j;
                f=1;
                ans+=j+'0';
                k-=dpsum[i][j-1];
                break;
            }
        }
        if(f)break;
    }
    for(int i=now;i>=0;i--){
        ll sum=0;
        REP(j,max(d-1,0LL),d+2){
            sum+=dp[i][j];
            if(sum>=k){
                ans+=j+'0';
                k-=sum-dp[i][j];
                d=j;
                break;
            }
        }
    }
    cout<<ans<<endl;
}

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

template<long long mod>
class modint{
private:
  long long a;
public:
  constexpr modint(const long long x = 0) noexcept : a(x%mod) {}
  constexpr long long& value() noexcept { return a; }
  constexpr const long long& value() const noexcept { return a; }
  constexpr modint operator+(const modint rhs) const noexcept {
    return modint(*this) += rhs;
  }
  constexpr modint operator-(const modint rhs) const noexcept {
    return modint(*this) -= rhs;
  }
  constexpr modint operator*(const modint rhs) const noexcept {
    return modint(*this) *= rhs;
  }
  constexpr modint operator/(const modint rhs) const noexcept {
    return modint(*this) /= rhs;
  }
  constexpr modint& operator+=(const modint rhs) noexcept {
    a += rhs.a;
    if(a >= mod) a -= mod;
    return *this;
  }
  constexpr modint &operator-=(const modint rhs) noexcept {
    if(a < rhs.a) a += mod;
    a -= rhs.a;
    return *this;
  }
  constexpr modint& operator*=(const modint rhs) noexcept {
    a = a*rhs.a%mod;
    return *this;
  }
  constexpr modint& operator/=(modint rhs) noexcept {
    long long k = mod-2;
    while(k > 0){
      if(k&1){
        *this *= rhs;
      }
      rhs *= rhs;
      k /= 2;
    }
    return *this;
  }
  friend ostream& operator<<(ostream &os, const modint &X){
    return os << X.a;
  }
  friend istream& operator>>(istream &is, modint &X){
    is >> X.a;
    X.a %= mod;
    if(X.a < 0) X.a += mod;
    return is;
  }
};


int main(){
  using mint = modint<998244353>;
  int N, S;
  cin >> N >> S;
  vector<int> A(N);
  for(int i = 0; i < N; ++i) cin >> A[i];
  vector<mint> dp(S+1);
  mint ans = 0;
  for(int i = 0; i < N; ++i){
    if(A[i] <= S){
      for(int j = S-A[i]; j >= 0; --j){
        dp[j+A[i]] += dp[j];
      }
      dp[A[i]] += i+1;
    }
    ans += dp[S];
    // cerr << i << " " << dp[S] <<endl;
  }
  cout << ans << endl;
}


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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> mat;
#define FOR(i,a,b) for(int i=(a);i<(int)(b);++i)
#define rep(i,n) FOR(i,0,n)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define mset(a,x) memset(a,x,sizeof(a))
#define OUT(x) cout<<(x)<<"\n"
#define SZ(x) (int)(x).size()
#define FASTIO cin.tie(0),ios::sync_with_stdio(0)



int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) scanf("%d", &a[i]);

    if(n == 1) {
        OUT(1); return 0;
    }

    int inc = -1;
    rep(i, n - 1) {
        if(a[i] < a[i + 1]) {
            inc = 1; break;
        }
        else if(a[i] > a[i + 1]) {
            inc = 0; break;
        }
    }

    if(inc == -1) {
        OUT(1); return 0;
    }

    ll ans = 0;
    a.push_back(114514);
    rep(i, n - 1) {
        if(inc) {
            if(a[i] > a[i + 1]) {
                ++ans;
                FOR(j, i + 1, n - 1) {
                    if(a[j] < a[j + 1]) {
                        inc = 1; break;
                    } else if(a[j] > a[j + 1]) {
                        inc = 0; break;
                    }
                }
            }
        }
        else {
            if(a[i] < a[i + 1]) {
                ++ans;
                FOR(j, i+1, n - 1) {
                    if(a[j] < a[j + 1]) {
                        inc = 1; break;
                    } else if(a[j] > a[j + 1]) {
                        inc = 0; break;
                    }
                }
            }
        }
    }

    OUT(ans + 1);

    return 0;
}

Measured memory_bytes: 1024
#include <iostream>

using namespace std;

int main() {
    int s; cin >> s;
    int index = 1;
    while(true) {
        if(s == 2 || s == 1 || s == 4) break;
        if(s % 2 == 0) {
            s /= 2;
        } else {
            s = 3 * s + 1;
        }
        index++;
    }

    cout << index + 3 << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define INF (1LL<<50)
#define MOD 1000000007

int main(){
    int N,K;
    cin >> N >> K;
    vector<int> P(N);
    rep(i,N) cin >> P[i];
    sort(P.begin(),P.end());
    ll ans =0;
    rep(i,K) ans+=P[i];
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3632
import std.algorithm,
       std.string,
       std.range,
       std.stdio,
       std.conv;

bool chmin(T)(ref T a, T b) {
  if (b < a) {
    a = b;
    return true;
  } else {
    return false;
  }
}

void chChar(ref string base, size_t idx, char c) {
  char[] tmp = base.to!(char[]);
  tmp[idx] = c;
  base = cast(string)tmp;
}

void main() {
  string Sd = readln.chomp.to!(char[]);
  string T = readln.chomp.to!(char[]);
  string ans;

  foreach (i, s; Sd) {
    string tmp = Sd;
    bool match = true;
    foreach (j, t; T) {
      if (i + j >= Sd.length) {
        match = false;
        break;
      }
      if (Sd[i + j] == T[j] || Sd[i + j] == '?') {
        chChar(tmp, i + j, T[j]);
      } else {
        match = false;
        break;
      }
    }

    if (!match) {
      continue;
    }

    foreach (j, c; tmp) {
      if (c == '?') {
        chChar(tmp, j,  'a');
      }
    }
    if (ans.empty) {
      ans = tmp;
    } else {
      chmin(ans, tmp);
    }
  }

  if (ans.empty) {
    writeln("UNRESTORABLE");
  } else {
    writeln(ans);
  }
}


Measured memory_bytes: 380
#!/usr/bin/env python3
import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
A = list(map(lambda x: x*(-1), A))  # 各要素を-1倍

heapq.heapify(A)

if N == 1:
    MAX = heapq.heappop(A)//2**M 
    if MAX < 0:
        print(0)
    else:
        print(MAX)
    exit()

cnt = 0
while M > 0:
    MAX = heapq.heappop(A)
    if MAX % 2 == 0:
        heapq.heappush(A, MAX//2)
    else:
        heapq.heappush(A, MAX//2+1)

    M -= 1

print(-sum(A))


Measured memory_bytes: 74520
N=int(input())
A=list(map(int,input().split()))

base=A[0]
cnt=1
mode="N"
for i in range(N):
    if mode=="N":
        if A[i]>base:
            mode="P"
        elif A[i]<base:
            mode="M"
        else:
            pass
    elif mode=="P":
        if A[i]>=A[i-1]:
            pass
        else:
            mode="N"
            cnt+=1
            base=A[i]
    elif mode=="M":
        if A[i]<=A[i-1]:
            pass
        else:
            mode="N"
            cnt+=1
            base=A[i]
print(cnt)

Measured memory_bytes: 14224
#!/usr/bin/ruby
# -*- coding: utf-8 -*-
=begin

Discussion Solution Statistics Submit

Math Functions - Distance
Time Limit : 1 sec, Memory Limit : 65536 KB
?????¢

?????? P1(x1, y1), P2(x2, y2) ????????¢????±???????????????°????????????????????????
Input

x1, y1, x2, y2 ????????°???????????????????????§?????????????????????
Output

P1??¨P2????????¢????????°??§?????????????????????????????????0.0001??\????????????????????£????????????????????¨????????????
Sample Input

0 0 1 1

Sample Output

1.41421356

=end
fh=STDIN
fl=fh.gets.chomp.split
x1=fl[0].to_f
y1=fl[1].to_f
x2=fl[2].to_f
y2=fl[3].to_f
r = Math.sqrt((x1-x2)**2 + (y1-y2)**2)
puts r

Measured memory_bytes: 8732
#include<bits/stdc++.h>
	using namespace std;
	typedef long long ll;
	typedef long double ld;
	typedef pair<ll,ll> pll;
	typedef pair<int,int> pii;
	#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
	#define pb push_back
	#define F first
	#define S second
	//cout<<fixed<<setprecision(11);
	const string nl="\n";
	const int MOD=1e9+7;
	const ll ARR_MAX = 1e5+1;
	const ll VAL_MAX = 1e5+1;
	const ll INF=1e14;

	vector<int> tr[ARR_MAX];
	ll dp[ARR_MAX][2];
	//dp[x][i] = number of ways to color all visited vertices so far and by coloring current vertex x by i.
	//0 is white
	//1 is black
	void dfs(int par,int x){
		ll zero=1,one=1;
		for(int i=0;i<tr[x].size();i++){
			int y=tr[x][i];
			if(y!=par){
				// cout<<par+1<<" "<<x+1<<" "<<y+1<<" ,";
				dfs(x,y);
				zero*=(dp[y][0]+dp[y][1])%MOD;
				zero%=MOD;
				one*=dp[y][0];
				one%=MOD;
			}
		}
		// if(par!=-1 && tr[x].size()==1){
		// 	dp[x][0]=1;
		// 	dp[x][1]=1;
		// 	return;
		// }
		// cout<<x+1<<" "<<zero<<" "<<one<<nl;
		dp[x][0]=zero;
		dp[x][1]=one;
	}

	void solve(){
	    int n;cin>>n;
	    for(int i=0;i<n-1;i++){
	    	int x,y;
	    	cin>>x>>y;
	    	x--;y--;
	    	tr[x].pb(y);
	    	tr[y].pb(x);
	    }
	    dfs(-1,0);
	    int ans=(dp[0][0]+dp[0][1])%MOD;
	    cout<<ans<<nl;
	}

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

Measured memory_bytes: 15616