akhauriyash/Code-Regression huggingface dataset:
uses crt;
var
        g,h: array [0..100000] of longint;
        n,k, carry,i,j,f: longint;
begin

        read (n); readln (k);
        for i:=1 to n do read(g[i]);
        readln;
        fillchar (h, sizeof (h), 0);
        h[1]:= 0;
        h[2]:= abs (g[2] - g[1]);
        for i:=3 to n do
        begin
                f:= i-k; if (i-k < 1) then f:= 1;
                h[i]:= abs(g[i] - g[i-1]) + h[i-1];
                while f  < i do
                begin
                        carry:= abs(g[i] - g[f]) + h[f];
                        if carry  <= h[i] then h[i]:= carry;
                        inc(f);
                end;
        end;
        write (h[n]);
        readln;
end.

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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define FOR(i, a, b) for (int i = a; i < (int)b; ++i)
#define rrep(i, n) for (int i = ((int)n - 1); i >= 0; --i)

using ll = long long;
using ld = long double;

const ll INF = 1e18;
const int Inf = 1e9;
const double EPS = 1e-9;
const ll MOD = 1e9 + 7;

vector<pair<ll, int> > primeFactorize(ll n) {
  vector<pair<ll, int> > res;
  for (ll i = 2; i * i <= n; ++i) {
    if (n % i) continue;
    res.push_back(make_pair(i, 0));
    while (n % i == 0) {
      n /= i;
      res.back().second++;
    }
  }
  if (n != 1) res.push_back(make_pair(n, 1));
  return res;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(0);
    ll n;
    cin >> n;
    auto v = primeFactorize(n);
    if (v.size() == 0) {
        cout << 0 << endl;
        return 0;
    }
    ll res = 0;
    rep (i, v.size()) {
        for (int j = 1; ; ++j) {
            int t = j * (j + 1) / 2;
            if (t >= v[i].second) {
                res += j;
                if (t != v[i].second) res--;
                break;
            }
        }
    }
    cout << res << endl;
    
    return 0;
}



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

int selectionSort(int a[], int n) {
    int total_swap = 0;

    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++) {
            if (a[min] > a[j]) min = j;
        }

        if (i != min) {
            swap(a[i], a[min]);
            total_swap++;
        }
    }

    return total_swap;
}

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

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

    int count = selectionSort(a, n);

    for (int i = 0; i < n; i++) {
        if (i) cout << " ";
        cout << a[i];
    }

    cout << endl << count << endl;

    return 0;
}



Measured memory_bytes: 3112
lab = list(map(int,input().split()))
dir = str(input())

for i in range(len(dir)):
    dcopy = lab.copy()
    if dir[i] == 'E':
        lab[0]=dcopy[3]
        lab[2]=dcopy[0]
        lab[3]=dcopy[5]
        lab[5]=dcopy[2]
    elif dir[i] == 'N':
        lab[0]=dcopy[1]
        lab[1]=dcopy[5]
        lab[4]=dcopy[0]
        lab[5]=dcopy[4]
    elif dir[i] == 'S':
        lab[0]=dcopy[4]
        lab[1]=dcopy[0]
        lab[4]=dcopy[5]
        lab[5]=dcopy[1]
    else:
        lab[0]=dcopy[2]
        lab[2]=dcopy[5]
        lab[3]=dcopy[0]
        lab[5]=dcopy[3]
print(lab[0])


Measured memory_bytes: 5604
n = int(input())
lst = list(map(int,input().split()))
ans = 0
for i in range (n - 2):
  for j in range (i + 1, n - 1):
    for k in range (j + 1, n):
      lst2 = [lst[i], lst[j], lst[k]]
      if (lst2[0] != lst2[1] and lst2[0] != lst2[2] and lst2[1] != lst2[2]):
        if (lst2[0] < lst2[1] + lst2[2] and lst2[1] < lst2[0] + lst2[2] and lst2[2] < lst2[0] + lst2[1]):
          ans = ans + 1
print(ans)


Measured memory_bytes: 9204
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b;
  cin >> a >> b;
  if(a<=0&&b>=0){
    cout << "Zero" << endl;
  }
  else if(a>0){
    cout << "Positive" << endl;
  }
  else if((b-a)%2==1){
    cout << "Positive" << endl;
  }
  else{
    cout << "Negative" << endl;
  }
}

Measured memory_bytes: 256
object Main {
  def main(args: Array[String]): Unit = {
    val days  = scala.io.StdIn.readInt
    val rates = scala.io.StdIn.readLine.split(" ").map{_.toInt}

    var have_money = 1000L
    var have_stock = 0L

    ( 0 until days - 1 ).foreach{ i =>
      if( rates( i ) > rates( i + 1 ) ) {
        have_money += have_stock*rates( i )
        have_stock = 0L
      }
      if( rates( i ) < rates( i + 1 ) ) {
        have_stock += have_money/rates( i )
        have_money = have_money%rates( i )
      }
    }

    have_money += have_stock*rates.last

    println( have_money )
  }
}

Measured memory_bytes: 54552
import java.util.*;
import java.math.*;

class Main{
    
    public static void main(String arg[]){
        
        Scanner sc = new Scanner(System.in);
        
        int a = sc.nextInt();
        
        BigInteger ar = new BigInteger("0");
        BigInteger br = new BigInteger("0");
        
        for(int i=1;i<=a;i++){
            
            ar = sc.nextBigInteger();
            br = sc.nextBigInteger();
            
            if(ar.toString().length()>80)System.out.println("overflow");
            else if(br.toString().length()>80)System.out.println("overflow");
            else if(ar.add(br).toString().length()>80)System.out.println("overflow");
            else System.out.println(ar.add(br));
        }
        
        
        
    }
}

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

int fact(int a, int b){
    int sum = 1;
    for(int i = 1;i <= a;i++)sum *= i;
    sum *= b;
    return sum;
}

int main(void){
    int n;
    cin >> n;
    int a[n],b[n],c[n],d[n];
    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;i++){
        c[i] = 1;
        d[i] = 1;
    }
    int P = 0,Q = 0;
    for(int i = 0;i < n;i++){
        //cout << fact(((n-1)-i),1) << endl;
        int j = 0;
        c[a[i]-1]--;
        for(int k = 0;k < a[i];k++)if(c[k] != 0)j++;
        //for(int k = 0;k < n;k++)cout << c[k] << " ";
        //cout << endl << j << endl;;
        P += fact(((n-1)-i),j);
        //cout << fact(((n-1)-i),j) << endl;
    }
    
    for(int i = 0;i < n;i++){
        int j = 0;
        d[b[i]-1]--;
        for(int k = 0;k < b[i];k++)if(d[k] != 0)j++;
        Q += fact(((n-1)-i),j);
    }
    cout << abs(P-Q);
}

Measured memory_bytes: 256
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from cmath import pi, rect

def _fft(A, inverse = False):
    step = N
    for k in range(logN):
        step >>= 1
        w = rect(1, pi / (1 << k) * (1 - 2 * inverse))
        wj = 1
        nA = [0] * N
        for j in range(1 << k):
            for i in range(1 << logN - k - 1):
                s, t = i + j * step, i + j * step + (N >> 1)
                ps, pt = i + j * step * 2, i + j * step * 2 + step
                nA[s], nA[t] = A[ps] + A[pt] * wj, A[ps] - A[pt] * wj
            wj *= w
        A = nA
    return A

def convolution(f, g):
    Ff, Fg = _fft(f + [0] * (N - len(f))), _fft(g + [0] * (N - len(g)))
    fg = _fft([a * b / N for a, b in zip(Ff, Fg)], inverse = True)
    del fg[len(f) + len(g) - 1:]
    return fg

P = 200_003
logN = (2 * P - 1).bit_length()
N = 1 << logN
r = 2
exp = [1] * (P - 1)
log = [0] * P

e = 1
for i in range(1, P - 1):
    e *= r
    e %= P
    exp[i] = e
    log[e] = i

def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    B = [0] * P
    for a in A:
        if a == 0:
            continue
        B[log[a]] += 1
    C = [0] * P
    for i, b in enumerate(convolution(B, B)):
        C[exp[i % (P - 1)]] += round(abs(b))
    for a in A:
        C[(a * a) % P] -= 1
    ans = 0
    for i in range(1, P):
        ans += i * C[i] // 2
    print(ans)
resolve()

Measured memory_bytes: 358160
#include<iostream>
#include<cstdio>
#define MN 100000
using namespace std;
inline int read()
{
	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,a[MN+5];
long long l=2,r=2;
int main()
{
	n=read();
	for(int i=1;i<=n;++i) a[i]=read();
	for(int i=n;i;--i)
	{
		long long L=(l-1)/a[i],R=r/a[i];
		if(L==R) return 0*puts("-1");
		l=(L+1)*a[i],r=R*a[i]+a[i]-1;
	}
	printf("%lld %lld\n",l,r);
	return 0;
}



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

int main() {
  int N;
  string s;
  cin >> N >> s;

  int cnt[2] = {};
  for (int i = 0; i < N; i++) {
    if (s[i] == 'R') cnt[0]++;
    else cnt[1]++;
  }

  if (cnt[0] > cnt[1]) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	int a,b,c,d;
	scanf("%d %d %d %d",&a,&b,&c,&d);
	a=a*b;
	c=c*d;
	if(a>c) printf("%d\n",a);
	else printf("%d\n",c);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("unroll-loops") 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#define int long long
#define fr(i,a,b) for(int i = a ; i <= b ; ++i)
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define pb push_back
#define fst first
#define snd second
using namespace __gnu_pbds;
using ordered_set =
 tree<int, null_type,less<int>,
 rb_tree_tag,tree_order_statistics_node_update>;
//find_by_order(k):returns iterator to kth element starting from 0
//order_of_key(k):returns count of elements strictly smaller than k
typedef long long ll;typedef pair<int, int> pii;
typedef vector<int> vi;typedef long double ld;
template<class T>
using min_heap = priority_queue<T,vector<T>,greater<T>>; 
template<typename T> T gcd(T a, T b){return(b?__gcd(a,b):a);}
template<typename T> T lcm(T a, T b){return(a*(b/gcd(a,b)));}
template<class T> void re(T& x) { cin >> x; }
template<typename T> 
void remdup(vector<T>& v) {
	sort(all(v)); v.erase(unique(all(v)), v.end());
}
template<typename T> void re(vector<T> &v) {trav(i,v) cin >> i;}
template<class H, class... T> void re(H& h, T&... t) { re(h); re(t...); }
void unsyncIO() { ios_base::sync_with_stdio(0); cin.tie(0); }
#ifdef np
#include "C:\Users\navodit\Desktop\mycodes\pr.h"
#else
#define trace(...)
#endif

#define MOD 1000000007  





void solve(){
	int n; re(n);
	vector<pii> wrk(n);
	rep(i,0,n){
		re(wrk[i].snd,wrk[i].fst);
	}
	sort(all(wrk));
	int done = 0 ; 
	bool ok = 1 ;
	trav(i,wrk){
		done+=i.snd;
		if(done > i.fst){
			ok = 0;
			break;
		}
	}
	if(ok) cout << "Yes\n";
	else cout << "No\n";
}

signed main() {
	unsyncIO();
	int tt =1 ;
	// cin >> tt;
	rep(i,0,tt) solve();













#ifdef np
	cout <<endl<<endl<< "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}


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

using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    vector<vector<int> > s(M);

    for (int i = 0; i < M; i++) {
        int k;
        cin >> k;
        for (int j = 0; j < k; j++) {
            int number_switch = 0;
            cin >> number_switch;
            number_switch--;
            s[i].push_back(number_switch);

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

    int ans = 0;
    for (int bit = 0; bit < (1 << N); bit++) {
        bool on = true;
        for (int i = 0; i < M; i++) {
            int number_on = 0;
            for (auto v : s[i]) {
                if (bit & (1 << v)) number_on++;
            }
            if (number_on % 2 != p[i]) {
                on = false;
            }
        }
        if (on) ans++;
    }
    cout << ans;
} 

Measured memory_bytes: 256
/**********************************************
 * author : deepak nayan
 * file   : e:/Solutions/atcoder/abc120_a.cpp
 * time   : Fri May  1 14:48:02 2020
 * quest  : A - Favorite Sound
 *********************************************/
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>

using namespace std;

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int a, b, c;
  cin >> a >> b >> c;
  cout << min(c, b / a) << "\n";
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
const long long mod = 1e9+7;
const int dx[8] = {0,1,0,-1,1,1,-1,-1};
const int dy[8] = {1,0,-1,0,1,-1,1,-1};
//////////////////////////////////

// ABCACCBABCBCAABCB
// AX ACCB AXXAAX B
// AXXAAX
// XAXAAX
// XXAAAX
int main() {
    string s; cin >> s;
    s += " ";
    string t = "";
    for(int i=0; i<s.size()-1; i++) {
        if(s[i] == 'B' && s[i+1] == 'C') {
            t += "X";
            i++;
        }else{
            t += s[i];
        }
    }
    int n = t.size();
    long long cnt = 0;
    int a = 0;
    for(int i=0; i<n; i++) {
        if(t[i] == 'A') a++;
        else if(t[i] == 'X') {
            cnt += a;
        }else {
            a = 0;
        }
    }
    cout << cnt << endl;
    return 0;
}




// EOF


Measured memory_bytes: 900
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
  int n;
  for(;cin>>n,n;)
    {
      for(;n--;)
	{
	  int data[3][4];
	  memset(data,0,sizeof(data));
	  for(int i=0;i<2;i++)
	    for(int j=0;j<4;j++)
	      cin>>data[i][j];
	  
	  for(int i=0;i<4;i++)
	    for(int j=0;j<4;j++)
	      {
		int tmp=data[0][i]*data[1][j];
		if(i==0)
		  data[2][j]+=tmp;
		else if (j==0)
		  data[2][i]+=tmp;
		else if(i==j)
		  data[2][0]-=tmp;
		else if(i==1&& j==2)
		  data[2][3]+=tmp;
		else if(i==1&& j==3)
		  data[2][2]-=tmp;
		else if(i==2&& j==1)
		  data[2][3]-=tmp;
		else if(i==2&& j==3)
		  data[2][1]+=tmp;
		else if(i==3&& j==1)
		  data[2][2]+=tmp;
		else if(i==3&& j==2)
		  data[2][1]-=tmp;
	      }
	  cout<<data[2][0]<<" "<<data[2][1]<<" "<<data[2][2]<<" "<<data[2][3]<<endl;
	}
    }

}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#define PI 3.14159265359
#define NIL -1
using namespace std;
const int64_t MOD = 1e9 + 7;

int main() {
	int N;
	cin >> N;
	
	int64_t p = 1;
	for (int i = 1; i <= N; i++) {
		p = p % MOD * i % MOD;
	}

	cout << p << endl;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
#include <algorithm>
#include <cctype>
using namespace std;
int main() {
string S; 
cin >> S;
string ans = "AC"; 
if(S.at(0) != 'A') {ans = "WA";
} 
int M = 100; 
for(int i = 2; i <= S.size() - 2; ++i){
if(S.at(i) == 'C') {M = i; 
break; }
}
if(M == 100) {ans = "WA"; 
}
else{
for(int i = 1; i <= M-1; ++i){
if(islower( S.at(i) ) == 0) {ans = "WA"; 
break; }
}
for(int i = M+1; i < S.size(); ++i){
if(islower( S.at(i) ) == 0) {ans = "WA"; 
break; }
}
}
cout << ans << endl; 
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;

#define EACH(i,a) for (auto& i : a)
#define FOR(i,a,b) for (ll i=(a);i<(b);i++)
#define RFOR(i,a,b) for (ll i=(b)-1;i>=(a);i--)
#define REP(i,n) for (ll i=0;i<(n);i++)
#define RREP(i,n) for (ll i=(n)-1;i>=0;i--)
#define debug(x) cout<<#x<<": "<<x<<endl
#define pb push_back
#define ALL(a) (a).begin(),(a).end()

const ll linf = 1e18;
const int inf = 1e9;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
	EACH(x,vec) is >> x;
	return is;
}
template<typename T>
ostream& operator<<(ostream& os, vector<T>& vec) {
	REP(i,vec.size()) {
		if (i) os << " ";
		os << vec[i];
	}
	return os;
}
template<typename T>
ostream& operator<<(ostream& os, vector< vector<T> >& vec) {
	REP(i,vec.size()) {
		if (i) os << endl;
		os << vec[i];
	}
	return os;
}

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

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	ll a, b;
	while (cin >> a >> b) {
		cout << gcd(a, b) << " " << a * b / gcd(a, b) << endl;
	}
}

Measured memory_bytes: 3108
#include <bits/stdc++.h>
using namespace std;
const long double PI = acos(-1);
typedef long long ll;
typedef pair<int64_t,int64_t> pll;
int dx[]={1,-1,0,0,1,-1,1,-1};
int dy[]={0,0,1,-1,1,-1,-1,1};
#define INF (2147483647)
#define mod (1000000007)
#define limit (7368791)
#define rep(i,a,b) for (int64_t i = (a); i < (b); i++)
#define REP(i,n) rep(i,0,n)
#define ALL(a) begin(a),end(a)
#define sz(s) (s).size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second


void solve(){
    int n;cin>>n;
    int a[n+1];REP(i,n)cin>>a[i];a[n]=0;
    ll ans=0;ll tem=0;
    REP(i,n+1){
        if(a[i]==0){ans+=tem/2;tem=0;}
        tem+=a[i];
    }
    cout<<ans<<endl;
}
int main()
{
    cin.tie(0);
	ios::sync_with_stdio(false);
    solve();
    return 0;
}


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

int a[100005],ans,n,f[100005][2];
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%d",&a[i]);
	for(int k=1<<29;k;k>>=1){
		for(int i=0,j=0;i<n;i=j){
			if(a[i]<=k){
				j=i+1;continue;
			}
			for(j++;j<n&&a[j]==k<<1;j++);
			if(j<n&&a[j]>k)j++;
			ans++;
		}
		for(int i=0;i<n;i++)if(a[i]>k)a[i]=k;
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 640
#include<stdio.h>
int main(void)
{
	int n,x;
	while (1){
		scanf("%d",&n);
		if(n==-1) break;
		if(n<=10) printf("3130\n");
		if(n>10&&n<20){
			x=n-10;
			printf("%d\n",4280-(x*125+1150));
		}
		if(n>20&&n<30){
			x=n-20;
			printf("%d\n",4280-(x*140+2400));
		}
		if(n>30){
			x=n-30;
			printf("%d\n",4280-(x*160+3800));
		}
		if(n==20) printf("1880\n");
		if(n==30) printf("480\n");
	}
	return 0;
}	

Measured memory_bytes: 2592
#include<bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    cin>>s;
    if (s.find('7') !=string::npos) {
         cout << "Yes";
     }
	else
	cout<<"No";

}


Measured memory_bytes: 3648
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define IREP(i,n) for(int i=n-1;i>=0;i--)


using namespace std;
int main(){
	int n;
	cin >> n;
	vector<int> v;
	vector<int> v1;
	bool state=false;
	REP(i,n){
		int a;
		cin >> a;
		if(i%2==0){
			v.push_back(a);
			state=true;
		}
		else{
			v1.push_back(a);
			state=false;
		}
	}
	if(state==true){
		reverse(v.begin(),v.end());
		REP(i,v.size()){
			cout << v[i] << " ";
		}
		REP(i,v1.size()){
			if(i==v1.size()-1){
				cout << v1[i] << endl;
			}
			else{
				cout << v1[i] << " ";
			}
		}
	}
	else{
		reverse(v1.begin(),v1.end());
		REP(i,v1.size()){
			cout << v1[i] << " ";
		}
		REP(i,v.size()){
			if(i==v.size()-1){
				cout << v[i] << endl;
			}
			else{
				cout << v[i] << " ";
			}
		}
	}
}

Measured memory_bytes: 3188
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<iomanip>
#include<set>
#include<queue>

using namespace std;

int main()
{
	int n,m;
	cin >> n >> m;
	vector<int> a(n);
	for(int i=0;i<n;i++)
		cin >> a[i];
	sort(a.begin(),a.end());
	vector<pair<int,int> > cb(m);
	for(int i=0;i<m;i++)
	{
		int b,c;
		cin >> b >> c;
		cb[i]=make_pair(c,b);
	}

	sort(cb.begin(),cb.end());
	reverse(cb.begin(),cb.end());

	vector<int> ch(n,0);

	int itr=0;
	for(int i=0;i<cb.size();i++)
	{
		for(int j=0;j<cb[i].second;j++)
		{
			if(itr>=n)break;
			ch[itr]=cb[i].first;
			itr++;
		}
		if(itr>=n)break;
	}
	
	itr=0;
	for(int i=0;i<n;i++)
	{
		if(a[i]<ch[itr])
		{
			a[i]=ch[itr];
			itr++;
		}
	}

	long long ans=0;
	for(int i=0;i<n;i++)
	{
//		cout << a[i] << endl;
		ans+=a[i];
	}

	cout << ans << endl;







}

Measured memory_bytes: 1792
<?php
class Scanner {
    private $arr = [];
    private $count = 0;
    private $pointer = 0;
    public function next() {
        if($this->pointer >= $this->count) {
            $str = trim(fgets(STDIN));
            $this->arr = explode(' ', $str);
            $this->count = count($this->arr);
            $this->pointer = 0;
        }
        $result = $this->arr[$this->pointer];
        $this->pointer++;
        return $result;
    }
    public function hasNext() {
        return $this->pointer < $this->count;
    }
    public function nextInt() {
        return (int)$this->next();
    }
    public function nextDouble() {
        return (double)$this->next();
    }
}
$N = fgets(STDIN);
$A = array();
$sc = new Scanner();
for($i=0;$i<$N; $i++){
    $A[$i] = $sc->nextInt();
    if($A[$i] %2 == 0){
        if(($A[$i] %3 != 0)&&($A[$i] %5 != 0)){
            printf("DENIED");
            exit;
        }
    }
}

printf("APPROVED");


Measured memory_bytes: 3576
import java.util.Scanner;

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

    int a = scanner.nextInt();
    int b = scanner.nextInt();
    if (a < b) {
      for (int i = 0; i < b; i++) System.out.print(a);
    } else {
      for (int i = 0; i < a; i++) System.out.print(b);
    }
    System.out.println();
  }
}


Measured memory_bytes: 21844
n = gets.to_i
ps = [0, *gets.split.map(&:to_i)]

v = ps.each_with_index.with_object(Array.new(n + 1, 1)) do |(p, i), arr|
  arr[p] = 0 if p == i
end[1..-1]

ans = 0
n.times do |i|
  next if v[i] == 1

  v[i + 1] = 1
  ans += 1
end

puts ans


Measured memory_bytes: 15092
//# pragma GCC optimize ("O2")
#include<iostream>
#include<algorithm>
#include<bitset>
#include<climits>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<deque>
#include<climits>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<vector>
#include<iomanip>
#include<sstream>
#define out(i,a,now) for(int i=a.be[now],to=a.v[i];i;i=a.ne[i],to=a.v[i])
#define fo(i,a,b) for(i=a;i<=b;i++)
#define max(a,b) (a>b?a:b)
#define min(a,b) (a>b?b:a)
#define mp(a,b) make_pair(a,b)
#define qk(x) memset(x,0,sizeof(x))
#define RG register
#define gs(x) (tr[tr[x].f].son[1]==x)
#define lb(x) (x&(-x))
#define mid ((l+r)>>1)
#ifdef Mogician
#endif
using namespace std;
typedef long long LL;
typedef double DB;
template <class T> void cmax(T &a,T b)
{
    a=max(a,b);
}
template <class T> void cmin(T &a,T b)
{
    a=min(a,b);
}
template <class T> void swp(T &a,T &b)
{
	T temp=a; a=b; b=temp;
}
const LL maxn=2100,kcz=1000000007;
struct edge
{
	LL u,v,w;
	bool operator <(const edge a) const
	{
		return w<a.w;
	}
}e[maxn];
LL ma[maxn][maxn],in_mst[maxn],mst[maxn],n,m,t,x,dif[3],ans;
struct adj_list
{
	LL be[maxn],ne[maxn<<1],v[maxn<<1],w[maxn<<1],cnt;
	adj_list()
	{
		qk(be); cnt=0;
	}
	void add(LL x,LL y,LL z)
	{
		v[++cnt]=y;
		w[cnt]=z;
		ne[cnt]=be[x];
		be[x]=cnt;
	}
}v;
struct uni_find
{
	LL fa[maxn];
	void init(LL n)
	{
		LL i;
		fo(i,1,n) fa[i]=i;
	}
	LL gf(LL x)
	{
		return (fa[x]=((fa[x]==x)?x:gf(fa[x])));
	}
	void uni(LL x,LL y)
	{
		LL fx=gf(x),fy=gf(y);
		if (fx!=fy) fa[fx]=fy;
	}
};
void kruskal()
{
	uni_find bcj;
	bcj.init(n);
	LL i,cnt=0;
	sort(e+1,e+m+1);
	fo(i,1,m)
		if (bcj.gf(e[i].u)!=bcj.gf(e[i].v))
		{
			t+=e[i].w;
			mst[++cnt]=i;
			in_mst[i]=1;
			bcj.uni(e[i].u,e[i].v);
			v.add(e[i].u,e[i].v,e[i].w);
			v.add(e[i].v,e[i].u,e[i].w);
		}
}
void dfs(LL be,LL now,LL fa,LL temp)
{
	ma[be][now]=temp;
	out(i,v,now)
	if (to!=fa)
		dfs(be,to,now,max(temp,v.w[i]));
}
LL ksm(LL ds,LL zs)
{
	LL res=1;
	for(;zs;zs>>=1)
	{
		if (zs&1) res=res*ds%kcz;
		ds=ds*ds%kcz;
	}
	return res;
}
int main()
{
#ifdef Mogician
	freopen("E.in","r",stdin);
#endif
	scanf("%lld%lld%lld",&n,&m,&x);
	LL i;
	fo(i,1,m)
		scanf("%lld%lld%lld",&e[i].u,&e[i].v,&e[i].w);
	kruskal();
	LL temp=x-t;
	if (temp<0)
	{
		printf("0");
		return 0;
	}
	fo(i,1,m) dfs(i,i,0,0);
	fo(i,1,m)
		if (!in_mst[i])
		{
			if (e[i].w-ma[e[i].u][e[i].v]<temp) dif[0]++;
			else if (e[i].w-ma[e[i].u][e[i].v]>temp) dif[2]++;
			else dif[1]++;
		}
	ans=0;
	if (!temp)
	{
		ans+=(ksm(2,n-1)-2)*ksm(2,m-n+1)%kcz;
	}
	ans=(ans+2*(ksm(2,dif[1])-1)*ksm(2,dif[2]))%kcz;
	printf("%lld",ans);
}

Measured memory_bytes: 32640
#include <bits/stdc++.h>
using namespace std;
#define rep for(int i = 0;i<n;i++)
#define ll long long
 
//const int INF = 1e8;
const int MOD = 1000000007;
typedef pair<int,int>P;
int dx[4] = {1,0,-1,0};int dy[4] = {0,1,0,-1};
queue<P> que;
 
int main(){
    ll s; cin >> s;
    //面積s/2の三角形の座標６つ→long 部分とint 部分を分けて考える
    // s = ad-bc = 1e9*d - b*1
    //sを1e9で割った省とあまりより求められる
    ll a = 1000000000;
    ll c = 1;
    ll b,d;
    if(s%a != 0 and s/a == 0){
      d = 1; b = a - (s%a);
    }else if(s % a != 0 and s/a > 0){
      d = s/a + 1; b = a -(s%a);
    }else {
	  b = 0; d =  s/a;
    }
    cout << 0 << " " << 0<< " ";
    cout << a << " " << b << " ";
    cout << c << " " << d << endl;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"

using namespace std;

using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using i8 = int8_t;
using i32 = int32_t;
using i64 = int64_t;
constexpr char newl = '\n';

template<typename T1, typename T2> inline void chmin(T1& a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define F0R(i,b) FOR(i,0,b)
#define RFO(i,a,b) for (int i = ((b)-1); i >=(a); i--)
#define RF0(i,b) RFO(i,0,b)
//#define F first
//#define S second
#define debug(x) cout << #x << ": " << x << '\n';

#if 1

template<typename T>
constexpr T Abs(T a) {
  return a > 0 ? a : -a;
}

// INSERT ABOVE HERE
signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  vector<i64> pow5;
  // 6200 - 6300 の間で i64 オーバーフロー
  pow5.reserve(6300);
  for (i64 i = 0; i < 6300; i++) {
    pow5.push_back(i * i * i * i * i);
  }

  i64 X;
  cin >> X;
  
  i64 A, B;

  for (i64 a = 0; true; a++) {
    i64 a5 = pow5[a];

    i64 dif = X - a5;
    auto it = lower_bound(pow5.begin(), pow5.end(), Abs(dif));

    if ((*it) == Abs(dif)) {
      A = a;
      B = it - pow5.begin();
      if (dif > 0) B = -B;
      break;
    }
  }

  cout << A << ' ' << B;
}
#endif


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

struct node{
  int key;
  struct node *next;
  struct node *prev;
};

typedef struct node * NodePointer;

NodePointer nil;

NodePointer listSearch(int);
void init(void);
void printList(void);
void deleteFirst(void);
void deleteLast(void);
void delete(int);
void insert(int);

int main(){
  int n,i,num,np,nd,size;
  char order[11];

  init();
  size = np = nd = 0;

  scanf("%d" ,&n);
  for(i = 0 ; i < n ; i++){
    scanf("%s %d" ,order ,&num);

    if(order[0] == 'i'){
      insert(num);
      np++; 
      size++;
    }else if(order[0] == 'd'){
      if(strlen(order) > 6){
	if(order[6] == 'F'){
	  deleteFirst();
	}else if(order[6] == 'L'){
	  deleteLast();
	}
      }else{
	delete(num);
	nd++;
      }
      size--;
    }
  }
  printList();

  return 0;
}

NodePointer listSearch(int key){
  NodePointer x,y;

  y = nil;
  x = y->next;

  while(x != nil){
    if(x->key == key){
      return y;
    }
    y = x;
    x = y->next;
  }
  return NULL;
}

void init(){
  nil = malloc(sizeof(struct node));
  nil->next = nil;
  nil->prev = nil;
  nil->key = -1;
}

void printList(){
  NodePointer cur = nil->next;
  int isf = 1;

  while(1){
    if(cur == nil) break;
    if(isf == 0) printf(" ");
    printf("%d" ,cur->key);
    cur = cur->next;
    isf = 0;
  }
  printf("\n");
}

void deleteFirst(){
  NodePointer x,y;

  x = nil->next;
  y = x->next;
  y->prev = nil;
  nil->next = y;
  free(x);
}

void deleteLast(){
  NodePointer x,y;

  x = nil->prev;
  y = x->prev;
  y->next = nil;
  nil->prev = y;
  free(x);
}

void delete(int key){
  NodePointer x,y,z;

  if(nil->next->key == key){
    deleteFirst();
    return;
  }

  x = listSearch(key);
  if(x == NULL){
    return;
  }
  z = x->next;

  y = x->next->next;
  x->next = y;
  y->prev = x;
  
  free(z);
}

void insert(int key){
  NodePointer x,y;
  x = malloc(sizeof(struct node));
  x->key = key;
  
  y = nil->next;
  nil->next = x;
  x->prev = nil;
  x->next = y;
  y->prev = x;
}



Measured memory_bytes: 32940
#include<vector>
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include <iostream>
#include <algorithm>
#include <map>
#include <cmath>
#include<queue>
#include <sstream>
#include <set>

const long long INF = 1000000007;
using namespace std;
typedef long long llong;

//int isalpha(char ch): ch がアルファベットなら true を返す
//int isdigit(char ch): ch が数字なら true を返す
//int islower(char ch): ch が小文字なら true を返す
//int isupper(char ch): ch が大文字なら true を返す
//int tolower(char ch): ch の小文字を返す
//int toupper(char ch): ch の大文字を返す

//string型
//size()	文字数を返す
//Insert()	（指定した場所に）文字・文字列を挿入する
//erase()	（指定した場所の）文字・文字列を削除する
//clear()	すべての文字を削除する
//substr()	文字列の（指定した）部分文字列を返す
//replace()	（指定した）部分文字列を新しい文字列に置換する
//c_str()変換
//文字列の比較は、<=や==などを使え
//replace関数を使い、簡単に文字列を置換
//リバース関数：reverse(str.begin(), str.end());
//map<type, type> dict;で宣言
//グラフ理論用変数
//vector<vector<llong> > graph(N);

//ソート
//降順sort(v.begin(), v.end(), std::greater<Type>());

//大文字から小文字へんかん
//w[i] = w[i]-'A'+'a';

//vector
//assignメソッド　引数：サイズ、値
//与えられたサイズと値でvectorを初期化する

//queueクラス
//find()次に取り出す値の表示をする。
//pop()値を取り出す。戻り値はなし
//push()キューに値をプッシュする

//priority_queueクラス

//切り上げ
//ceil
//floor

int main(){
    llong N;
    cin >> N;
    vector<llong> A(N, 0);
    for(int i=0; i<N; i++){
        cin >> A[i];
    }
    llong maxv=-1;
    llong minv=INF;
    for(int i=0; i<A.size(); i++){
        maxv = max(maxv, A[i]);
        minv = min(minv, A[i]);
    }
    cout << maxv-minv << endl;
    return 0;
}


Measured memory_bytes: 3208
#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int mod=1e9+7;
int a[200000],sum[200001],unzip[200001],cnt[200001];
signed main(){
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++)
        cin>>a[i],a[i]--;
    for(int i=0;i<n;i++)
        sum[i+1]=(sum[i]+a[i])%k;
    for(int i=0;i<=n;i++)
        unzip[i]=sum[i];
    sort(unzip,unzip+n+1);
    int zip_sz=unique(unzip,unzip+n+1)-unzip;
    map<int,int>zip;
    for(int i=0;i<zip_sz;i++)
        zip[unzip[i]]=i;
    int ans=0;
    for(int i=0;i<=n;i++){
        ans+=cnt[zip[sum[i]]];
        cnt[zip[sum[i]]]++;
        if(i>=k-1)
            cnt[zip[sum[i-k+1]]]--;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 19072
#include <iostream>
#include<cstdio>
using namespace std;
#define MAX 2000000
int H,A[MAX];
void maxHeapify(int i)
{
    int l,r,largest;
    l=i*2;
    r=i*2+1;
    if(l<=H&&A[i]<A[l])largest=l;
    else largest=i;
    if(r<=H&&A[largest]<A[r])largest=r;
    if(largest!=i){
        swap(A[largest],A[i]);
        maxHeapify(largest);
    }
}
void buildMaxHeap()
{
    for(int i=H/2;i>=1;i--){
        maxHeapify(i);
    }
}
int main()
{
    scanf("%d",&H);
    for(int i=1;i<=H;i++)
    {
        scanf("%d",&A[i]);
    }
    buildMaxHeap();
    for(int i=1;i<=H;i++)
    {
        printf(" %d",A[i]);
    }
    printf("\n");
    return 0;
}

Measured memory_bytes: 5120
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <string>
#include <utility>
#include <map>
#include <queue>

#define rep(i,s,n) for(int i = s; n > i; i++)
#define REP(i,n) rep(i,0,n)
#define ll long long int
#define ALL(a) a.begin(), a.end()
using namespace std;

template<class T>
class segtree {
	vector<T> tree;
public:
	segtree(const int n) :tree(n * 2) {}
	int base() const { return tree.size() / 2; }
	void update(int i, const T&v) {
		i += base();
		tree[i] = v;
		while (i /= 2)
			tree[i] = tree[i * 2] + tree[i * 2 + 1];
	}
	T fold(int f, int l)const {
		f += base();
		l += base();
		T accl, accr;
		while (f < l) {
			if (f & 1)
				accl = accl + tree[f++];
			f /= 2;
			if (l & 1)
				accr = tree[--l] + accr;
			l /= 2;
		}
		return accl + accr;
	}
};


ll k;

struct hoge {
	bool flip;
	ll sum;
	hoge(bool x = 0, ll y = 0) :flip(x), sum(y) {}
	hoge operator+(const hoge &r)const {
		if (flip)
			return hoge(!r.flip, (sum - r.sum + k) % k);
		else
			return hoge(r.flip, (sum + r.sum) % k);
	}
};

ll getmod(const ll a) {
	return (a%k + k) % k;
}

hoge make(const ll a) {
	if (a != 0)
		return hoge(0, a);
	else
		return hoge(1, 0);
}


int gcd(int a, int b) {
	if(a < b) swap(a, b);
	while (b != 0)
		a %= b, swap(a, b);
	return a;
}

#define Getbit(a,n) (a & (1LL << n))
#define int ll
typedef pair<int, int> pii;
signed main() {
	int n, q;
	string s;
	cin >> n >> s >> q;

	vector<pii> k(q);
	vector<int> mc(3*n+1), cc(3*n+1), out(q);
	REP(i, q) {
		cin >> k[i].first;
		k[i].second = i;
	}
	int cmc = 0;
	REP(i, n) {
		cmc += s[i] == 'M';
		mc[i + 1] = mc[i] + (s[i] == 'C' ? cmc : 0);
		cc[i + 1] = cc[i] + (s[i] == 'C');
	}
	rep(i, n, 3*n) {
		mc[i + 1] = mc[i];
		cc[i + 1] = cc[i];
	}

	sort(ALL(k));

	int ans = 0, cur = 0;

	REP(i, q) {
		cmc = 0;
		REP(j, n) {//D
			cmc += s[j] == 'M';
			if (s[j] == 'D') {
				ans += (mc[j + k[i].first] - mc[j + cur]) - cmc * (cc[j + k[i].first] - cc[j + cur]);
			}
		}

		out[k[i].second] = ans;
		cur = k[i].first;
	}

	REP(i, q) {
		printf("%lld\n", out[i]);
	}

	return 0;
}


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

//template
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(a);i>(b);i--)
#define ALL(v) (v).begin(),(v).end()
typedef long long int ll;
const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; const double eps=1e-12;
void tostr(ll x,string& res){while(x)res+=('0'+(x%10)),x/=10; reverse(ALL(res)); return;}
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; }
//template end

int cnt[100010]={};
int rem[100010]={},sub[100010]={};

int main(){
   int n,m; scanf("%d%d",&n,&m);
   rep(i,0,n){
      int tmp; scanf("%d",&tmp);
      cnt[tmp]++; rem[tmp%m]++;
   }
   rep(i,0,100001)sub[i%m]+=cnt[i]/2;
   int ans=rem[0]/2; if(m%2==0)ans+=rem[m/2]/2;
   rep(i,1,(m+1)/2){
      int add=abs(rem[i]-rem[m-i])/2;
      if(rem[i]<rem[m-i])chmin(add,sub[m-i]);
      else chmin(add,sub[i]);
      ans+=min(rem[i],rem[m-i])+add;
   }
   printf("%d\n",ans);
   return 0;
}

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

int main()
{
  int a = 0;
  int b = 0;
  int c = 0;
  
  cin >> a >> b >> c;
  if(a < b && b < c)
  {
    cout << "Yes" << endl;
  }else
  {
    cout << "No" << endl;
  }
}


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

using namespace std;

typedef long long ll;

const ll MOD = 1000000007;
const ll INF = 1LL<<60;
//int INF = numeric_limits<int>::max();

int main(int, char**) {
	int n; cin >> n;
	string s; cin >> s;
	for (int i=0; i<s.size(); i++) {
		if (s[i] + n > 'Z') s[i] -= (26 - n);
		else s[i] += n;
	}
	cout << s << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i = 0; i < N; i++)
#define all(x) x.begin(), x.end()
#define sort(x) sort(all(x))
#define cou(x) cout << x << endl
using lint = long long;
using vi = vector<int>;

int main() {
	int n, r;
	cin >> n >> r;
	int count = 0;
	while (n) {
		n /= r;
		count++;
	}
	cou(count);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
typedef long long ll;
namespace mp = boost::multiprecision;
using Mint = mp::cpp_int;
#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 all(v) v.begin(), v.end()
#define uni(v) v.erase(unique(all(v)), v.end())
#define sort_g(v) sort(all(v), greater<int>())
#define dump(x) cerr << #x << ' ' << '=' << ' ' << x << endl

int main() {
    int N;
    cin >> N;
    vector<int> data(N);
    rep(i, N) cin >> data.at(i);

    int sum = 0;
    rep(i, N) {
        repi(j, i + 1, N) {
            sum += data.at(i) * data.at(j);
        }
    }

    cout << sum << endl;
}

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

using ll = long long;

const int INF = 1e9 + 5;

int main() {
    int n;
    scanf("%d", &n);
    int k;
    scanf("%d", &k);
    vector<int> h(n);
    for(int& x : h) {
        scanf("%d", &x);
    }
    vector<int> dp(n, INF);
    dp[0] = 0;
    for(int i = 0; i < n; ++i) {
        for(int j = i + 1; j <= i + k; ++j) {
            if(j < n) {
                dp[j] = min(dp[j], dp[i] + abs(h[i] - h[j]));
            }
        }
    }
    printf("%d\n", dp[n-1]);
}

Measured memory_bytes: 1024
N = int(input())
a = list(map(int,input().split()))
s = list(sorted(a))
ind = {}
for i in range(N):
    if s[i] not in ind:
        ind[s[i]] = i
for i in range(N):
    if ind[a[i]] < N//2:
        print(s[N//2])
    else:
        print(s[N//2-1])

Measured memory_bytes: 42492
import math
def main2():
    def get(N):
        res = set()
        for i in range(1, int(math.sqrt(N)+2)):
            if N % i == 0:
                res.add(i)
                res.add(N // i)
        return res
    N = int(input())
    mini = 10 ** 15
    for c in get(N):
        d = N // c
        e = c + d - 2
        mini = min(mini, e)
    print(mini)
main2()

Measured memory_bytes: 3828
H, W, N, sr, sc, S, T = open(0).read().split()
H, W, N, sr, sc = map(int, (H,W,N,sr,sc))
dpr = [0]*(N+1)
dpl = [0]*(N+1)
dpu = [0]*(N+1)
dpd = [0]*(N+1)
dpr[0] = W-sc
dpl[0] = sc-1
dpu[0] = sr-1
dpd[0] = H-sr
for i in range(N):
  if S[i]=='R':
    dpr[i] -= 1
    if 0>dpr[i]:
      print('NO')
      break
  elif S[i]=='D':
    dpd[i] -= 1
    if 0>dpd[i]:
      print('NO')
      break
  elif S[i]=='L':
    dpl[i] -= 1
    if 0>dpl[i]:
      print('NO')
      break
  else:
    dpu[i] -= 1
    if 0>dpu[i]:
      print('NO')
      break
  if T[i]=='R':
    dpl[i+1] = min(W-1,dpl[i]+1)
    dpr[i+1] = dpr[i]
    dpd[i+1] = dpd[i]
    dpu[i+1] = dpu[i]
  elif T[i]=='L':
    dpr[i+1] = min(W-1,dpr[i]+1)
    dpl[i+1] = dpl[i]
    dpu[i+1] = dpu[i]
    dpd[i+1] = dpd[i]
  elif T[i]=='U':
    dpd[i+1] = min(H-1,dpd[i]+1)
    dpl[i+1]= dpl[i]
    dpu[i+1] = dpu[i]
    dpr[i+1] = dpr[i]
  else:
    dpu[i+1] = min(H-1,dpu[i]+1)
    dpl[i+1] = dpl[i]
    dpr[i+1] = dpr[i]
    dpd[i+1] = dpd[i]
else:
  print('YES')

Measured memory_bytes: 57808
#read test
parseInt(x) = parse(Int, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
	n = readline() |> parseInt
	#buf = zeros(UInt8,100)
	#println(length(buf))
	buf = read(STDIN,5000000)
	#println(size(buf))
	str = transcode(String,buf)
	str = split(str,"\n")
	#println(length(str[1]))
	a = Array{Int}(2,n)
	for i in 1:n
		a[:,i] = str[i] |> split |> parseMap
	end
	a = sortcols(a, by=z->z[2])
	t = 0
	flg = 0
	for i in 1:n
		t += a[1,i]
		if t > a[2,i]
			flg = 1
			break
		end
	end
	println(flg==0?"Yes":"No")
end

main()


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

using namespace std;

#define F first
#define S second
#define modulo ll (1e9 + 7)
const long double PI = 3.141592653589793238L;

typedef long long ll;
typedef pair<int,int> pii;

void init(){
    cin.tie(0);
    cin.sync_with_stdio(0);
}

const int N = 3e5 + 9, M = 4e5 + 9, OO = 0x3f3f3f3f;
const ll llOO = 0x3f3f3f3f3f3f3f3f;

int main(){
    init();

    string s;   cin >> s;

    int q;  cin >> q;

    int state = 0;
    vector<char> add[2];
    for(int i = 0;i < q;i++){
        int t;  cin >> t;
        if(t == 1)  state ^= 1;
        else{
            int f;  char c; cin >> f >> c;
            f--;
            add[state ^ f].push_back(c);
        }
    }

    if(state)   reverse(s.begin(), s.end());
    reverse(add[state].begin(), add[state].end());
    for(auto c : add[state])    cout << c;
    cout << s;
    for(auto c : add[state ^ 1])    cout << c;

}

Measured memory_bytes: 976
n, ma, mb = list(map(int, input().split()))
negs, poss, ans = [], [], 100 * n + 1
for _ in range(n):
    a, b, c = list(map(int, input().split()))
    sub = a * mb - b * ma
    if sub > 0:
        poss.append((sub, c))
    elif sub < 0:
        negs.append((-sub, c))
    else:
        ans = min(c, ans)

def sums(tups):
    ret = {0: 0}
    for x, c in tups:
        tmp = ret.copy()
        for x0, c0 in tmp.items():
            if x + x0 in ret:
                ret[x + x0] = min(c + c0, ret[x + x0])
            else:
                ret[x + x0] = c + c0
    del ret[0]
    return ret

nsum = sums(negs)
psum = sums(poss)

for v in nsum:
    if v in psum:
        ans = min(ans, nsum[v] + psum[v])
if ans == 100 * n + 1:
    ans = -1
print(ans)


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

template <typename TYPE>
void print_vec(const vector<TYPE>& v){
	for(int i=0; i<v.size(); i++){
		cout << v[i] << " ";
	}
	cout << endl;
}

template <typename TYPE>
void print_vec2(const vector<vector<TYPE>>& v){
  cout << endl;
  for(int i=0; i<v[0].size(); i++) cout << i << "   "; 
  cout << endl;
	for(int i=0; i<v.size(); i++){
		cout << "i=" << i << ":   " << endl;
		for(int j=0; j<v[i].size(); j++){
			if(v[i][j] == 0) cout << "\x1B[0m" << v[i][j] << "   ";
      else cout << "\x1B[31m" << v[i][j] << "   ";//https://stackoverrun.com/ja/q/12618775
		}
		cout << "\x1B[0m" << endl;
	}
}
 

int main(){
  ll N, M;
  cin >> N >> M;
  vector<ll> H(N), A(M), B(M);
  vector<vector<ll>> vec(N, vector<ll>());
  for(int i=0; i<N; i++) cin >> H[i];
  for(int i=0; i<M; i++){
      ll a, b;
      cin >> a >> b;
      a--; b--;
      A[i] = a;
      B[i] = b;
      vec[a].push_back(b);
      vec[b].push_back(a);
  }

  vector<bool> is_highest(N, true);
  for(int i=0; i<N; i++){
    if(is_highest[i] == false) continue;
    bool is_tall = true;
    for(int j=0; j<vec[i].size(); j++){
      if(H[i] <= H[vec[i][j]]){
        is_tall = false;
      }
      else if(H[i] > H[vec[i][j]]) is_highest[vec[i][j]] = false;
    }
    if(is_tall == false) is_highest[i] = false;

  }

  ll ans = 0;
  for(int i=0; i<N; i++){
      if(is_highest[i] == true) ans++;
  }
  cout << ans << endl;
    
}


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

int main(){
  int n,m,p,a,s[20000];
  cin >> n >> m >> p;
  for(int i=0;i<m;i++){
    cin >> a;
    s[2*i] = a;
    s[2*i+1] = (a<p)?a+n:a-n;
  }
  sort(s,s+2*m);

  a = min(p-s[0], s[2*m-1]-p);
  for(int i=1;i<m;i++){
    int l = s[i], r = s[i+m-1];
    a = min(a, min(p-l,r-p)*2 + max(p-l,r-p));
  }
  cout << a*100 << endl;
}

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

//Euclid's algorithm
ll gcd(ll a , ll b)
{
   if(b==0) return a;
   a%=b;
   return gcd(b,a);
}

int main(){
    ll s,w;
    cin>>s>>w;
    if(w>=s) cout<<"unsafe\n";
    else cout<<"safe\n";
}

Measured memory_bytes: 3596
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include <unordered_map>
//#include"testlib.h"
#define endl "\n"
#define all(v) v.begin(),v.end()
#define allr(s) s.rbegin(),s.rend()
#define RT(s) return cout<<s,0
#define watch(x) cout << (#x)<<" = "<<x<<endl
#define sz(s)    (int)(s.size())
#define PI acos(-1)
#define EPS 1e-8
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
int dy[] = { 1, -1, 0, 0, -1, 1, 1, -1 };
int dx[] = { 0, 0, 1, -1, 1, -1, 1, -1 };
void file() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
#else
	//freopen("street.in", "r", stdin);
	//freopen("out.txt", "w", stdout);
#endif
}
void fast() {
	std::ios_base::sync_with_stdio(0);
	cin.tie(NULL);
}

int main() {
	//file();
	fast();
	int n, x, y; cin >> n >> x >> y;
	vector<ll> ans(n + 9);
	// first part
	for (int i = 1; i <= x; i++) {
		// third part
		ans[x - i + 2]++, ans[x - i + 1 + (n - y) + 1]--;

		// mid part
		int start = x, end = y, mid, hold = x;
		while (start <= end) {
			mid = (start + end) / 2;
			if (mid - x <= 1 + y - mid) {
				hold = mid;
				start = mid + 1;
			}
			else
				end = mid - 1;
		}
		ans[1]++, ans[hold - i + 1]--;
		ans[x - i + 1]++, ans[x - i + 1 + (y - hold)]--;
	}
	//third part
	for (int i = y; i < n; i++)
		ans[1]++, ans[n - i + 1]--;
	//for (int i = 1; i < n; i++) {
	//	ans[i] += ans[i - 1];
	//	cout << ans[i] << endl;
	//}
	//cout << endl;

	// mid part
	for (int i = x + 1; i < y; i++) {
		int start = i + 1, end = y, mid, hold = i + 1;
		while (start <= end) {
			mid = (start + end) / 2;
			if (mid - i <= i - x + 1 + (y - mid)) {
				hold = mid;
				start = mid + 1;
			}
			else
				end = mid - 1;
		}
		ans[1]++, ans[hold - i + 1]--;
		ans[i - x + 1]++, ans[i - x + 1 + (y - hold)]--;
		int mn = min(i - x + 1, y - i) + 1;
		ans[mn]++, ans[mn + n - y]--;
	}
	for (int i = 1; i < n; i++) {
		ans[i] += ans[i - 1];
		cout << ans[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

type key struct {
	a int
	c int
}

const inf = 1 << 60

func main() {
	n, m := getInt(), getInt()
	ks := make([]key, m)
	for i := range ks {
		ks[i].a = getInt()

		b := getInt()
		for j := 0; j < b; j++ {
			tmp := uint(getInt()) - 1
			ks[i].c |= 1 << tmp
		}
	}

	// if !checker(ks, n) {
	// 	fmt.Println(-1)
	// 	return
	// }

	dp := make([]int, (1 << uint(n)))
	for i := range dp {
		dp[i] = inf
	}
	dp[0] = 0

	for i := 0; i < (1 << uint(n)); i++ {
		for _, k := range ks {
			dp[k.c|i] = min(dp[k.c|i], dp[i]+k.a)
		}
	}

	if dp[len(dp)-1] >= inf {
		fmt.Println(-1)
		return
	}

	fmt.Println(dp[len(dp)-1])
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func checker(ks []key, n int) bool {
	m := 0
	for _, k := range ks {
		m |= k.c
	}

	if n > m {
		return false
	}
	return true
}

// -----------------------------------------

var sc = bufio.NewScanner(os.Stdin)

func init() {
	// buf := 200001
	// sc.Buffer(make([]byte, buf), buf)
	sc.Split(bufio.ScanWords)
}

func getInt() int {
	i, err := strconv.Atoi(getString())
	if err != nil {
		panic(err)
	}
	return i
}

func getString() string {
	sc.Scan()
	s := sc.Text()
	return s
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define pb push_back
#define ff first
#define ss second
#define ll long long
#define ld long double
typedef pair<ll,ll> pll;
typedef pair<pll,ll> ppll;
typedef vector <ll> vi;
#define out(x) return cout<<x,0;
#define precision(x,d) cout<<fixed<<setprecision(d)<<x
#define lc(n) 2*n+1
#define rc(n) 2*n+2
#define fill(a,b) memset((a),(b),sizeof((a)))
#define FAST ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);srand(time(NULL)); 
const ll N = 55, M = 35;

int main(){
    FAST;
    ll n, x = 0, m, k, i, t, ans = 1, j, y = 0, z = 0, c = 0;
    cin >> n >> m;
    cout << (n*(n - 1))/2 + (m*(m - 1)) / 2;
}

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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
template <typename T> T gcd(T a, T b){return b?gcd(b,a%b):a;}

int main() {
  int N, K;
  if (scanf("%d%d", &N, &K));

  int A[N];
  if (scanf("%d", &A[0]));
  int g = A[0];
  int max_val = A[0];
  REP(i, N-1) {
    if (scanf("%d", &A[i+1]));
    g = gcd(g, A[i+1]);
    max_val = max(A[i+1], max_val);
  }
  if (max_val >= K && K % g == 0)
    printf("POSSIBLE\n");
  else
    printf("IMPOSSIBLE\n");
  return 0;
}


Measured memory_bytes: 640
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
ans = 0

for i in range(N):
    a = A[i]
    b = B[i]
    c = A[i + 1]
    if b <= a:
        ans += b
    else:
        b -= a
        ans += a
        if b < c:
            ans += b
            c -= b
            A[i + 1] = c
        else:
            A[i + 1] = 0
            ans += c

print(ans)



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

class Main {

    public static void main(String[] args) throws Exception {
        final Scanner sc = new Scanner(System.in);
        int N;
        N = sc.nextInt();
        int[] A = new int[(int)(N)];
        for(int i = 0 ; i < N ; i++){
                A[i] = sc.nextInt();
        }
        solve(N, A);
    }

    static void solve(int N, int[] A){
        int[] ans = new int[(int)N];

        for (int i = 0; i < N; i++) {
            ans[(int)A[i] - 1] = i + 1;
        }

        StringBuilder sb = new StringBuilder();

        for ( int var : ans) {
            sb.append(Long.toString(var));
            sb.append(" ");
        }

        System.out.println(sb.toString());
    }
}


Measured memory_bytes: 58764