akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <numeric>
typedef long long Int;
#define rep(i,a,b) for(Int i=a;i<b;++i)
#define rrep(i,a,b) for(Int i=a;i>=b;--i)
using namespace std;

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

    Int N, M; cin >> N >> M;
    vector<Int> cnt(M, 0);

    rep(i, 0, N) {
        Int K; cin >> K;
        rep(j, 0, K) {
            Int A; cin >> A;
            cnt[A-1]++;
        }
    }

    cout << count(cnt.begin(), cnt.end(), N) << endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
int n,a,max = -10000,min = 100000;
    cin >> n;
    for(int i = 0;i < n;i++){
        cin >> a;
        if(max < a){
            max = a;
        }
        if(min > a){
            min = a;
        }
    }
    cout << max-min << endl;
  	return 0;
}

Measured memory_bytes: 256
#include"bits/stdc++.h"
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define REP(i, n) FOR(i, 0, n)
#define RFOR(i, a, b) for (int i = b - 1; i >= a; i--)
#define RREP(i, n) RFOR(i, 0, n)
#define rep(i, a, b) for (auto i = a; i < b; i++)
#define rrep(i, a, b) for (auto i = a; i > b; i--)
#define range(i, a, b) (a <= i && i < b)
#define fi first
#define fs first
#define se second
#define sc second
using namespace std;
using vec = vector<int>;
using mat = vector<vec>;
typedef pair<int, int> P;
#define ll long long

class Rect
{
public:
	int w, d;
	Rect(int a,int b)
		: w(a)
		, d(b)
	{}

	bool operator<(const Rect& a)const
	{
		return w * d < a.w *a.d;
	}
};

bool solve()
{
	int n, w, d;
	cin >> n >> w >> d;
	if (n == 0 && w == 0 && d == 0) return false;

	list<Rect> lst;
	lst.emplace_back(w, d);

	for (int i = 0; i < n; ++i)
	{
		int p, s;
		cin >> p >> s; --p;

		auto rect = lst.begin();
		REP(j, p) rect++;

		s %= rect->w * 2 + rect->d * 2;
		
		if (s < rect->w)
		{
			lst.emplace_back(min(rect->w - s, s), rect->d);
			lst.emplace_back(max(rect->w - s, s), rect->d);
		}
		else if (s < rect->w + rect->d)
		{
			s -= rect->w;
			lst.emplace_back(rect->w, min(rect->d - s, s));
			lst.emplace_back(rect->w, max(rect->d - s, s));
		}
		else if (s < rect->w * 2 + rect->d)
		{
			s -= rect->w + rect->d;
			lst.emplace_back(min(rect->w - s, s), rect->d);
			lst.emplace_back(max(rect->w - s, s), rect->d);
		}
		else
		{
			s -= rect->w * 2 + rect->d;
			lst.emplace_back(rect->w, min(rect->d - s, s));
			lst.emplace_back(rect->w, max(rect->d - s, s));
		}
		lst.erase(rect);
	}
	lst.sort();

	for (auto itr=lst.begin();itr!=lst.end();++itr)
	{
		if (itr != lst.begin())
		{
			cout << " ";
		}
		cout << itr->w * itr->d;
	}
	cout << endl;
	return true;
}

int main()
{
	while (solve());
	return 0;
}


Measured memory_bytes: 3084
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main(){
    ll n;
    cin>>n;
    if(n%1000==0)
    cout<<0<<endl;
    else
    {
        n=n%1000;
        int rem;
        rem=1000-n;
        cout<<rem<<endl;
    }
    return 0;
}

Measured memory_bytes: 3620
#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
#define sz(c) int((c).size())

typedef pair<int, int> pii;
priority_queue<pii> q;


int main(int argc, char **argv)
{
  int team, ac;
  char c;
  for (;;) {
    cin >> team >> c >> ac;
    if (!team && !ac)
      break;
    q.push(pii(ac, team));
  }
  map<int, int> m;
  int rank = 0, prev_score = 0;
  while (sz(q)) {
    pii p = q.top(); q.pop();
    if (p.first != prev_score) {
      prev_score = p.first;
      ++rank;
    }
    m[p.second] = rank;
  }
  while (cin >> team) {
    cout << m[team] << endl;
  }
  return 0;
}

Measured memory_bytes: 1196
package main

import (
	"fmt"
	"os"
)

func main() {
	var x int
	fmt.Scanf("%d", &x)

	composit := [1000000]bool{}

	composit[0] = true
	composit[1] = true

	p := 2
	for p < 1000 {
		for m := 2; p*m < 1000000; m++ {
			composit[p*m] = true
		}
		p++
		for composit[p] {
			p++
		}
	}

	for i := x; i < 1000000; i++ {
		if !composit[i] {
			fmt.Printf("%d\n", i)
			os.Exit(0)
		}
	}
}


Measured memory_bytes: 1536
#include <bits/stdc++.h>
#define REP(i, a, n) for (long long i = (a); i < (long long)(n); ++i)
#define REPC(i, a, n) for (long long i = (a); i <= (long long)(n); ++i)
#define ALL(t) t.begin(), t.end()
#define RALL(t) t.rbegin(), t.rend()
#define MATINIT(type, row, col, init)                                          \
  vector<vector<type>>(row, vector<type>(col, init));
#define Yes(cond) cout << (cond ? "Yes" : "No") << endl;
#define YES(cond) cout << (cond ? "YES" : "NO") << endl;
using namespace std;
using LL = long long;
using ULL = unsigned long long;
template <class T> using VEC = std::vector<T>;
template <class T> using MAT = std::vector<std::vector<T>>;
void DUMP() { cerr << endl; }
template <class Head, class... Tail> void DUMP(Head &&head, Tail &&... tail) {
  cerr << head << ", ";
  DUMP(std::move(tail)...);
}
template <typename T> ostream &operator<<(ostream &os, vector<T> &vec) {
  os << "{";
  for (auto v : vec)
    os << v << ",";
  os << "}";
  return os;
}
template <typename T> ostream &operator<<(ostream &os, set<T> &s) {
  os << "{";
  for (auto p : s)
    os << p << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, map<T1, T2> &m) {
  os << "{";
  for (auto p : m)
    os << p << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, pair<T1, T2> p) {
  os << "[" << p.first << " " << p.second << "]";
  return os;
}

int main() {
  int N;
  cin>>N;
  VEC<LL>A(N+1), B(N);
  REP(i,0,N+1)cin>>A[i];
  REP(i,0,N)cin>>B[i];
  LL orig =0;
  REP(i,0,N+1){
    orig+=A[i];
  }

  REP(i,0,N){
    if(B[i]>0){
      A[i]-=B[i];
      B[i]=0;
      if(A[i]<0){
        B[i]+=-A[i];
        A[i]=0;
      }
    }
    if(B[i]>0){
      A[i+1]-=B[i];
      B[i]=0;
      if(A[i+1]<0){
        B[i]+=-A[i+1];
        A[i+1]=0;
      }
    }
  }
  LL sum =0;
  REP(i,0,N+1){
    sum+=A[i];
  }
  cout<<orig-sum<<endl;

  return 0;
}


Measured memory_bytes: 1792
import java.util.Scanner;

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

		int n = sc.nextInt();
		int l = sc.nextInt();
		int first = l;
		int last = l + n - 1;
		int sum = n * l + n * (n + 1) / 2 - n;
		int ans = sum;

		if (first > 0) {
			ans -= first;
		} else if (last < 0) {
			ans -= last;
		}

		System.out.println(ans);

	}

}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;
#define ll long long
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define rep1(i, n) FOR(i, 1, n+1)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; --i)
#define whole(x) (x).begin(),(x).end()
#define rwhole(x) (x).rbegin(), (x).rend()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define P pair<int, int>
#define debug(var) cerr << "[" << #var << "] " << var << endl
template<typename T1, typename T2>
bool chmax(T1 &a,T2 b){if(a<b){a=b;return true;}else return false;}
template<typename T1, typename T2>
bool chmin(T1 &a,T2 b){if(a>b){a=b;return true;}else return false;}
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define pr(s) cout << (s) << '\n'
ll mod = 1000000007;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,-1,0,1};
const int INF = 1001001001;
const ll INFll = 1E+18;
 
int main() {
  int n, h, w;
  cin >> n >> h >> w;
  int ans = 0;
  rep(i, n) {
    int a, b;
    cin >> a >> b;
    if (h<=a && w<=b) ans++;
  }
  pr(ans);
}

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

int main()
{
  ll n; cin >> n;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];
  map<int, int> mpl, mpr;
  ll ans = 0;
  rep(i, n) {
    ll r = i-a[i];
    mpr[r]++;
  }
  rep(i, n) {
    ll l = i+a[i];
    ll r = i-a[i];
    mpr[r]--;
    ans += mpr[l];
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 21912
import java.util.Arrays;
import java.util.Scanner;


public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] ints = new int[5];
		for(int i=0; i<5;i++){
			ints[i]=sc.nextInt();
		}
		Arrays.sort(ints);
		int[] ints2 = new int[5];
		for(int i=0; i<ints.length; i++){
			ints2[4-i]=ints[i];
		}
		int a=0;
		while(a<4){
		System.out.print(ints2[a]+" ");
		a++;
		}
		System.out.println(ints2[4]);
	}
}

Measured memory_bytes: 17304
import collections

n, m = map(int, input().split())
lst = [input().split() for i in range(n)]

lst2 = list()
for i in range(0, len(lst)):
    for j in range(1, len(lst[i])):
        lst2.append(lst[i][j])

c = collections.Counter(lst2)

ans_cnt = 0
for moji, cnt in c.items():
    if cnt == n:
        ans_cnt+=1

print(ans_cnt)

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

typedef long long ll;

using namespace std;


void solve(vector<vector<int>> room, int n) {
    
    set<int> used;
    
    map<int,int> mapp;
    vector<int> roomNums={1};
    int index=0;
    int before = 0;
    
    while(roomNums.size()<n) {
        
        index=(int)roomNums.size()-index;
        
        if(index==before) {
            cout<<"No"<<"\n";
            return;
        }
        
        before=index;
        
        for(int i=index; i<roomNums.size(); i++) {
            int roomNum = roomNums[i]-1;
            for(int j=0; j<room[roomNum].size(); j++) {
                int num = room[roomNum].at(j);
                if(used.count(num)==0){
                    mapp[num]=roomNum+1;
                    used.insert(num);
                    roomNums.push_back(num);
                    index++;
                }
            }
        }
    }
    
    cout<<"Yes"<<"\n";
    for(auto x : mapp) {
        if(x.first!=1)
            cout<<x.second<<"\n";
    }
    
    
}


int main() {
    
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n, m;
    
    cin>>n>>m;
    vector<vector<int>> room(n+1,vector<int>(0));

    while(m--) {
        int a,b;
        cin>>a>>b;
        room[b-1].push_back(a);
        room[a-1].push_back(b);
    }
    
    solve(room, n);

}


Measured memory_bytes: 24900
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()

if K%2 == 0:  # K が偶数
	print((N//K)**3+((N//(K//2)-N//K))**3)
else:  # K が奇数
	print((N//K)**3)


Measured memory_bytes: 5156
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <string>

using namespace std;
typedef long long ll;
#define rep(i,s,n)for(ll i = s;i<n;i++)
#define repe(i,s,n)for(ll i = s;i<=n;i++)

ll a[100000] = {};
int main() {
	ll N; cin >> N;
	map<ll, ll> mp;
	rep(i, 0, N) {
		ll A; cin >> A;
		mp[A]++;
	}

	ll cnt = 0;
	for (map<ll, ll>::iterator it = mp.begin(); it != mp.end(); it++) {
		if (it->second % 2 == 1) {
			cnt++;
		}
	}

	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 6528
#include<iostream>
#include<cstring>
#include<algorithm>
#include<math.h>
#include<queue>
#include<cstdio>
#include<limits.h>
#include<map>
using namespace std;
map<string ,int>	myM;
int mov[4]= {4,-4,1,-1};
void bfs() {
	string init="01234567";
	myM[init]=0;
	queue<string>	myQ;
	myQ.push(init);
	while(!myQ.empty()) {
		string s=myQ.front();
		myQ.pop();
		int index=s.find('0',0);
		for(int i=0; i<4; i++) {
			int t=index+mov[i];
			string temp=s;
			if(t>=0&&t<8&&!(index==3&&t==4)&&!(index==4&&t==3)) {
				swap(temp[index],temp[t]);
				if(myM.find(temp)==myM.end()) {
					myQ.push(temp);
					myM[temp]=myM[s]+1;
				}
			}
		}
	}
}
int main() {
	string input;
	bfs();
	while(getline(cin,input)) {
		input.erase(remove(input.begin(),input.end(),' '),input.end());
		printf("%d\n",myM[input]);
	}
	return 0;
}


Measured memory_bytes: 5520
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#define my_abs(x) ((x) < 0 ? -(x) : (x))
#define mp std::make_pair
#define pb push_back
typedef long long ll; 
int idx[200005]; 
int main()
{
	// freopen("AGC024-B.in", "r", stdin); 
	int n, ans = 0; 
	scanf("%d", &n); 
	for (int i = 0; i < n; i++)
	{
		int x; 
		scanf("%d", &x); 
		idx[x] = i; 
	}
	for (int i = 1; i <= n;)
	{
		int x = idx[i], cnt = 0; 
		while (i <= n && idx[i] >= x)
		{
			cnt++; 
			x = idx[i++]; 
		}
		ans = std::max(ans, cnt); 
	}
	printf("%d\n", n - ans);
	return 0; 
}


Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <utility>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;

const ll INF = 4e18;

int main()
{
    int n, k;
    cin >> n >> k;
    ll x[51], y[51];
    P p[51];
    for(int i = 0; i < n; i++){
        cin >> x[i] >> y[i];
        p[i] = P(x[i], y[i]);
    }
    sort(p, p + n);
    ll ans = INF;
    for(int l = 0; l <= n - k; l++){
        ll ls = INF;
        for(int r = l + k - 1; r < n; r++){
            ll dx = p[r].first - p[l].first;
            P plr[51];
            for(int i = 0; i <= r - l; i++){
                plr[i] = P(p[i + l].second, p[i + l].first);
            }
            sort(plr, plr + r - l + 1);
            ll dy = plr[k - 1].first - plr[0].first;
            ll now = dy;
            for(int i = 0; i <= r - l - k; i++){
                now += (plr[k + i].first - plr[k + i - 1].first - plr[i + 1].first + plr[i].first);
                dy = min(dy, now);
            }
            ls = min(ls, dx * dy);
        }
        ans = min(ans, ls);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define IO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
typedef long long ll;
typedef struct data {
    ll x,y;
    bool operator<(const data& a) const
    {
        return x < a.x;
    }
} stu;



ll n,m,k;
ll arr[600000][3];
ll dp[600000][3];

void solve(){
     ll x = 0;
     for (int i = 0; i < 600000; ++i)
     {
        for (int j = 0; j < 3; ++j)
        {
        dp[i][j]=x;
        arr[i][j]=x;
        }
     }
    cin >> n ;
    for (int i = 1; i <= n; ++i)
    {   
        cin >> arr[i][0] >> arr[i][1]>>arr[i][2];    
    }
    for (int i = 1; i <= n; ++i)
    {
        for(int j = 0 ; j < 3 ; j++){
            for(int h=0 ; h<3 ;h++){
                if(h!=j){
                    dp[i][j]=max(dp[i][j],arr[i][j]+dp[i-1][h]);
                }
            }
        }
    }
    ll ma=max(dp[n][0],max(dp[n][1],dp[n][2]));
    cout << ma ;
}




int main() {

        //clock_t startTime = clock();

    solve();
    //cout << double( clock() - startTime ) / (double)CLOCKS_PER_SEC<<  endl;    
    return 0;
}

Measured memory_bytes: 28416
#include <bits/stdc++.h> 
#include <chrono>
using namespace std;
 
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
 
 
//typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef long long LL;
typedef pair<long, long> PLL;
 
//container util
//------------------------------------------
#define PB emplace_back
#define MP make_pair 
#define SZ(a) int((a).size())
//repetition
//------------------------------------------
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SORT(c) sort((c).begin(),(c).end())
#define ALL(a)  (a).begin(),(a).end()
//constant
//--------------------------------------------
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

int main(){
    LL a;cin>>a;
    cout<<a*a*3<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<cstdio>
using namespace std;
int main(){
	string s;
	cin>>s;
	s=" "+s;
	int i;
	for(i=1;i<=s.length();i++){
		if((i)%2!=0){
			if(s[i]=='L')
			break;
		}
		else{
			if(s[i]=='R')
			break;
		}
	}
	if(i==s.length()+1)
	cout<<"Yes"<<endl;
	else
	cout<<"No"<<endl;
	
	return 0;
}

Measured memory_bytes: 256
/*input
3
6 10 15
*/

#include <bits/stdc++.h>
using namespace std; 
#define int long long int
// #define max(x, y) ((x) > (y) ? (x) :(y))
#define pii pair< int , int> 
#define vi vector<int>
#define fore( i ,st) for ( int i= 0 ; i < (int)(st) ; i ++)
#define REP( i , st , en ) for ( int i =st; i < (int)en; i++)
#define REPD( i , en , st ) for ( int i =en; i >= (int)st; i--)
#define SZ(a) (int)a.size()
#define all(v) v.begin() , v.end()
#define pb push_back
#define F first
#define S second
#define bug(x) cout <<__LINE__ << ":"<<__FILE__ << " : " <<   #x  << " = " << x << "\n";
#define bitch_i_m_on_fiyaah_yeahhhh ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const int mod = 1e9+7;
ostream& operator << ( ostream&  o, vector<int> s){for ( int i = 0;  i < (int)s.size() ; i++)o << s[i] << " ";o << "\n";return o;}
int  add( int a, int b){int c = a + b; if ( a> mod ) a-= mod; return c;}
void sub( int &a, int b){a = a - b;if ( a < 0) a += mod;}
int mul( int a , int b){return ((a %mod) * (b %mod) ) %mod;}
int exp( int a , int pow){ return (pow == 0 ? 1 : ( pow & 1  ? mul ( a ,exp( mul(a, a) , pow /2) ) : exp(mul(a ,a) , pow/2)));}
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }
// void in( vector<int> &v){for (int i=0;i<(int)v.size();i++)cin>>v[i];}
// void in(int &n) {cin >> n; }

const int maxn = 2e6 +5;
int factors[maxn];
int spf[maxn];
void solve( int test){
	int n;
	cin >> n ;
	vector<int> v(n);
	int g =0;
	for ( int i =2; i < maxn ; i++ ) spf[i]=i;
	for ( int i = 4 ; i < maxn ; i+=2) spf[i]=2;
	
	for ( int i =3 ; i < maxn ; i ++ ){
		if ( spf[i] == i ){
			for ( int j = i*i ; j < maxn ; j+=i ){
				if ( spf[j] == j) spf[j]=i;
			}
		}
	}





	for ( int &x :  v ) cin >> x; 
	for ( int i =0 ; i < n ; i ++ ){
		
		g= gcd( g , v[i]);
		if ( v[i] <= 1) continue;
		int tmp = v[i];
		set<int> s;
		while( tmp != 1) {
			s.insert(spf[tmp]);
			tmp /= spf[tmp];
		}
		for ( int x : s) factors[x]++;	
	}
	int ans=0;
	for ( int i =2 ; i < maxn ; i++ ){
		if ( factors[i] >= 2 ) {
			ans =1;
			break;
		}
	}
	if ( !ans ){
		cout << "pairwise coprime";
	}
	else if ( g == 1) {
		cout << "setwise coprime";
	}
	else cout << "not coprime";

}	
signed main(){
	bitch_i_m_on_fiyaah_yeahhhh
	int t =1; 
	// cin >> t;
	for ( int i = 0 ; i < t; i++)
		solve(i+1);
}

Measured memory_bytes: 34552
from math import ceil


def main():
    n = int(input())
    a = [0 for _ in range(n)]
    b = [0 for _ in range(n)]
    for i in range(n):
        a[i], b[i] = map(int, input().split())
    added = 0
    for i in range(n - 1, -1, -1):
        added += ceil((a[i] + added) / b[i]) * b[i] - (a[i] + added)
    print(added)


if __name__ == '__main__':
    main()



Measured memory_bytes: 11048
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys


def solve(s, t):
    v = [0] * (len(s) + 1)
    dp = [v]
    for _, ti in enumerate(t, 1):
        u, v = v, v.copy()
        dp.append(v)
        ll, ul = 0, 0
        for j, sj in enumerate(s, 1):
            uj = u[j]
            if sj == ti:
                v[j] = 1 + ul
                ll = 1 + ul
            else:
                if ll > uj:
                    v[j] = ll
                else:
                    ll = uj
            ul = uj
    i = len(t)
    j = len(s)
    k = dp[i][j]
    selected = []
    while k > 0:
        if dp[i - 1][j] == k:
            i -= 1
        elif dp[i][j - 1] == k:
            j -= 1
        else:
            selected.append(t[i - 1])
            k -= 1
            i -= 1
            j -= 1
    return "".join(selected[::-1])


def do_job():
    "Do the work"
    s = input()
    t = input()
    result = solve(s, t)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


Measured memory_bytes: 316888
#include<iostream>
#include<cmath>
#include<map>
#include<deque>
#include<string>
#include<algorithm>

#define all(x) (x).begin(),(x).end()
#define puts(x) cout<< x << endl;
#define rep(i,m,n) for(ll i=m;i<n;i++)
#define fore(i,a) for(auto i:a)
#define ll long long
using namespace std;
ll n,k,r,s,p;
string t;
ll ans;
ll last[100005];//g1 c2 p3
int main(){
    cin>>n>>k>>r>>s>>p;
    cin>>t;
    rep(i,0,t.size()){
        if(t[i]=='r'){
            if(i>=k){
                if(last[i-k]!=3){
                    ans+=p;
                    last[i]=3;
                }
            }else{
                ans+=p;
                last[i]=3;
            }
        }
        if(t[i]=='s'){
            if(i>=k){
                if(last[i-k]!=1){
                    ans+=r;
                    last[i]=1;
                }
            }else{
                ans+=r;
                last[i]=1;
            }
        }
        if(t[i]=='p'){
            if(i>=k){
                if(last[i-k]!=2){
                    ans+=s;
                    last[i]=2;
                }
            }else{
                ans+=s;
                last[i]=2;
            }
        }
        //puts(ans);
    }
    puts(ans);
}

Measured memory_bytes: 1280
#include <algorithm>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cassert>
#include <iostream>
#include <map>
#include <queue>
#include <sstream>
#include <string>
#include <stack>
#include <set>
#include <vector>

using namespace std;

#define all(c) ((c).begin()), ((c).end())
#define dump(c) cerr << "> " << #c << " = " << (c) << endl;
#define iter(c) __typeof((c).begin())
#define tr(i, c) for (iter(c) i = (c).begin(); i != (c).end(); i++)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i <= (int)(b); i++)

#define mp make_pair
#define fst first
#define snd second
#define pb push_back

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
typedef pair<int,int> pii;

const int INF = 1 << 29;
const double EPS = 1e-10;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
    return os<<'('<<p.first<<','<<p.second<<')';
}
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& a){
    os<<'[';
    rep(i,a.size()) os<<(i?" ":"")<<a[i];
    return os<<']';
}

typedef pair<int, pii> State;

int H, W, N;
char m[1010][1010];

int bfs(pii s, int dest, pii &ns) {
	queue<pair<int, pii> > q;
	q.push(mp(0, s));
	bool visited[1010][1010];
	memset(visited, false, sizeof(visited));
	while(!q.empty()) {
		pair<int, pii> p = q.front();
		q.pop();
		int x = p.snd.fst;
		int y = p.snd.snd;
		if (visited[y][x]) continue;
		visited[y][x] = true;
		
		if (m[y][x] == dest + '0') {
			ns = p.snd;
			return p.fst;
		}
		
		static const int dx[] = {1, 0, -1, 0};
		static const int dy[] = {0, 1, 0, -1};
		rep(d, 4) {
			int tx = x + dx[d];
			int ty = y + dy[d];
			if (tx < 0 || tx >= W || ty < 0 || ty >= H) continue;
			if (m[ty][tx] == 'X') continue;
			q.push(mp(p.fst + 1, mp(tx, ty)));
		}
	}
}

int main() {
	cin >> H >> W >> N;
	pii s;
	rep(i, H) rep(j, W) {
		cin >> m[i][j];
		if (m[i][j] == 'S') {
			s.fst = j;
			s.snd = i;
		}
	}
	
	int ans = 0;
	rep(i, N) ans += bfs(s, i + 1, s);
	
	cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 3208
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define INF 1e9
#define PI 3.14159265359
#define MOD 1000000007
#define ALL(v) v.begin(),v.end()
#define ALLR(v) v.rbegin(),v.rend()
typedef long long ll;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//isPrime
//modpow modinv
//getDigit
int main() {
  cout << fixed << setprecision(10);
  int n;
  cin >> n;
  vector<tuple<string,int,int>> a(n);
  rep(i,n){
    string s;
    int p;
    cin >> s >> p;
    p = INF - p;
    a.at(i)=make_tuple(s,p,i);
  }
  sort(ALL(a));
  rep(i,n){
    cout << get<2>(a.at(i))+1 << endl;
  }
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int width,height;
int map[21][21];
int answer;

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

void check(int x, int y, int count){
	int cx,cy;

	if(count>=answer) return;//èª10ð´¦Ä¢½çI¹

	for(int i=0 ; i<4 ; i++){//ãº¶ESûüÉ²×é
		cx = x+dx[i];
		cy = y+dy[i];
		
		if(cx<0 || cy<0 || cx>=width || cy>=height || map[cy][cx]==1){
			continue;//áQ¨ÉÔÂ©é©æÊOÉo½çcontinue
		}

		while(1){//[vÅêûüÉTõ·é
			if(map[cy][cx]==3){//S[É½çI¹
				if(answer>count)answer = count;
				return;
			}

			cx += dx[i];
			cy += dy[i];

			if(cx<0 || cy<0 || cx>=width || cy>=height){
				break;//æÊOÉo½çbreak
			}
			
			if(map[cy][cx]==1){//áQ¨ÉÔÂ©Á½çÄA
				map[cy][cx] = 0;
				check( cx-dx[i] , cy-dy[i] , count+1 );
				map[cy][cx] = 1;
				break;
			}
		}
	}
}


int main(){
	int y,x,sx,sy;

	while(1){
		//E³ÌüÍ
		cin >> width >> height;
		if(width==0 && height==0) break;//0 0¾Á½çI¹

		//zñmap[][]Élðãü
		for(y=0 ; y<height ; y++){
			for(x=0 ; x<width ; x++){
				cin >> map[y][x];
				if(map[y][x]==2){//2¾Á½çX^[gn_
					sx = x; sy = y;
				}
			}
		}
		answer = 11;
		check( sx , sy , 1 );//±ÌÖÅ²×é

		//¦ÌoÍ(answer>10¾Á½ç-1ðoÍ)
		if(answer>10) answer = -1;
		cout << answer << endl;
	}

	return 0;
}

Measured memory_bytes: 0
N, K = map(int, input().split())

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

MOD = 1000000007


def combinations(n, r, MOD):
    if (r < 0) or (n < r):
        return 0

    r = min(r, n - r)
    return fact[n] * fact_inv[r] * fact_inv[n - r] % MOD


A.sort()
fact = [1, 1]
fact_inv = [1, 1]
inv = [0, 1]

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    fact_inv.append((fact_inv[-1] * inv[-1]) % MOD)

max_sum = 0
min_sum = 0

for i, a in enumerate(A):
    # max
    if i >= K - 1:
        max_sum += a * combinations(i, K - 1, MOD)

    # min
    if i <= N - K:
        min_sum += a * combinations(N - i - 1, K - 1, MOD)

print(int((max_sum - min_sum) % MOD))


Measured memory_bytes: 20056
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
#define INF 1000000010
#define EPS 1e-9
#define F first
#define S second

#define debug(x) cout<<x<<endl;
#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define lp(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
#define int long long
#define endl "\n"

typedef pair<int,int> PII;
typedef pair<int,string> PIS;
typedef pair<string,int> PSI;


signed main(){
  cin.tie(0);	
  ios::sync_with_stdio(false);
  int n,m;
  cin>>n>>m;
  int h[n];
  rep(i,n) cin>>h[i];
  int good[n]={0};
  rep(i,m){
    int a,b;
    cin>>a>>b;
    a--;
    b--;
    if(h[a]>h[b]) good[b]++;
    else if(h[a]<h[b]) good[a]++;
    else if(h[a]==h[b]){
      good[a]++;
      good[b]++;
    }
  }
  int ans=0;
  rep(i,n){
    if(good[i]==0) ans++;
  }
  cout<<ans<<endl;

  return 0;
}


Measured memory_bytes: 5232
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <map>
#include <queue>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using namespace std;

template<class T>
constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n), b(n);
    ll ans = 0, ans1 = 0;
    for (int i = 0; i < n; ++i) {
        scanf("%d %d", &a[i], &b[i]);
        if(a[i] == 0) ans += b[i];
        if((a[i]|k) == k) ans1 += b[i];
    }
    ans = max(ans, ans1);
    for (int i = 1 << 29; i; i >>= 1) {
        if((i & k) == 0) continue;
        ll tmp = 0;
        int mask = (k^i)|(i-1);
        for (int j = 0; j < n; ++j) {
            if((a[j]|mask) == mask) tmp += b[j];
        }
        ans = max(ans, tmp);
    }
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <numeric>
#include <queue>
#include <algorithm>
#include <utility>
#include <functional>
using namespace std;

// http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1911975#1
template<typename Int = int>
struct PrimalDual {
    struct Edge {
        int dst;
        Int cap, flow, cost;
        int rev;
        Edge(int dst, Int cap, Int flow, Int cost, int rev)
            :dst(dst), cap(cap), flow(flow), cost(cost), rev(rev) {
        }
    };

    int n;
    vector<vector<Edge>> g;
    PrimalDual(int n_) : n(n_), g(vector<vector<Edge>>(n_)) {}
    void addEdge(int src, int dst, Int cap, Int cost) {
        g[src].emplace_back(dst, cap, 0, cost, g[dst].size());
        g[dst].emplace_back(src, cap, cap, -cost, g[src].size() - 1);
    }

    vector<Int> h, dist;
    vector<int> prevv, preve;
    Int solve(int s, int t, Int f) {
        Int res = 0;
        h.assign(n, 0); dist.assign(n, 0);
        prevv.assign(n, 0); preve.assign(n, 0);
        while (f > 0) {
            if (!dijkstra(s, t)) return -1;
            Int flow, cost;
            tie(flow, cost) = push(s, t, f);
            f -= flow; res += cost;
        }
        return res;
    }

    bool dijkstra(int s, int t) {
        constexpr Int INF = numeric_limits<Int>::max();
        fill(dist.begin(), dist.end(), INF);
        dist[s] = 0;
        priority_queue<pair<Int, int>> q;
        q.emplace(0, s);
        while (q.size()) {
            int d, v;
            tie(d, v) = q.top(); q.pop();
            d = -d;
            if (dist[v] < d) continue;
            for (int i = 0; i < (int)g[v].size(); ++i) {
                Edge &e = g[v][i];
                if (residue(e) > 0 && dist[e.dst] > dist[v] + e.cost + h[v] - h[e.dst]) {
                    dist[e.dst] = dist[v] + e.cost + h[v] - h[e.dst];
                    prevv[e.dst] = v;
                    preve[e.dst] = i;
                    q.emplace(-dist[e.dst], e.dst);
                }
            }
        }
        return dist[t] != INF;
    }

    pair<Int,Int> push(int s, int t, Int lim) {
        for (int i = 0; i < n; ++i) h[i] += dist[i];
        Int flow = lim;
        for (int v = t; v != s; v = prevv[v]) {
            Edge &e = g[prevv[v]][preve[v]];
            flow = min(flow, residue(e));
        }
        Int cost = flow * h[t];
        for (int v = t; v != s; v = prevv[v]) {
            Edge &e = g[prevv[v]][preve[v]];
            e.flow += flow;
            g[v][e.rev].flow -= flow;
        }
        return make_pair(flow, cost);
    }

    Int residue(const Edge& e) { return e.cap - e.flow; }
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m, f;
    cin >> n >> m >> f;
    PrimalDual<int> pd(n);
    for (int i = 0; i < m; i++) {
        int u, v, c, d;
        cin >> u >> v >> c >> d;
        pd.addEdge(u, v, c, d);
    }
    cout << pd.solve(0, n - 1, f) << endl;
}

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

int main(){
    int x,y; cin >> x >> y;
    if(2*x <= y && y <= 4*x && (y-2*x)%2 == 0) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 3636
#include <iostream>
  #include <iomanip>
  #include <algorithm>
  #include <cmath>
  #include <queue>
  #include <list>
  #include <limits>
  #include <string>
  #include <vector>
  #include <stack>
  using namespace std;
  typedef long long ll;

  typedef pair<ll, ll> curr;
  const int MOD = 998244353;


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

  ll calc(int a, int b, int p){
    if(b == 0) return 1;
    if(b % 2 == 0){
      ll d = calc(a, b/2, p);
      return (d*d)%p;
    }else{
      return (a*calc(a, b-1, p))%p;
    }

  }
  int main()
  {
    int N,K,i,_max = 0,curr;
    int S[200002];
    char c;
    bool flag = true,start = true;
    cin >> N >> K;
    S[0] = 0;
    int index = 1;
    cin >> c;
    if(c == '0') flag = start = false;
    for(i=1;i<N;i++){
      cin >> c;
      if(c == '1'&&!flag){
        flag = true;
        S[index] = i;
        index++;
      }else if(c == '0'&&flag){
        flag = false;
        S[index] = i;
        index++;
      }
    }
    S[index] = N;
    index++;
    for(i=0;i<index;i++){
      if((start && i%2==0)||(!start && i%2==1)) {
        curr = S[i+K*2+1] - S[i];
        if(i+K*2+1 >= index) curr = S[index-1] - S[i];
      }else{
        curr = S[i+K*2] - S[i]; 
        if(i+K*2 >= index) curr = S[index-1] - S[i];
      } 
      _max = max(_max, curr);
    }
    cout << _max;
  }


Measured memory_bytes: 640
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
import random
from decimal import *

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	D = inputInt()
	C = inputList()
	S = []
	for i in range(D):
		s = inputList()
		S.append(s)

	ans = []
	for i in range(D):
		bestSco = 0
		bestI = 1
		for j,val in enumerate(S[i]):
			tmpAns = ans + [j+1]
			tmpSco = findScore(tmpAns, S, C)
			if bestSco < tmpSco:
				bestSco = tmpSco
				bestI = j+1
		ans.append(bestI)

	for i in ans:
		print(i)


def findScore(ans, S, C):
	scezhu = [inf for i in range(26)]
	sco = 0
	for i,val in enumerate(ans):
		tmp = S[i][val-1]
		scezhu[val-1] = i
		mins = 0
		for j,vol in enumerate(C):
			if scezhu[j] == inf:
				mins = mins + (vol * (i+1))
			else:
				mins = mins + (vol * ((i+1)-(scezhu[j]+1)))
		tmp -= mins
		sco += tmp
	return sco

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()


Measured memory_bytes: 84908
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
int main(){
    int p, q, r;
    cin >> p >> q >> r;
    cout << q+p+r - max({p, q, r}) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/numeric>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#define oo 0x3f3f3f3f
#define OO 0x3f3f3f3f3f3f3f3f
#define popcount(n) __builtin_popcount(n)
#define popcountll(n) __builtin_popcountll(n)
#define long long long

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef vector<int> vi;
typedef vector<pair<int, int>> vii;

const double PI = acos(-1.0), EPS = 1e-9;
const int MAXN = 100005, MAXM = 102, Mod = 998244353, MAXLog = 20;
 
int main() {
#ifndef ONLINE_JUDGE
//    freopen("input.txt", "rt", stdin);
//    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0), cout.precision(10), cout
            << fixed;

    int a, b;
    cin >> a >> b;
    if (max(a, b) < 10) {
        cout << a * b << '\n';
    } else {
        cout << -1 << '\n';
    }

    return 0;
}


Measured memory_bytes: 256
/*
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
*/

#ifdef LOCAL
#include "debug.h"
#else
#include<bits/stdc++.h>
using namespace std;
#define debug(x...)
#endif
 
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> 
using ordered_set= tree<T, null_type, 
		less<T>, 
		rb_tree_tag, tree_order_statistics_node_update> ;
template<class T> 		
using ordered_mset= tree<T, null_type, 
		less_equal<T>, 
		rb_tree_tag, tree_order_statistics_node_update> ;
		
*/
 
/*
 
PBDS
-------------------------------------------------
			0 based indexing
-------------------------------------------------			 
1) insert(value)
2) erase(value)
3) order_of_key(value) // Number of items strictly smaller than value
4) *find_by_order(k) : K-th element in a set (counting from zero)
 
*/
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());	

void solve()
{
	string x;
	cin>>x;
	
	ll sum=0;
	for(auto it: x) sum+=(it-'0');
	
	cout<<(sum%9?"No":"Yes");
}		

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int testcase=1;
	//cin>>testcase;
	
	for(int i=1;i<=testcase;i++)
	{
		//cout<<"Case "<<i<<": ";
		solve();
	}
	
	#ifdef LOCAL
	cerr<<"\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms\n";
	#endif
	
	
	return 0;
}


Measured memory_bytes: 3736
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int n,i,sum=0,j;
    cin>>n;
    vector<long long int>a(n+1,0);
    for(i=1;i<=n;i++)
    {
        for(j=0;j<=n;j+=i)
        {
            a[j]++;
        }
    }
    for(i=1;i<=n;i++)
    {
        sum+=a[i]*i;
    }
    cout<<sum;
}


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

static const int INF = 1001001001;

using namespace std;

int main()
{
	int n, l;
	cin >> n >> l;
	vector<string> s(n);
	for (int i = 0; i < n; ++i) {
		cin >> s[i];
	}
	sort(s.begin(), s.end());
	for (int i = 0; i < n; ++i) {
		cout << s[i];
	}
	cout << endl;
	return 0;
}


Measured memory_bytes: 256
N = int(input())
D = list(map(int,input().split())) + [0]
from collections import Counter

ctr = Counter(D)
if ctr[0] >= 2 or ctr[12] >= 2:
    print(0)
    exit()
if any(v >= 3 for v in ctr.values()):
    print(0)
    exit()

ans = 0
for b in range(1<<11):
    ts = [0] * 24
    ts[0] = 1
    if ctr[12]: ts[12] = 1
    for i in range(11):
        t = i+1
        if ctr[t] == 0: continue
        if ctr[t] == 2:
            ts[t] = ts[24-t] = 1
            continue
        if b&(1<<i):
            ts[t] = 1
        else:
            ts[24-t] = 1
    tt = [i for i,b in enumerate(ts) if b]
    tmp = 24 - tt[-1]
    for t1,t2 in zip(tt,tt[1:]):
        tmp = min(tmp, t2-t1)
    ans = max(tmp, ans)
print(ans)

Measured memory_bytes: 3444
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
int main()
{
    int a,b,c;
    cin >> a >> b >> c;
    cout << setprecision(10) << a * sin(c / 360.0 * 2 * M_PI) * b * 0.5 << endl;
    cout << a + b + sqrt(a * a + b * b - 2 * a * b * cos(c / 360.0 * 2 * M_PI)) << endl;
    cout << b * sin(c / 360.0 * 2 * M_PI) << endl;
}

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

int main(){
    ll n;
    cin>>n;
    ll a[n];
    for(int i=0;i<n;++i)cin>>a[i];     
    ll amount = 1000,stocks = 0,first=-1,second=-1;
    int i=0;
    
    while(i<n){
             if(i==n-1 && first==-1)break;
             if(i==n-1 && first!=-1){
                 second = i;
                 stocks = amount/a[first];
                 amount = amount%a[first] + stocks*(a[second]);
                 break;
             }
             if(a[i]<a[i+1] && first==-1){
                first = i;
                i++;
                continue;
            }
            if(a[i]>a[i+1] && first!=-1){
                second = i;
                stocks = amount/a[first];
                amount = amount%a[first] + stocks*(a[second]);
                first = -1;
            }
            i++;
    }
    cout<<amount;


    return 0;
}


Measured memory_bytes: 3608
import math
import numpy as np
x = int(input())
height = list(map(lambda x: int(x), input().split()))  
cands = [0 for i in range(len(height))]


count = 0
  
for i in range(len(height)):
  if i-height[i] >= 0:
    count += cands[i-height[i]]
      
  if i+height[i] < len(height):
    cands[i+height[i]] += 1

print(count)
	    


Measured memory_bytes: 51008
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
const int maxn=1e6+10;
const int mod=1e9+7;
const double pi=3.1415926535;
int w[3005],v[3005];
int dp[3005][2];




int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,t;
    cin>>n>>t;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i]>>v[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=t-1;j>=0;j--)
        {
            for(int x=1;x>=0;x--)
            {
                if(x==0)
                {
                    if(j>=w[i])
                    {
                        dp[j][x]=max(dp[j][x],dp[j-w[i]][x]+v[i]);
                    }
                }
                else
                {
                    dp[j][x]=max(dp[j][x],dp[j][0]+v[i]);
                    if(j>=w[i])
                    {
                        dp[j][x]=max(dp[j][x],dp[j-w[i]][x]+v[i]);
                    }
                }
            }
        }
    }
    cout<<dp[t-1][1]<<'\n';






}


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

int bubbleSort(int A[], int N){
    int t = 0;
    bool flag = 1;
    for(int i = 0; flag; i++){
        flag = 0;
        for(int j = N - 1; j >= i + 1; j--){
            if(A[j] < A[j-1]){
                swap(A[j], A[j-1]);
                flag = 1;
                t++;
            }
        }
    }
    return t;
}

int main(){
    int A[100], N, t;
    cin >> N;
    for(int i = 0; i < N; i++) cin >> A[i];
    
    t = bubbleSort(A, N);
    
    for(int i = 0; i < N; i++){
        if(i > 0) cout << " ";
        cout << A[i];
    }
    
    cout << endl << t << endl;
    
    return 0;
    
}


Measured memory_bytes: 3104
#include<bits/stdc++.h>
using namespace std;
///Welcome to Nasif's Code
#define bug printf("bug\n");
#define bug2(var) cout<<#var<<" "<<var<<endl;
#define co(q) cout<<q<<endl;
#define all(q) (q).begin(),(q).end()
typedef long long int ll;
typedef unsigned long long int ull;
const int MOD = (int)1e9+7;
const int MAX = 1e6;
#define pi acos(-1)
#define inf 1000000000000000LL
#define FastRead    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
vector< pair <int,int> >graph[MAX];
int cost[MAX];
void dijkstra(int src)
{
    priority_queue< pair<int,int> >q;
    q.push(make_pair(0,src));
    cost[src]=0;
    while(!q.empty())
    {
        int parents_money=q.top().first*-1;
        int parent=q.top().second;
        q.pop();
        for(int i=0; i<graph[parent].size(); i++)
        {
            int childs_money=graph[parent][i].first;
            int child=graph[parent][i].second;
            if(cost[child]==-1 || cost[child]>childs_money+cost[parent])
            {
                cost[child]=childs_money+cost[parent];
                q.push(make_pair(-1*cost[child],child));
            }
        }
    }
}
void create_graph(int n)
{
    for(int i=1; i<=n; i++)
    {
        int u=i%n;
        int v=(i+1)%n;
        graph[u].push_back({1,v});
        v=(i*10)%n;
        graph[u].push_back({0,v});
    }
}
int main()
{
    FastRead
    //freopen("output.txt", "w", stdout);
    memset(cost,-1,sizeof(cost));
    int n;
    cin>>n;
    create_graph(n);
    dijkstra(1);
    cout<<cost[0]+1<<endl;
    return 0;
}


Measured memory_bytes: 34360
import java.lang.reflect.Array;
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int X = sc.nextInt();
		int[] x = new int[N+1];
		x[0] = X;
		for (int i = 1; i < N+1; i++) {
			x[i] = sc.nextInt();
		}
		Arrays.sort(x);
		int[] y = new int[N];
		for (int i = 0; i < N; i++) {
			y[i] = x[i+1] - x[i];
		}
		if (y.length==1) {
			System.out.println(x[1]-x[0]);
			return;
		}
		// 最大公約数
		int g = gcd(y[0], y[1]);
		for (int i = 1; i < y.length-1; i++) {
			g = gcd(g, y[i+1]);
		}
		System.out.println(g);						
		
		
		// 入力
		/*
		String S = sc.next();                
		String T = sc.next();                
		
		for (int i = 0; i < S.length(); i++) {
			if (!S.substring(i,i+1).equals(T.substring(i,i+1))) {
				if (S.indexOf(T.substring(i,i+1)) == -1) {
					S = S.replace(S.substring(i,i+1), T.substring(i,i+1));
				} else {
					String s = S.substring(0, S.length());
					StringBuilder sb = new StringBuilder("");
					for (int j = 0; j < s.length(); j++) {
						if (s.substring(j, j+1).equals(S.substring(i, i+1))) {
							sb.append(T.substring(i, i+1));
						} else if (s.substring(j, j+1).equals(T.substring(i, i+1))) {
							sb.append(S.substring(i, i+1));							
						} else {
							sb.append(s.substring(j, j+1)); 
						}
					}
					S = sb.toString();
				}
			}
		}
		if(S.equals(T)){
			System.out.println("Yes");			
		} else {
			System.out.println("No");			
		}
	*/
	}	
	private static int gcd(int x, int y){
		if(y == 0){
			return x;
		}
		return gcd(y, x % y);
	}
	
}


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

#define ll long long
const char newl = '\n';

//***---***---***---Useless Code---***---***---***//

template<class T> void read(T &t) {
	cin >> t;
}
template<class A, class...B> void read(A& a, B&... b) {
	read(a);
	read(b...);
}
template<class T> void read(vector<T>& vt) {
	for(auto &a : vt)
		read(a);
}

string to_string(bool b) { return (b ? "true" : "false"); }
string to_string(char c) { return string(1, c); }
string to_string(string s) { return s; }
string to_string(const char* str) { return string(str); }
string to_string(vector<bool> vt) {
	string ret;
	bool ft = 1;
	for(bool x : vt) {
		if(!ft)
			ret += ' ';
		ft = 0;
		ret += char('0' + x);
	}
	return ret;
}
template<class T> string to_string(vector<T> vt) {
	string ret;
	bool ft = 1;
	for(auto a : vt) {
		if(!ft)
			ret += ' ';
		ft = 0;
		ret += to_string(a);
	}
	return ret;
}

template<class T> void write(T t) {
	cout << to_string(t);
}
template<class A, class... B > void write(A a, B... b) {
	write(a);
	if(sizeof...(b))
		write(' ');
	write(b...);
}
void print() {
	write(newl);
}
template<class A, class... B> void print(A a, B... b) {
	write(a);
	if(sizeof...(b))
		write(' ');
	print(b...);
}

//***---***---***---Useless Code---***---***---***//

int n;

void solve() {
	ll ans = 1000, cnt = 0;
	read(n);
	vector<int> a(n);
	read(a);
	for(int i = 1; i < n; ++i) {
		if(a[i-1] < a[i]) {
			cnt = ans / a[i-1];
			ans += cnt * (a[i] - a[i - 1]);
		}
	}
	print(ans);
}

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

	solve();
}


Measured memory_bytes: 3712