akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

#define ALL(a) begin(a), end(a)
#define TPL template
#define TNM typename

using ll = long long;
using ull = unsigned long long;

TPL<TNM T> using vec = vector<T>;
TPL<TNM T> using vec2 = vec<vec<T>>;
TPL<TNM T> using vec3 = vec<vec2<T>>;
TPL<TNM T> using vec4 = vec<vec3<T>>;
TPL<TNM T> using vec5 = vec<vec4<T>>;

TPL<TNM T> inline istream& operator >> (istream& is, vector<T>& vec) { for (T& x : vec) is >> x; return is; }
TPL<TNM V, TNM H> void resize(vector<V>& _v, const H _h) { _v.resize(_h); }
TPL<TNM V, TNM H, TNM ... T> void resize(vector<V>& _v, const H& _h, const T& ... _t) { _v.resize(_h); for (auto& __v : _v) resize(__v, _t ...); }
TPL<TNM V, TNM T> TNM enable_if<!is_class<V>::value>::type fill(vector<V>& _v, const T& _t) { std::fill(ALL(_v), _t); }
TPL<TNM V, TNM T> TNM enable_if<is_class<V>::value>::type fill(vector<V>& _v, const T& _t) { for (auto& _e : _v) fill(_e, _t); }
TPL<TNM T> inline void UNIQUE(vector<T>& _v) { sort(ALL(_v)); _v.erase(unique(ALL(_v)), _v.end()); }
struct pre_ { pre_() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(6); } } pre__;

int main(void) {
	int N;
	cin >> N;
	vec<int> A(N);
	vec<int> memo1(N, -1);
	vec<int> memo2(N, -1);
	for (int i = 0; i < N; ++i) {
		cin >> A[i];

	}
	memo1[0] = A[0];
	for (int i = 1; i < N; ++i) {
		memo1[i] = max(memo1[i - 1], A[i]);
	}
	memo2[N - 1] = A[N - 1];
	for (int i = N - 2; i >= 0; --i) {
		memo2[i] = max(memo2[i + 1], A[i]);
	}

	for (int i = 0; i < N; ++i) {
		if (i == 0) {
			cout << memo2[1] << endl;
		}
		else if (i == N - 1) {
			cout << memo1[N - 2] << endl;
		}
		else {
			cout << max(memo1[i - 1], memo2[i + 1]) << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 3968
n, m = gets.chomp.split.map(&:to_i)
a = gets.chomp.split.map(&:to_i)

a.sort!.reverse!

s = a[m-1]

all = a.inject(:+)

if (s * 4 * m) >= all
  puts 'Yes'
else
  puts 'No'
end


Measured memory_bytes: 3836
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>
#include <cstring>

#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define all(c) begin(c),end(c)

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; }

typedef long long int ll;
using ll = long long int;
using ull = long long unsigned int;
using Int = long long int;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 1000000007


//edit
class Solve {
public:
    void solve() {
        Int T1, T2;
        Int A1, A2;
        Int B1, B2;
        cin >> T1 >> T2 >> A1 >> A2 >> B1 >> B2;
        Int P = T1 * (B1 - A1);
        Int Q = T2 * (B2 - A2);

        if (P + Q == 0ll) {
            cout << "infinity" << endl;
            return;
        }
        if (P < 0) {
            P = -P;
            Q = -Q;
        }
        if (P + Q > 0) {
            cout << 0 << endl;
            return;
        }
//        if ((P >= 0 && Q >= 0) || (P <= 0 && Q <= 0)) {
//            cout << 0 << endl;
//            return;
//        }

        Int dec = -(P + Q);


        Int ans = (P / dec + 1ll) * 2 - 1ll;

        if (P % dec == 0) ans--;
        cout << ans << endl;
    }
};


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

    Solve().solve();


    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define EPS (1e-10)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

struct st{int a,b,c,d;};
int a[1000][1000];

int main(){
	random_device rnd;
	int h,w;cin>>h>>w;
	rep(i,h)rep(j,w)scanf("%d",&a[i][j]);
	vector<st>v;
	rep(i,h)rep(j,w){
		vector<P>d{P(1,0),P(-1,0),P(0,1),P(0,-1)};
		shuffle(d.begin(),d.end(),rnd);
		vector<int>dx{d[0].first,d[1].first,d[2].first,d[3].first},
					dy{d[0].second,d[1].second,d[2].second,d[3].second};
		if(a[i][j]%2){
			rep(k,4){
				int nx=i+dx[k],ny=j+dy[k];
				if(0<=nx&&nx<h&&0<=ny&&ny<w&&a[nx][ny]%2){
					v.push_back({i,j,nx,ny});a[i][j]--;a[nx][ny]++;goto G;
				}
			}
			rep(k,4){
				int nx=i+dx[k],ny=j+dy[k];
				if(0<=nx&&nx<h&&0<=ny&&ny<w&&nx*w+ny>i*w+j){
					v.push_back({i,j,nx,ny});a[i][j]--;a[nx][ny]++;goto G;
				}
			}
			G:;
		}
	}
	cout<<v.size()<<endl;
	for(auto s:v){
		cout<<s.a+1<<' '<<s.b+1<<' '<<s.c+1<<' '<<s.d+1<<endl;
	}
	//~ cout<<"-----------"<<endl;
	//~ rep(i,h){
		//~ rep(j,w){
			//~ cout<<a[i][j]%2<<' ';
		//~ }
		//~ cout<<endl;
	//~ }
}

Measured memory_bytes: 6128
#include <algorithm>
#include <bitset>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define reps(i, f, n) for (ll i = (f); i < (n); i++)
#define repv(v) for (auto it = (v).begin(); it != (v).end(); it++)
ll const INF = 1LL << 60;
ll const MAX_N = 510000;
ll const MOD = 1000000007;

// in
// 6 3
// 4 3 1 0 9 8
// out
// 18

int main() {
    ll N, x;
    cin >> N >> x;
    vector<ll> a(N);
    rep(i, N) cin >> a[i];

    ll ans = 0;
    for (ll i = 0; i < N - 1; i++) {
        if (a[i] + a[i + 1] > x) {
            ans += a[i] + a[i + 1] - x;
            a[i + 1] -= min(a[i + 1], (a[i] + a[i + 1] - x));
        }

        // repv(a) cout << *it << " ";
        // cout << endl;
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3968
N=int(input())
A=list(map(int,input().split()))
ans=0
t=dict()
for i in range(N):
    if A[i]-i in t:
        ans+=t[A[i]-i]
    t.setdefault(-A[i]-i,0)
    t[-A[i]-i]+=1
print(ans)

Measured memory_bytes: 40384
object Main {
  def main(args: Array[String]): Unit = {
    val (num, limit) = {
      val nw = io.StdIn.readLine().split(" ").map(_.toInt)
      (nw(0), nw(1))
    }
    val items = new Array[(Int, Int)](num)
    for (i <- 0 until num) {
      val vw = io.StdIn.readLine().split(" ").map(_.toInt)
      items(i) = (vw(0), vw(1))
    }

    val dp = solve(limit, items)
    val max =
      dp(num)
        .zipWithIndex
        .collect { case (w, v) if w <= limit => v }
        .max
    println(max)
  }

  def solve(weightLimit: Int, items: Array[(Int, Int)]): Array[Array[Int]] = {
    val length = items.length
    val maximum = length * MaxValue
    val dp = Array.ofDim[Int](length + 1, maximum + 1)
    for (i <- 1 to maximum) {
      dp(0)(i) = weightLimit + 1
    }
    dp(0)(0) = 0

    items.zipWithIndex.foreach { case ((v, w), i) =>
      for (limit <- 0 to maximum) {
        if (v <= limit && dp(i)(limit) > dp(i)(limit - v) + w) {
          dp(i + 1)(limit) = dp(i)(limit - v) + w
        } else {
          dp(i + 1)(limit) = dp(i)(limit)
        }
      }
    }
    dp
  }

  val MaxValue = 100
}

Measured memory_bytes: 50208
#include<stdio.h>
int main(void){
long long A, B, K;
scanf("%lld %lld %lld",&A, &B, &K);
if(A+B<=K){
    printf("0 0\n");
}else if(K>=A){
    printf("0 %lld\n", B-K+A);
}else{
    printf("%lld %lld\n", A-K, B);
}
return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
using lint = long long int;
long long int INF = 1001001001001001LL;
int inf = 1000000007;
long long int MOD = 1000000007LL;
double PI = 3.1415926535897932;

template<typename T1,typename T2>inline void chmin(T1 &a,const T2 &b){if(a>b) a=b;}
template<typename T1,typename T2>inline void chmax(T1 &a,const T2 &b){if(a<b) a=b;}

#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()

/* do your best */

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

  lint ans = 1000;
  lint kabu = 0;
  lint kane = 1000;

  bool isKai = true;

  for (int i = 0; i < n - 1; i++) {

    if (isKai) {
      // 極小値を見つけたい
      if (a[i] > a[i + 1]) continue;
      kabu = kane / a[i];
      kane = kane % a[i];
      isKai = false;
    } else {
      // 極大値を見つけたい
      if (a[i] < a[i + 1]) continue;
      kane += a[i] * kabu;
      kabu = 0;
      isKai = true;
      ans = max(ans, kane);
    }
  }

  if (!isKai) {
    kane += a[n - 1] * kabu;
    kabu = 0;
    ans = max(ans, kane);
  }

  cout << ans << endl;

  return 0;
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define Abs(x)((x) < 0 ? (x) * -1 : (x))
#define rep(x, y) for ((x) = 0; (x) < (y); (x)++)
#define repin(x, y) for ((x) = 0; (x) <= (y); (x)++)
#define nep(x, y) for ((x) = (y) - 1; 0 <= (x); (x)--)
#define nepi(x, y, z) for ((x) = (y) - 1; (z) <= (x); (x)--)
#define repi(x, y, z) for ((x) = (z); (x) < (y); (x)++)
#define repiin(x, y, z) for ((x) = (z); (x) <= (y); (x)++)
#define reps(x, y, z) for ((x) = 0; (x) < (y); (x) += (z))
#define repit(x) for (__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define all(x) (x).begin(),(x).end()
#define Mem0(x) memset(x, 0, sizeof(x))
#define Mem1(x) memset(x, -1, sizeof(x))
#define _end '\n'
#define Out(x) cout<<(x)<<_end
template<typename T> inline bool Max(T &x, const T &y) { return x < y ? x = y, 1 : 0; }
template<typename T> inline bool Min(T &x, const T &y) { return x > y ? x = y, 1 : 0; }
template<typename T> using V = vector<T>;
template<typename T> using VV = V<V<T> >;

#define pb push_back
#define mp make_pair

static const ll MOD = 1e9 + 7;
static const double PI = 3.141592653589793;

#define LOCAL 0

int main()
{
#if LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    freopen("debug.txt", "w", stderr);
#endif

    cin.tie(0);
    ios::sync_with_stdio(false);

    int a, b, c;

    cin >> a >> b >> c;

    if (c <= a + b) Out("Yes");
    else Out("No");

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  bool f = true;
  string S;
  cin >> N >> S;
  int l;
  l = S.size();
  if (l % 2 != 0) f = false;
  for (int i = 0; i < l / 2; i++){
    if ( S.at(i) != S.at(l/2 + i)){
      f = false;
    }
    if (f == false) break;
  }
  if (f == true){     
    cout << "Yes" <<endl;
  }
  else{
      cout << "No" << endl;    
  }
        
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;
int main(int argc, char *argv[]) {
	int n = 0;
	string s = "";
	int count = 0;
	
	cin >> n >> s;
	
	for(int i = 0; i < n; i++){
		if (s[i] == 'A' && i != n-2) 
			if (s[i+1] == 'B')
				if (s[i+2]=='C')
					count++;
	}
	
	cout << count;
	return 0;
	
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
#define oset tree<int , null_type, less_equal<int> , rb_tree_tag, tree_order_statistics_node_update>
#define show(x) cout<<#x<<" "<<x<<'\n'
 
#define MAX 1000000007
#define N 100000
 
using namespace std;
using namespace __gnu_pbds;

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long int n;
  cin>>n;
  long long int ans = n*n*n;
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define pb puhs_back
#define Int int64_t
using namespace std;

int N;
int main()
{
   cin>>N;
   vector<Int> A(N);
   for(auto &x:A) cin>>x;
   Int ans=0;
   sort(A.begin(),A.end());
   for(int i=N-1;i>=0;--i){
       for(int j=i-1;j>=0;--j){
           Int sum=A[i]+A[j];
           auto itr=lower_bound(A.begin(),A.end(),sum);
           Int x=distance(itr,A.end());
           ans+=(N-1-x)-i;
           
       }
   }
   cout<<ans<<"\n";
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
#define rep(i,n) for (ll i = 0; i < n; ++i)
#define ALL(c) (c).begin(), (c).end()
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())
#define FORV(i, v) for (auto i = v.begin(); i != v.end(); i++)
using namespace std;

typedef long long ll;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const int INF = 1001001001;
const long long INFL = (1LL<<60);
const double eps = (1e-9);

int mod = int(1e+9) + 7;

int dp[101][4][4][4];

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

  // A: 0, G: 1, C: 2, T: 3

  // 長さ 0 の文字列は1である。
  // 0, 1, 2, に関する制約しかないので S は 333S と考えても問題がない
  dp[0][3][3][3] = 1;

  rep(len, n) {
    rep(i, 4) {      // 1つ前の文字について 0, 1, 2, 3 を全部
      rep(j, 4) {    // 2つ前の文字について 0, 1, 2, 3 を全部
        rep(k, 4) {  // 3つ前の文字について 0, 1, 2, 3 を全部
          if (dp[len][i][j][k] == 0) continue;
          // 新しく追加する文字列
          rep(a, 4) {
            if (a == 2 && i == 1 && j == 0) continue;  // AGC
            if (a == 2 && i == 0 && j == 1) continue;  // GAC
            if (a == 1 && i == 2 && j == 0) continue;  // ACG
            if (a == 2 && i == 1 && k == 0) continue;  // A*GC
            if (a == 2 && j == 1 && k == 0) continue;  // AG*C

            dp[len+1][a][i][j] += dp[len][i][j][k];
            dp[len+1][a][i][j] %= mod;
          }
        }
      }
    }
  }

  int ans = 0;
  rep(i, 4) {
    rep(j, 4) {
      rep(k, 4) {
        ans += dp[n][i][j][k];
        ans %= mod;
      }
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
def shortest_path(edge,num_v,start):
    inf = float("inf")
    d = [-inf for f in range(num_v)]
    d[start] = 0;
    for i in range(3000):
        update = False
        for e in edge:
            if (d[e[0]-1] != -inf and d[e[1]-1] < d[e[0]-1] + e[2]):
                d[e[1]-1] = d[e[0]-1] + e[2]
                update = True
                if (e[1] == n and i >= n):
                  return "inf"
        if not update:
            break
    return d[-1]
n,m = map(int,input().split())
p = []
for i in range(m):
    p.append(list(map(int, input().split())))
ans = shortest_path(p,n,0)
print(ans)

Measured memory_bytes: 3572
#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9+5;

int main(){
  int n;
  cin>>n;
  int M[n][3];
  for(int i=0; i<n; i++){
      for(int j : {0, 1, 2}){
          cin>>M[i][j];
      }
  }
  for(int i=1;i<n;i++){
      for(int j : {0, 1 , 2})
      M[i][j] += max(M[i-1][abs(j+1)%3], M[i-1][abs(j+2)%3]);
  }
  int res INT_MIN;
  for(int j : {0, 1, 2}) res=max(res, M[n-1][j]);
  cout<<res;
  return 0;
}

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

using namespace std;

int main(void)
{
    int l;
    cin >>l;

    double x = (double)l / (double)3;

    printf("%.8lf\n", x * x * x);

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#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)
typedef long long ll;
long long mod = 1e9 + 7;
const int iINF = 0x3f3f3f3f;
const long long INF = 1LL << 60;
using namespace std;
using pint = pair<int, int>;

template <class T>
inline bool chmin(T &a, T b)
{
  if (a > b)
  {
    a = b;
    return true;
  }
  return false;
}

template <class T>
inline bool chmax(T &a, T b)
{
  if (a < b)
  {
    a = b;
    return true;
  }
  return false;
}

struct mint
{
  ll x; // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint &operator+=(const mint a)
  {
    if ((x += a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator-=(const mint a)
  {
    if ((x += mod - a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator*=(const mint a)
  {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const { return mint(*this) += a; }
  mint operator-(const mint a) const { return mint(*this) -= a; }
  mint operator*(const mint a) const { return mint(*this) *= a; }
  mint pow(ll t) const
  {
    if (!t)
      return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1)
      a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod - 2); }
  mint &operator/=(const mint a) { return *this *= a.inv(); }
  mint operator/(const mint a) const { return mint(*this) /= a; }
};

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

  map<char, int> mp;

  rep(i, n)
  {
    char c;
    cin >> c;
    mp[c]++;
  }

  mint ans = {1};
  for (auto i : mp)
  {
    ans *= (i.second + 1);
  }

  cout << (ans - 1).x << endl;

  return 0;
}

Measured memory_bytes: 3608
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int num = Integer.parseInt(sc.next() + sc.next());

		if ((int)Math.sqrt(num)*(int)Math.sqrt(num) == num) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}

	}

}

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


int main() {
  int n;
  cin>>n;
  vector<long>a(n),b(n);
  rep(i,n){
    cin>>a.at(i);
  }
  rep(i,n){
    cin>>b.at(i);
  }
  long ta=0;
  long tb=0;
  rep(i,n){
    ta+=a.at(i);
    tb+=b.at(i);
  }
  bool ex=true;
  if(ta-tb>0){
    ex=false;
  }
  if(ex){
    long di=tb-ta;
    long di2=0;
    long di3=0;
    rep(i,n){
      if(a.at(i)-b.at(i)>0){
        di2+=a.at(i)-b.at(i);
      }
      else{
        di3+=(b.at(i)-a.at(i)+1)/2;
      }
    }
    if(di2>di||di3>di){
      ex=false;
    }
  }
  if(ex){
    cout<<"Yes"<<endl;
  }
  else{
    cout<<"No"<<endl;
  }
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <tuple>
#include <map>
#include <queue>
#include <set>
typedef long long ll;
using namespace std;
#define rep(i, n) for (int i = 0; i < int(n); i++)
#define mod 1000000007
#define fst first
#define pb push_back

int main()
{
    string s;
    cin >> s;
    int findA;
    int findB;
    for (int i = 0; i < s.length(); i++)
    {
        if (s[i] == 'A')
        {
            findA = i;
            break;
        }
    }
    for (int i = 0; i < s.length(); i++)
    {
        if (s[i] == 'Z')
        {
            findB = i;
        }
    }
    cout << findB - findA + 1 << endl;
}

Measured memory_bytes: 640
import sys
from bisect import bisect_left

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, D, A, *XH = map(int, read().split())
    monster = [0] * N
    for i, (x, h) in enumerate(zip(*[iter(XH)] * 2)):
        monster[i] = (x, (h + A - 1) // A)

    monster.sort()

    pos = []
    damage = []
    idx = 0

    cur_damage = 0
    ans = 0

    for x, h in monster:
        while idx < len(pos) and pos[idx] < x:
            cur_damage -= damage[idx]
            idx += 1

        if h > cur_damage:
            pos.append(x + 2 * D)
            damage.append(h - cur_damage)
            ans += h - cur_damage
            cur_damage += h - cur_damage

    print(ans)
    return


if __name__ == '__main__':
    main()


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

int selection_sort(long* a, int n){
    int count = 0;
    int min;

    for (int i = 0; i < n; i++){
        min = i;
        for (int j = i; j < n; j++){
            if(a[j] < a[min]){
                min = j;
            }
        }
        if (a[i] > a[min]) {
            swap(a[i], a[min]);
            count++;
        }
    }
    return count;
}

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

    int count = selection_sort(a, n);

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

    return 0;
}


Measured memory_bytes: 3088
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;

int main ()
{
	int n;
	int a, b, c, d;
	scanf("%d",&n);
	d = n % 10;
	n /= 10;
	c = n % 10;
	n /= 10;
	b = n % 10;
	n /= 10;
	a = n % 10;
	if((a+b+c+d) == 7) printf("%d+%d+%d+%d=7\n",a,b,c,d);
	else if(a+b+c-d == 7)  printf("%d+%d+%d-%d=7\n",a,b,c,d);
	else if(a+b-c+d == 7)  printf("%d+%d-%d+%d=7\n",a,b,c,d);
	else if(a+b-c-d == 7) printf("%d+%d-%d-%d=7\n",a,b,c,d);
	else if(a-b+c+d == 7) printf("%d-%d+%d+%d=7\n",a,b,c,d);
	else if(a-b+c-d == 7) printf("%d-%d+%d-%d=7\n",a,b,c,d);
	else if(a-b-c-d == 7) printf("%d-%d-%d-%d=7\n",a,b,c,d);
	else if(a-b-c+d == 7) printf("%d-%d-%d+%d=7\n",a,b,c,d);
	return 0;
}

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

#define rep(i, n) rep2(i, 0, n)
#define rep2(i, m, n) for (ll i = m; i < (n); i++)

using ll = long long;
using pii = pair<int, int>;
using Vi = vector<int>;


int main() {
  int a,b,c,d;
  cin >>a>>b>>c>>d;
  cout << min(a,b)+min(c,d);
}
      

Measured memory_bytes: 3604
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <string>
#include <tuple>
#include <functional>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <map>
//#include "toollib.h"
#pragma warning (disable:4018)
#define INT_MAX 2147483647

using namespace std;

bool judge_prime_numbers(int n) {
	if (n == 1) return false;
	if (n == 2) return true;
	else if (n % 2 == 0) return false;
	else {
		bool judge = true;
		for (int i = 3; i <= sqrt(n); i = i + 2) {
			if (n%i == 0) {
				judge = false;
				break;
			}
		}
		return judge;
	}
}

void make_new_prime_numbers(vector<int>* ary) {
	int n = (*ary).back() + 2;
	while (true) {
		bool judge = true;
		for (int i = 1; i < (*ary).size(); i++) {
			if (n < pow((*ary)[i], 2)) break;
			if (n % (*ary)[i] == 0) {
				judge = false;
				break;
			}
		}
		if (judge) break;
		n += 2;
	}
	(*ary).push_back(n);
}

int main() {
	int n;
	cin >> n;
	cout << n << ":";
	vector<int> ret;
	vector<int> prime_numbers{ 2,3 };
	while (n % 2 == 0) {
		n /= 2;
		ret.push_back(2);
	}
	if (n != 1) {
		while (!judge_prime_numbers(n)) {
			if (n%prime_numbers.back() == 0) {
				n /= prime_numbers.back();
				ret.push_back(prime_numbers.back());
			}
			else make_new_prime_numbers(&prime_numbers);
		}
		ret.push_back(n);
	}
	for (int i = 0; i < ret.size(); i++) cout << " " << ret[i];
	cout << endl;
}

Measured memory_bytes: 3156
# Press the green button in the gutter to run the script.
if __name__ == '__main__':
    s = int(input())
    x = [list(map(int, input().split())) for i in range(1)]

    count = 0
    while True:
        flg = False
        for n in range(len(x[0])):
            if x[0][n] % 2 == 1:
                flg = True
                break
            x[0][n] = x[0][n] / 2
        if flg:
            break

        count = count + 1

    print(count)


Measured memory_bytes: 9156
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

int main()
{
    long long int N;
    long long int M;
    
    long long int P[100001];
    string S[100001];
    long long int OK[100001];
    long long int NG[100001];
    
    for(long long int i=0; i<100001; i++){
        OK[i] = 0;
        NG[i] = 0;
    }
    
    cin >> N;
    cin >> M;
    
    for(long long int i=0; i<M; i++){
        cin >> P[i];
        cin >> S[i];
        if(OK[P[i]] == 0){
            if(S[i] == "AC"){
                OK[P[i]] = 1;
            }
            else{
                NG[P[i]] += 1;
            }
        }
    }
    long long int true_count=0;
    long long int false_count=0;
    for(long long int i=0; i<N+1; i++){
//        if(OK[i] > 0){
//            cout << i << ":" << OK[i] << endl;
//        }
            
        true_count += OK[i];
        if(OK[i]>0){
            false_count += NG[i];
        }
    }
    cout << true_count << " " << false_count << endl;
    return 0;
}


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

using namespace std;
#define lint long long
#define P pair<lint, int>

lint F(lint a){
    if(a % 2 != 0){
        return ((a + 1) / 2) % 2;
    } else {
        return (a ^ ((a / 2) % 2));
    }
}

int main() {
    lint A, B;
    cin >> A >> B;

    cout << (F(A - 1) ^ F(B)) << endl;
}


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

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

const int MAXN=101010;
vector<int> AdList[MAXN];
int n,m,dp[MAXN];

int maxdfs(int i)
{
    if(dp[i]!=-1)
        return dp[i];
    int mpath=0;
    for(auto u : AdList[i])
    {
        mpath=max(mpath,1+maxdfs(u));
    }
    dp[i]=mpath;
    return dp[i];
}
int main(){
//    #ifdef Javier
//        freopen(".in", "r", stdin);
//    #endif // Javier

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        AdList[a].push_back(b);
    }

    int sol=INT_MIN;
    fill(dp,dp+n+1,-1);
    for(int i=1;i<=n;i++)
      {
          if(dp[i]!=-1)
          {
              continue;
          }
          else
          {
              dp[i]=maxdfs(i);
              sol=max(dp[i],sol);
          }
      }

     cout<<sol;

    return 0;
}



Measured memory_bytes: 8192
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b,c;
int zh(int x,int y,int z)
{
	int xy=0,tot=0,tnt=0;
	while(y)
	{
		if(y&1)
		{
			tot+=x;
			tnt+=xy;
			if(tot>=z)
			tot-=z,tnt++;
		}
		x=x*2;
		xy*=2;
		if(x>=z)
		{
			xy+=x/z;
			x-=x/z*z;
		}
		y>>=1;
	}
	return tnt;
}
signed main()
{
	scanf("%lld%lld%lld",&a,&b,&c);
	printf("%lld",zh(a,min(c,b-1),b));
	return 0;
}

Measured memory_bytes: 3812
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>

#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(x) (x).begin(),(x).end()

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

typedef long long ll;

using namespace std;


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

  int n;
  cin>>n;
  cout<<(double)(n-n/2)/(n)<<endl;
  return 0;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
#define SUM(a)  accumulate((a).begin(),(a).end(),0)
#define SORT(a) sort(ALL(a))
#define REV(a) reverse(ALL(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
typedef long long ll;
const int INTINF = 1<<30;
const ll LLINF = 1LL<<62;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
const int DX[8]={ 0, 1, 0,-1, 1, 1,-1,-1};
const int DY[8]={ 1, 0,-1, 0, 1,-1, 1,-1};


int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  set<int> st;
  int a,b,c;
  int sm = 0;
  cin >> a >> b >> c;
  while(1){
    sm = (sm + a) % b;
    if (sm==c){
        cout << "YES" << endl;
        break;
    }else{
        if (st.count(sm)==1){
            cout << "NO" << endl;
            break;
        }else{
            st.insert(sm);
        }
    }
  }
}


Measured memory_bytes: 256
#関数リスト
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
n, k = MI()
mylist = LI()

for i in range(n-k):
    last = mylist[i]
    update = mylist[k+i]
    if update > last:
        print("Yes")
    else:
        print("No")


Measured memory_bytes: 92044
import java.util.Scanner;

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

    int h = stdIn.nextInt();
    int w = stdIn.nextInt();

    String[] s = new String[h];
    for (int i = 0; i < h; i++) {
      s[i] = stdIn.next();
    }

    boolean answer = true;

    if (h == 1 && w == 1) {
      if (s[0].charAt(0) == '#') answer = false;
    } else if (h == 1 && w != 1) {
      if (s[0].charAt(0) == '#') {
        if (s[0].charAt(1) == '.') answer = false;
      }
      if (s[0].charAt(w-1) == '#') {
        if (s[0].charAt(w-2) == '.') answer = false;
      }

      for (int i = 1; i < w-1; i++) {
        if (s[0].charAt(i) == '#') {
          if (s[0].charAt(i-1) == '.' && s[0].charAt(i+1) == '.') answer = false;
        }
      }
    } else if (h != 1 && w == 1) {
      if (s[0].charAt(0) == '#') {
        if (s[1].charAt(0) == '.') answer = false;
      }
      if (s[h-1].charAt(0) == '#') {
        if (s[h-2].charAt(0) == '.') answer = false;
      }

      for (int i = 1; i < h-1; i++) {
        if (s[i].charAt(0) == '#') {
          if (s[i-1].charAt(0) == '.' && s[i+1].charAt(0) == '.') answer = false;
        }
      }
    } else {
      //キャンバス角の判定
      if (s[0].charAt(0) == '#') {
        if (s[0].charAt(1) == '.' && s[1].charAt(0) == '.') answer = false;
      }
      if (s[0].charAt(w-1) == '#') {
        if (s[0].charAt(w-2) == '.' && s[1].charAt(w-1) == '.') answer = false;
      }
      if (s[h-1].charAt(0) == '#') {
        if (s[h-2].charAt(0) == '.' && s[h-1].charAt(1) == '.') answer = false;
      }
      if (s[h-1].charAt(w-1) == '#') {
        if (s[h-2].charAt(w-1) == '.' && s[h-1].charAt(w-2) == '.') answer = false;
      }

      //キャンバス上の判定
      for (int i = 1; i < w-1; i++) {
        if (s[0].charAt(i) == '#') {
          if (s[0].charAt(i-1) == '.' && s[0].charAt(i+1) == '.' && s[1].charAt(i) == '.') answer = false;
        }
      }

      //キャンバス下の判定
      for (int i = 1; i < w-1; i++) {
        if (s[h-1].charAt(i) == '#') {
          if (s[h-1].charAt(i-1) == '.' && s[h-1].charAt(i+1) == '.' && s[h-2].charAt(i) == '.') answer = false;
        }
      }

      //キャンバス左の判定
      for (int i = 1; i < h-1; i++) {
        if (s[i].charAt(0) == '#') {
          if (s[i-1].charAt(0) == '.' && s[i+1].charAt(0) == '.' && s[i].charAt(1) == '.') answer = false;
        }
      }

      //キャンバス右の判定
      for (int i = 1; i < h-1; i++) {
        if (s[i].charAt(w-1) == '#') {
          if (s[i-1].charAt(w-1) == '.' && s[i+1].charAt(w-1) == '.' && s[i].charAt(w-2) == '.') answer = false;
        }
      }

      //キャンバス中央の判定
      for (int i = 1; i < h-1; i++) {
        for (int j = 1; j < w-1; j++) {
          if (s[i].charAt(j) == '#') {
            if (s[i-1].charAt(j) == '.' && s[i+1].charAt(j) == '.' && s[i].charAt(j-1) == '.' && s[i].charAt(j+1) == '.') answer = false;
          }
        }
      }
    }

    if (answer) {
      System.out.println("Yes");
    } else {
      System.out.println("No");
    }

  }
}


Measured memory_bytes: 21972
require 'pp'
# IS_DEBUG = true
IS_DEBUG = false
def dputs str
	if(IS_DEBUG)
		puts str
	end
end
def dpp str
	if(IS_DEBUG)
		pp str
	end
end


N,d=gets.chomp.split(' ').map{|n| n.to_i}
A=gets.chomp.split(' ').map{|n| n.to_i}

h = {}
def hadd (a,h)
	h[a].nil? ? h[a]=1 : h[a]+=1
end

(0..A.size-1).each{|i|
	hadd((A[i]-i),h)
}
size = A.size
nsum = 0
isum = 0
h.keys.sort.each{|key|
	if(nsum >= (size/2) +(size%2))
		break
	end
	isum = key
	nsum += h[key]
}

dpp h
dputs isum
dputs nsum
minsum = 0
(0..(A.size-1)).each{|i|
	minsum += (A[i]-i-isum).abs
}
puts minsum




Measured memory_bytes: 35816
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <complex>
#include <ctime>
#include <cstdlib>

using namespace std;

inline int to_int(string s) {int v; istringstream sin(s); sin >> v; return v;}
template<class T> inline string to_str(T x) {ostringstream sout; sout << x; return sout.str();}

const int INF = 1<<30;
const int MAX = 1000000;
typedef long long ll;

int main()
{
	bool dp[MAX+1]; // dp[i]
	bool prime[MAX+1];
	int n, m;
	memset(prime, true, sizeof(prime));

	for(int i = 2; i < sqrt(MAX); i++)
	{
		if(prime[i] == false)
		{
			continue;
		}
		for(int j = i*2; j < MAX; j += i)
		{
			prime[j] = false;
		}
	}

	while(cin >> n >> m ,n)
	{

		for(int i = 0; i <= MAX; i++)
		{
			dp[i] = false;
		}
		dp[0] = true;

		for(int i = 0; i < n; i++)
		{
			int x;
			cin >> x;
			for(int t = 0; t <= m-x; t++)
			{
				if(dp[t])
				{
					dp[t+x] = true;
				}
			}
		}

		int res = -1;
		for(int i = m; i >= 2; --i)
		{
			if(dp[i] && prime[i])
			{
				res = i;
				break;
			}
		}
		if(res ==  -1)
		{
			cout << "NA" << endl;
		}
		else
		{
			cout << res << endl;
		}

	}
}

Measured memory_bytes: 3120
#include <iostream>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#define fup(i,a,b) for(int i=a;i<=b;i++)
#define fdw(i,a,b) for(int i=a;i>=b;i--)
#define sync ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define cl(a) memset(a,0,sizeof(a))
using namespace std;
typedef long long ll;
const int N=1e6+10;
int a[N];
bool cmp(int a,int b)
{
    return a>b;
}
int main ()
{
    int n,k;
    cin>>n>>k;
    ll sum=0;
    fup(i,0,n-1)
    {
        cin>>a[i];
        sum+=a[i];
    }
    sort(a,a+n,cmp);
        fup(i,0,k-1)
        {
            sum-=a[i];
        }
    if(sum>0)
        cout<<sum<<endl;
    else cout<<0<<endl;
    return 0;
}


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

#define NDEBUG
#include <cassert>


typedef long long ll;
typedef long double Double;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<llll> vllll;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<long double> vD;

#define sz(a)  int((a).size())
#define pb  push_back
#define eb  emplace_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define repC3(vari,varj,vark,n)  for(int vari=0;vari<(n)-2;++vari)for(int varj=vari+1;varj<(n)-1;++varj)for(int vark=varj+1;vark<(n);++vark)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))
#define cons make_pair


int solve(int N, vi& a) {
    int ax = 0;
    vi mv(32, 0);
    rep(i,N) {
        ax ^= a[i];
        int x = a[i] ^ (a[i] - 1);
        int popcnt = __builtin_popcount(x);
        mv[popcnt - 1] = x;
    }
    if (ax == 0) return 0;

    int n = 32 - __builtin_clz(ax), cnt = 0;
    for (int i=n-1; i>=0; --i) {
        if (ax & (1 << i)) {
            if (!mv[i]) return -1;
            ax ^= mv[i];
            ++cnt;
        } else {
            continue;
        }
    }
    return cnt;
}

int main() {
    int N; scanf("%d", &N);
    vi a(N);
    rep(i,N) scanf("%d", &a[i]);
    cout << solve(N,a) << endl;
    return 0;
}


Measured memory_bytes: 640
#include<stdio.h>
#include<string.h>

int main(){
    char a[10], b[10], c[10];
    scanf("%s %s %s", a, b, c);
    int as = strlen(a);
    int bs = strlen(b);
    if(a[as-1]==b[0]&&b[bs-1]==c[0]){
        printf("YES\n");
    }else
    {
        printf("NO\n");
    }
}

Measured memory_bytes: 128
import collections

num = int(input())
a_i = list(map(int, input().split()))
anslist = collections.Counter(a_i)

ans = 0
for x in anslist.values():
    ans += x * (x - 1) // 2
for x in range(num):
    val = a_i[x]
    cnt = anslist[val]
    print(ans - (cnt - 1))

Measured memory_bytes: 26780
import static java.util.Arrays.deepToString;

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		new Main().run();
	}
	void tr(Object... os) {
		System.err.println(deepToString(os));
	}

	Scanner sc = new Scanner(System.in);
	public void run() {
		for (;sc.hasNext();) {
			int n = sc.nextInt();
			int m = sc.nextInt();
			if (n == 0 && m == 0) break;
			String[] ss = new String[m];
			for (int i = 0; i < m; i++) ss[i] = sc.next();
			solve(n, ss);
		}
	}
	
	void solve(int n, String[] ss) {
		P[] ps = new P[n];
		for (int i = 0; i < n; i++) ps[i] = new P();
		for (int i = 0; i < n; i++) {
			ps[i].next = ps[(i+1)%n];
			ps[i].prev = ps[(i-1+n)%n];
		}
		int died = 0;
		
		P current = ps[0];
		int num = 0;
		while (num < ss.length && n - died > 1) {
			String s = ss[num++];
			if (fizzbuzz(s, num)) {
				current = current.next;
			} else {
				died++;
				current.dead = true;
				current.next.prev = current.prev;
				current.prev.next = current.next;
				current = current.next;
			}
		}
		boolean first = true;
		for (int i = 0; i < n; i++) if (!ps[i].dead) {
			if (first) { first = false; } else System.out.print(" ");
			System.out.print(i+1);
		}
		System.out.println();
	}
	
	class P {
		boolean dead;
		P next;
		P prev;
	}
	
	boolean fizzbuzz(String s, int num) {
		if (num % 15 == 0) {
			return "FizzBuzz".equals(s);
		} else if (num % 3 == 0) {
			return "Fizz".equals(s);
		} else if (num % 5 == 0) {
			return "Buzz".equals(s);
		} else {
			try {
				int a = Integer.parseInt(s);
				return num == a;
			} catch (Exception e) {
				return false;
			}
		}
	}
}

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

int main() {
	int N,K;
	cin >> N >> K;
	vector<int> A(N), B(N,0);
	rep(i,N) cin >> A[i];

	rep(k,K) {
		// B_iの計算
		rep(i,N) B[i] = 0;
		rep(i,N) {
			int l_min = max(i-A[i],0);
			int l_max = min(i+A[i],N-1);
			//for (int j=l_min;j<=l_max;++j) B[j]++;
			B[l_min]++;
			if (l_max<N-1) B[l_max+1]--;
		}
		for (int i=1;i<N;i++) B[i]+=B[i-1];

		// A_iをB_iに更新
		rep(i,N) A[i] = B[i];

		// 出力
		/*
		printf("%2d: ", k+1);
		rep(i,N) printf("%2d ", A[i]);
		printf("\n");
		*/

		// 収束判定
		bool conv = true;
		rep(i,N) if (A[i]!=N) conv = false;
		if (conv) break;
	}

	rep(i,N) printf("%d ", A[i]);

	return 0;
}


Measured memory_bytes: 4836
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <math.h>
#include <ctype.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
typedef long long ll;
constexpr ll INF = 1000000000;
using namespace std;
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int n, q;
	cin >> n >> q;
	string s;
	cin >> s;

	vector<int>l(q + 1);
	vector<int>r(q + 1);
	rep(i, q)cin >> l[i] >> r[i];

	//累積部分文字列
	vector<int>count(n);
	for (int i = 1; i < n; i++) {
		if (s[i - 1] == 'A' && s[i] == 'C') {
			count[i]++;
		}
	}
	//n文字目までに"AC"がいくつ登場するかカウント
	vector<int>x(n);
	for (int i = 1; i < n; i++) {
		x[i] = x[i - 1] + count[i];
	}
	
	//l_iとr_iを読んで出力
	vector<int>ans(q);
	ans[0] == 0;
	for (int i = 0; i < q; i++) {
		ans[i] = x[r[i] - 1] - x[l[i] - 1];
	}

	rep(i, q)cout << ans[i] << endl;
}

Measured memory_bytes: 3024
#include<bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(0)
#define loop(i, a, b) for(lli i=a; i<b; i++)
#define loopb(i, a, b) for(lli i=a; i>=b; i--)
#define pb push_back
#define umap unordered_map
typedef long long int lli;
typedef pair<lli, lli> pii;
typedef vector<lli> vll;
typedef pair<lli, pii> ppi;
typedef tree<lli, null_type, less<lli>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// use to avoid collision
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
// for pair in unordered_map
struct hash_pair {
    static uint64_t splitmix64(uint64_t x) {
    // http://xorshift.di.unimi.it/splitmix64.c
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
    }
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const{
        auto hash1 = hash<T1>{}(p.first);
        auto hash2 = hash<T2>{}(p.second);
        uint64_t x = hash1 ^ hash2;
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
lli M = 1e9 + 7;
lli power(lli x, lli y){
    lli res = 1;
    x = x%M ;
    while (y > 0) {
        if (y & 1)
            res = (res*x)%M ;
        y = y>>1;
        x = (x*x)%M;
    }
    return res%M;
}
lli solve(){
    lli n;
    cin>>n;
    vll A(n);
    loop(i, 0, n)
        cin>>A[i];
    bool flag = true;
    loop(i, 0, n){
        if(A[i]%2 == 0 && (A[i] %3 == 0 || A[i] % 5 == 0))
            continue;
        else if(A[i]%2 != 0)
            continue;
        else
            flag = false;
    }
    if(flag)
        cout<<"APPROVED\n";
    else
        cout<<"DENIED\n";
    return 0;
}
int main(){
    fastio;
    lli t;
    // cin>>t;
    t = 1;
    while(t>0){
        t--;
        solve();
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define fileio freopen("in.in", "r", stdin),freopen("out.out", "w", stdout);
#define ll long long int
#define FF first
#define SS second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define pll pair<long long int,long long int>
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define pd(x) printf("%d\n",x)
#define plld(x) printf("%lld\n",x)
#define pss printf
#define MOD 1000000007
#define INF 1e18
#define eps 0.00001
#define endl '\n'
#define debug(n1) cout<<n1<<endl

string s;
int main() {
cin>>s;
ll n=s.length();
ll ans=9*(s.length()-1);
ll an=0;
for(int i=0;i<s.length();i++)
{
	an+=s[i]-'1';
	if(s[i]!='0')ans=max(ans,an+9ll*(n-i-1));
	an=an+(s[i]-'0')-(s[i]-'1');
}
ans=max(ans,an);
cout<<ans<<endl;
	return 0;
           } 

Measured memory_bytes: 256
#include<stdio.h>

#define vMAX 10001
#define nMAX 2000001
int n,A[nMAX],B[nMAX];

void CountingSort(void){
	int i,cnt[vMAX];
	for(i=0;i<vMAX;i++){
		cnt[i]=0;
	}

	for(i=0;i<n;i++){
		cnt[ A[i] ]++;
	}

	for(i=1;i<vMAX;i++){
		cnt[i]+=cnt[i-1];
	}

	for(i=0;i<n;i++){
		B[ cnt[A[i]] ]=A[i];	cnt[A[i]]--;
	}
}

int main(){
	int i;
	scanf("%d",&n);

	for(i=0;i<n;i++)scanf("%d",&A[i]);
	CountingSort();
	for(i=1;i<=n;i++){
		if(i>1)printf(" ");
		printf("%d",B[i]);
	}printf("\n");
	return 0;
}


Measured memory_bytes: 18396
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class AtCoderA
{
    static void Main()
    {
        var sc = new Scanner();

        long n = sc.NextLong();
        long k = sc.NextLong();
        long[] a = sc.LongArray();

        long[] count = new long[n + 1];
        for (long i = 0; i < count.Length; i++)
        {
            count[i] = -1;
        }

        long loopStart = 0;
        long loopSpan = 0;
        long current = 1;
        long step = 0;
        while (true)
        {
            if (count[current] == -1)
            {
                count[current] = step;
            }
            else
            {
                loopStart = count[current];
                loopSpan = step - count[current];
                break;
            }
            current = a[current - 1];
            step++;
        }

        if (loopSpan != 0 && k > loopStart)
        {
            k = loopStart + ((k - loopStart) % loopSpan);
        }

        long answer = 0;

        for (long i = 0; i <= n; i++)
        {
            if (count[i] == k)
            {
                answer = i;
                break;
            }
        }

        Console.WriteLine(answer);
    }

    class Scanner
    {
        private string[] _line;
        private int _index;
        private const char Separator = ' ';

        public Scanner()
        {
            _line = new string[0];
            _index = 0;
        }

        public string Next()
        {
            while (_index >= _line.Length)
            {
                _line = Console.ReadLine().Split(Separator);
                _index = 0;
            }

            return _line[_index++];
        }

        public int NextInt() => int.Parse(Next());
        public long NextLong() => long.Parse(Next());
        public double NextDouble() => double.Parse(Next());
        public decimal NextDecimal() => decimal.Parse(Next());
        public char NextChar() => Next()[0];
        public char[] NextCharArray() => Next().ToCharArray();

        public string[] Array()
        {
            _line = Console.ReadLine().Split(Separator);
            _index = _line.Length;
            return _line;
        }

        public int[] IntArray() => Array().Select(int.Parse).ToArray();
        public long[] LongArray() => Array().Select(long.Parse).ToArray();
        public double[] DoubleArray() => Array().Select(double.Parse).ToArray();
        public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray();
    }
}

Measured memory_bytes: 45372