akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;
 
int main(){
    int a,b,c,d,n,i,j,k;
 
    cin >> k >> a >> b;
  
    for(i=a;i<=b;i++){
      if(i%k==0){
        cout << "OK" << endl;
        return 0;
      }
    }
 
    cout << "NG" << endl;
}

Measured memory_bytes: 3636
using System;
class Program
{
	static void Main(string[] args)
	{
        string[] input = Console.ReadLine().Split(' ');
        int n = int.Parse(input[0]);
        int m = int.Parse(input[1]);

        if(n == m)
        {
            Console.WriteLine("Yes");
        }
        else
        {
            Console.WriteLine("No");
        }
	}
}


Measured memory_bytes: 11092
#define _USE_MATH_DEFINES
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
#include <random>
using namespace std;

#define rep(i, N) for (int i = 0; i < N; i++)
#define pb push_back

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };

ll MOD = 1000000007;
ll _MOD = 1000000009;
int INF = INT_MAX / 2;
double EPS = 1e-10;

int main() {
	string s; cin >> s;
	int N = s.length();
	vector<bool> dp(N + 1);
	dp[0] = true;
	for (int i = 0; i <= N; i++) {
		if (!dp[i]) continue;
		if (i + 5 <= N && s.substr(i, 5) == "dream")
			dp[i + 5] = true;
		if (i + 7 <= N && s.substr(i, 7) == "dreamer")
			dp[i + 7] = true;
		if (i + 5 <= N && s.substr(i, 5) == "erase")
			dp[i + 5] = true;
		if (i + 6 <= N && s.substr(i, 6) == "eraser")
			dp[i + 6] = true;
	}
	cout << (dp[N] ? "YES" : "NO") << endl;
}


Measured memory_bytes: 512
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <complex>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#define debug(x) cerr << #x << " = " << (x) << endl;


#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 100010


int main(){
  int n;
  int a, counter[SIZE] = {};
  scanf("%d",&n);

  for(int i=0;i<n;i++){
    scanf("%d",&a);
    counter[a]++;
  }

  int ans = 0;
  
  for(int x=1;x<=100000;x++){
    ans = max(ans, counter[x-1] + counter[x] + counter[x+1]);
  }

  printf("%d\n",ans);
  
  return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <list>
#include <utility>
#include <tuple>
#include <cstdio>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <cmath>
#define _GLIBCXX_DEBUG
using namespace std;
const long long INF = 1LL << 60;
typedef long long ll;
int main() {
    int X;
    cin >> X;
    int next_prime;
    bool frg1 = false;
    bool frg2 = false;
    if(X==2){
        next_prime = 2;
    }
    else{
        for(int i=X;i>=X;i++){
        for(int j=2;j<i;j++){
            if(i%j==0){
                break;
            }
            else if(j==i-1){
                next_prime = i;
                frg1 = true;
                break;
            }
        }
        if(frg1){
            break;
        }
    }
    }
    
    cout << next_prime << endl;
}

Measured memory_bytes: 3620
n = gets.to_i
robots = []
n.times do
  robots << gets.split.map(&:to_i)
end
robots.sort_by!{|x,l| x+l}
r = -10**10
ans = 0
robots.each do |x,l|
  next if r > x-l
  r = x+l
  ans += 1
end
p ans


Measured memory_bytes: 12664
using System;
using System.Collections.Generic;
using CompLib.Util;

public class Program
{
    private int X, Y, A, B, C;
    private int[] P, Q, R;

    public void Solve()
    {
        var sc = new Scanner();
        X = sc.NextInt();
        Y = sc.NextInt();
        A = sc.NextInt();
        B = sc.NextInt();
        C = sc.NextInt();
        P = sc.IntArray();
        Q = sc.IntArray();
        R = sc.IntArray();

        Array.Sort(P, (l, r) => r.CompareTo(l));
        Array.Sort(Q, (l, r) => r.CompareTo(l));
        Array.Sort(R, (l, r) => r.CompareTo(l));

        var ls = new List<int>();
        long sum = 0;
        for (int i = 0; i < X; i++)
        {
            ls.Add(P[i]);
            sum += P[i];
        }

        for (int i = 0; i < Y; i++)
        {
            ls.Add(Q[i]);
            sum += Q[i];
        }

        ls.Sort();

        // lsの sum[0,i]と Rのsum[0,R]の差の最大
        int c = Math.Min(C, X + Y);
        var lSum = new long[c + 1];
        var rSum = new long[c + 1];
        for (int i = 1; i <= c; i++)
        {
            lSum[i] = lSum[i - 1] + ls[i - 1];
            rSum[i] = rSum[i - 1] + R[i - 1];
        }

        int index = -1;
        long max = long.MinValue;
        for (int i = 0; i <= c; i++)
        {
            if (max < rSum[i] - lSum[i])
            {
                max = rSum[i] - lSum[i];
                index = i;
            }
        }

        sum += max;
        Console.WriteLine(sum);

    }


    public static void Main(string[] args) => new Program().Solve();
}

namespace CompLib.Util
{
    using System;
    using System.Linq;

    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: 43624
#include<iostream>
#include<string>
using namespace std;
int main()
{
    string a,b;
    int n,j;
    cin>>n;
    cin>>a>>b;
    char a1[2*n];
    for(int i=0,j=0;i<n;i=i+1,j=j+2)
    {
        a1[j]=a[i];
        a1[j+1]=b[i];
    }
    for(int j=0;j<2*n;j=j+1)
    {
        cout<<a1[j];
    }
}


Measured memory_bytes: 256
#include<iostream>
#include <algorithm>
#include<string>
#include <numeric>
#include<math.h>
#include <bits/stdc++.h>
using namespace std;

int main(void) {
    int a,b;
    cin>>a>>b;
    int s[3];
    s[0]=a+b;
    s[1]=a-b;
    s[2]=a*b;
    sort(s,s+3);
    cout<<s[2]<<endl;
}


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

int main(){

  int balls[100005], containsRed[100005];
  int n, m;
  cin >> n >> m;

  for(int i=1; i<=n; i++){
    balls[i] = 1;
    containsRed[i] = (i==1);
  }

  for(int i=1; i<=m; i++){
    int x, y;
    cin >> x >> y;
    if(containsRed[x]) containsRed[y] = true;
    balls[x]--;
    balls[y]++;
    if(balls[x] == 0){
      containsRed[x] = false;
    }
  }

  int ans = 0;
  for(int i=1; i<=n; i++) ans += containsRed[i];
  cout << ans << endl;
  return 0;
}

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

//const long double PIL = 3.141592653589793238462643383279502884L;
//const double PI = 3.14159265358979323846;

#define sz(a) int((a).size())
#define all(c) (c).begin(), (c).end()
#define debug(v) {for (auto z : v) {cerr << z << ' ';} cerr << endl;}

using ll = long long;
using ii = pair<int,int>;
using vi = vector<int>;
using vll = vector<long long>;
using vii = vector<pair<int,int>>;

int main() {
	//~ ios::sync_with_stdio(0);
	//~ cin.tie(0);
	//~ cout.tie(0);
	int h, a;
	scanf("%d%d", &h, &a);
	int ans = h / a;
	if (h%a) ++ans;
	printf("%d\n", ans);
}


Measured memory_bytes: 256
N, Q = map(int, input().split())
S = str(input())

l = [0]*N
count = 0

for i in range (1, N):
	if S[i-1] == 'A' and S[i] == 'C':
		count+=1
		l[i] = count
	else:
		l[i] = count

for i in range(0, Q):
	O, P = map(int, input().split())
	print(l[P-1] - l[O-1])


Measured memory_bytes: 6084
#include<stdio.h>
#include<string.h>
int main(void)
{
  int a,b;
  int cnt=0;
  char suji[6];
  char tmp[4];
  int len,center,flg;
  
  scanf("%d %d",&a,&b);
  for(int i=a;i<=b;i++){
    flg=0;
    sprintf(suji,"%d",i);
    len=strlen(suji);
    if(len%2==0){
      center=len/2;
    }else{
      center=len/2+1;
    }
    for(int j=0;j<center;j++){
      if(suji[j]!=suji[len-j-1]){
        flg=1;
        break;
      }
    }
    if(flg==0){
      cnt++;
    }
  }
  printf("%d\n",cnt);
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <stddef.h>
#include <stack>
#include <queue>

using namespace std;

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

}

Measured memory_bytes: 1156
# ABC143 D Triangles

import bisect

n = int(input())
l_list = [int(x) for x in input().split()]

l_list.sort()
ans = 0

for i in range(n-2):
    _a = l_list[i]
    for j in range(i+1,n-1):
        _b = l_list[j]
        _tmp = bisect.bisect_left(l_list, _a+_b)
        if j < _tmp:
            ans += _tmp - j - 1

print(ans)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#define all(V) V.begin(),V.end()

int main(){
	int N, s = 0;
	cin >> N;
	vector<int> S(N);
	for (int i = 0;i < N;i++) {
		cin >> S[i];
		s += S[i];
	}
	if (s % 10 == 0) {
		sort(all(S));
		for (int i = 0;i < N;i++) {
			if (S[i] % 10) {
				s -= S[i];
				break;
			}
			if (i == N - 1) s = 0;
		}
	}
	cout << s << endl;
}

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

typedef long long ll;

int main() {
	ll a[5];
	for (int i = 0; i < 5; i++) {
		cin >> a[i];
	}
	sort(a, a + 5);
	for (int i = 0; i < 5; i++) {
		if (i) cout << " ";
		cout << a[4 - i];
	}
	cout << endl;
}


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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }

const int maxn = 1e6 + 11;

int main() {

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

  string s; cin >> s;
  int n = s.size();

  string ans = "";
  while (n--) {
    ans += 'x';
  }
  out(ans);

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define EFOR(i,a,b) for(ll i=(a);i<=(b);++i)
#define REP(i, n) FOR(i,0,n)
const int MOD = 1000000007;

// 逐次MODを取りながら累乗の計算
ll MODPOW(ll x,ll N){
    ll res = 1;
    FOR(i,0,N){
        res = res * x % MOD;
    }
    return res;
}

int main(void){
    ll N;
    cin >> N;
    ll ans = MODPOW(10,N) - MODPOW(9,N) - MODPOW(9,N) + MODPOW(8,N);
    ans %= MOD;
    ans = (ans + MOD) % MOD;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3592
#include<stdio.h>
#include<string.h>
int main(void)
{
	int a,b,i,len;
	char s[200000];
	scanf("%s",s);
	len=strlen(s);
	for(i=0;i<len;i++){
		if(s[i]=='A'){
			a=i;
			break;
		}
	}
	for(i=a+1;i<len;i++){
		if(s[i]=='Z'){
			b=i;
		}
	}
	printf("%d\n",b-a+1);
	return 0;
	}

Measured memory_bytes: 384
// header {{{
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <complex>
#include <utility>
#include <string>
#include <sstream>
#include <queue>
#include <map>
#include <list>
#include <set>
#include <stack>
#include <tuple>
#include <cstdio>
#include <cmath>
using namespace std;

#define ALPHABET    26
#define EPS         (1e-10)
#define EQ(a, b)    (abs((a)-(b)) < EPS)
#define INF         1000000005

typedef long long ll;
typedef unsigned long long ull;
// }}}

ll f(ll b, ll n) {
    if(n < b){
        return n;
    }else{
        return f(b, n/b) + n%b;
    }
}

int main() {
    ll n, s;cin >> n >> s;
    if(s == n){
        printf("%lld\n", n+1LL);
        return 0;
    }
    if(s > n){
        printf("%d\n", -1);
        return 0;
    }
    for(ll b=2LL;b*b<=n;b++){
        if(f(b, n) == s){
            printf("%lld\n", b);
            return 0;
        }
    }
    vector<ll> ans;
    for(ll p=1LL;p*p<n;p++){
        ll b = (n-s)/p+1LL;
        if((n-s)%p == 0){
            if(f(b, n) == s){
                ans.push_back(b);
            }
        }
    }
    if(ans.size() == 0){
        printf("%d\n", -1);
    }else{
        printf("%lld\n", *min_element(ans.begin(), ans.end()));
    }
    return 0;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
qs = []
for _ in range(M):
  u, v = map(int, input().split())
  qs.append((u, v))
qs.reverse()
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1] * (n + 1)
    self.rnk = [0] * (n + 1)

  def Find_Root(self, x):
    if self.root[x] < 0:
      return x
    else:
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]

  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if x == y:
      return 
    elif self.rnk[x] > self.rnk[y]:
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if self.rnk[x] == self.rnk[y]:
        self.rnk[y] += 1

  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  def Count(self, x):
    return -self.root[self.Find_Root(x)]
uf = UnionFind(N)
res = [N * (N - 1) // 2]
for u, v in qs:
  if uf.isSameGroup(u, v):
    res.append(res[-1])
  else:
    res.append(res[-1] - uf.Count(u) * uf.Count(v))
  uf.Unite(u, v)
res.reverse()
for r in res[1: ]: print(r)

Measured memory_bytes: 103516
n = int(input())
order = list(map(lambda x : int(x)-1, input().split()))
sats = list(map(int, input().split()))
bonus = list(map(int, input().split()))

bef = 21
ans = 0
for i in order:
  ans += sats[i]
  if i == bef + 1:
    ans += bonus[i - 1]
  bef = i

print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define mod 1000000007
using ll = long long;
using namespace std;
int main(){
  int x;
  cin >> x;
  for(ll i = -1000; i <= 1000; i++){
    for(ll j = -1000; j <= 1000; j++){
      if(pow(i, 5) - pow(j, 5) == x){
        cout << i << " " << j << endl;
        return 0;
      }
    }
  }
}

Measured memory_bytes: 3992
N = int(input())
p = list(map(int, input().split()))

ans = sorted(p)

if p == ans:
    print ('YES')
    exit()

for i in range(N -1):
    for j in range(i + 1, N):
        p[i], p[j] = p[j], p[i]
        if p == ans:
            print ('YES')
            exit()
        else:
            p[i], p[j] = p[j], p[i]

print ('NO')

Measured memory_bytes: 3064
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Linq.Expressions;
using System.Text;
class Simple
{
    //////////////////////////////
    void Solve() {
        //input
        var N = io.Int;
        var t = new int[N + 1];
        var x = new int[N + 1];
        var y = new int[N + 1];
        t[0] = 0;
        x[0] = 0;
        y[0] = 0;
        for (int i = 1; i < N + 1; ++i) {
            t[i] = io.Int;
            x[i] = io.Int;
            y[i] = io.Int;
        }
        //cal
        Func<int, int, int, int, int> mdis = (x1, y1, x2, y2) =>
                                            Math.Abs(x2 - x1) + Math.Abs(y2 - y1);
        Func<int, int, bool> isEnable = (time, distance) => distance <= time && (distance - time) % 2 == 0;
        for (int i = 1; i < N + 1; ++i) {
            var cd = mdis(x[i - 1], y[i - 1], x[i], y[i]);
            var ct = t[i] - t[i - 1];
            if (!isEnable(ct, cd)) {
                Console.WriteLine("No");
                return;
            }
        }
        Console.WriteLine("Yes");
    }
    //////////////////////////////
    SimpleIO io = new SimpleIO();
    public static void Main(string[] args) { new Simple().Stream(); }
    void Stream() { Solve(); io.writeFlush(); }
}
class SimpleIO
{
    string[] nextBuffer;
    int BufferCnt;
    char[] cs = new char[] { ' ' };
    StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
    public SimpleIO() {
        nextBuffer = new string[0];
        BufferCnt = 0;
        Console.SetOut(sw);
    }
    public string Next() {
        if (BufferCnt < nextBuffer.Length)
            return nextBuffer[BufferCnt++];
        string st = Console.ReadLine();
        while (st == "")
            st = Console.ReadLine();
        nextBuffer = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        BufferCnt = 0;
        return nextBuffer[BufferCnt++];
    }
    public string String => Next();
    public char Char => char.Parse(String);
    public int Int => int.Parse(String);
    public long Long => long.Parse(String);
    public double Double => double.Parse(String);
    public void writeFlush() { Console.Out.Flush(); }
}


Measured memory_bytes: 15280
//インクルード(アルファベット順)
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

using namespace std;
typedef long long ll;

//マクロ
//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素



signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int a,b;
    cin >> a>>b;
    int x=(a+b)*0.5+0.9;
    cout<< x<<endl;
    
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long N = sc.nextLong();
        int K = sc.nextInt();
        int count = 1;
        while (N >= K) {
            //System.out.println(N);
            N /= K;            
            count++;
        }
        System.out.println(count);
    }
}

Measured memory_bytes: 23892
var abc="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ".split("");
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var Arr=(input.trim()).split("\n");
while(true){
   var n=Arr.shift()-0;
   if(n==0)break;
   var k=(Arr.shift()).split(" ").map(Number);
   var arr=(Arr.shift()).split("");
   var j=0;
   for(var i=0;i<arr.length;i++){
      var num=abc.indexOf(arr[i])-k[i%k.length];
      if(num<0)num+=abc.length;
      arr[i]=abc[num];
   }
   console.log(arr.join(""));
}

Measured memory_bytes: 8700
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <fstream>
#include <sstream>
#include <iomanip>
#define ll long long

using namespace std;

long long MOD = 998244353;

template<typename T>
void cout_vec(vector<T> &vec){
    for(int i=0; i<vec.size(); i++){
        if (i!=0){
            cout << ' ';
        }
        cout << vec[i];
    }
    cout << endl;
}

int main(){
    int N, S;
    cin >> N >> S;
    vector<ll> A(N,0);
    for(auto &a:A){
        cin >> a;
    }

    vector<ll> dp(S+1,0);
    dp[0]=1;
    ll ans=0;

    for(int i=0; i<N; i++){
        ll a=A[i];
        for(int j=S-a; j>=0; j--){
            if(j==0){
                dp[a]+=(ll) i+1;
                dp[a]%=MOD;
            }else{
                dp[j+a]+=dp[j];
                dp[j+a]%=MOD;
            }
        }
        //cout_vec(dp);
        ans+=dp[S];
        ans%=MOD;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
/*
by:-  
                     _ __ ___ 119574 
                    | '__/ __| 
                    | |  \__ \ 
                    |_|  |___/ 
                    

*/ 

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double db;
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define rep(i,n) for (ll i = 0; i < (ll)(n); ++i) 
#define endl "\n"
const ll mod=1e9+7;
const db eps=1e-9;
const double pi=acos(-1);


void solve(){
ll n,k;
cin>>n>>k;
n-=k;
if(k==1)n=0;
cout<<max(n,0LL)<<endl;


	return;
}
signed main(){
	IOS;
	ll t=1;
// 	cin>>t;
	while(t--)solve();
fflush(stdout);return 0;
}

Measured memory_bytes: 256
open Batteries
module EnumL = Enum.Labels
module ListL = List.Labels
module ArrayL = Array.Labels

let dbg0 x = Printf.eprintf "[debug]%s\n" @@ dump x
let dbg1 x = dbg0 x; x

let id = identity

let (++) n m = List.range n `To m
let (++-) n m = if n >= m then List.range n `Downto m else []
let (++^) n m = if n < m then List.range n `To (pred m) else []

let scan fmt = Scanf.sscanf (read_line ()) fmt

let scan_lines n fmt f =
  if n = 0 then []
  else List.map (fun _ -> scan fmt f) (1 ++ n)

let scan_list ?sep cnv =
  let line = read_line () in
  (match sep with
   | None -> List.map String.of_char @@ String.to_list line
   | Some sep -> String.split_on_char sep line)
  |> List.map cnv

let scan_array ?sep cnv = Array.of_list @@ scan_list ?sep cnv

let scan_matrix n m e ?sep conv =
  let arr = Array.make_matrix n m e in
  ListL.iter (0 ++^ n)
    ~f:(fun i -> arr.(i) <- Array.of_list @@ scan_list ?sep conv);
  arr

let atoi c = Char.code c - Char.code '0'

let rec powerset = function
  | [] -> [[]]
  | hd::tl ->
    let pws =  powerset tl in
    pws @ ListL.map pws ~f:(fun pw -> hd::pw)

let permutations l =
  let rec interleave x = function
    | [] -> [[x]]
    | (hd::tl) as l ->
      (x::l) :: (interleave x tl |> ListL.map ~f:(fun l -> hd::l)) in
  let rec aux = function
    | [] -> [[]]
    | a::rest ->
      aux rest |> ListL.map ~f:(interleave a) |> List.concat in
  aux l

let intersection l =
  EnumL.filter ~f:(fun x -> EnumL.exists ~f:((=) x) @@ Enum.clone l)

let zip l m =
  let n = min (List.length l) (List.length m) in
  List.combine (List.take n l) (List.take n m)

let lower_bound n f =
  let rec aux l u =
    if u - l > 1 then
      let m = (l + u) / 2 in
      if f m then aux l m
      else aux m u
    else u in aux (-1) n

let between n x m = n <= x && x < m

let (n,m) = scan "%d %d" Tuple2.make
let ls = ListL.map (0++^m) ~f:(fun _ ->
    List.tl @@ scan_list ~sep:' ' Int.of_string)
let p  = scan_array ~sep:' ' Int.of_string

let () =
  let sets = powerset (1 ++ n) in
  ListL.map sets ~f:(fun set ->
      if ListL.for_all (ListL.mapi ls ~f:Tuple2.make) ~f:(fun (i, ss) ->
          (ListL.map ss ~f:(fun s ->
               (if ListL.exists set ~f:((=) s) then 1 else 0))
           |> List.sum) mod 2 = p.(i))
      then 1 else 0)
  |> List.sum
  |> Printf.printf "%d\n"


Measured memory_bytes: 3200
/*
g++ -std=c++11 -o2 -Wall AISing2019A0.cpp -o .\out\AISing2019A0.out
.\out\AISing2019A0.out
*/

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main(){
//  freopen("./input/input.txt", "r", stdin);
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n[4];
  for (int i = 0; i < 4; ++i) cin >> n[i];
  sort(begin(n), end(n));
  if (n[0]==1&&n[1]==4&&n[2]==7&&n[3]==9) cout << "YES\n";
  else cout <<"NO\n";
}


Measured memory_bytes: 256
from collections import defaultdict
import sys
input = sys.stdin.readline


class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


def main():
    N, K, L = map(int, input().split())
    A = UnionFind(N)
    for _ in range(K):
        p, q = map(int, input().split())
        A.Unite(p, q)
    B = UnionFind(N)
    for _ in range(L):
        s, r = map(int, input().split())
        B.Unite(s, r)
    
    d = defaultdict(int)
    C = []
    for i in range(N):
        a = A.Find_Root(i+1)
        b = B.Find_Root(i+1)
        C.append(str(a)+","+str(b))
        d[C[i]] += 1
    # print(C)
    # print(d)

    ans = [str(d[c]) for c in C]
    print(" ".join(ans))


if __name__ == '__main__':
    main()

Measured memory_bytes: 122412
#include<bits/stdc++.h>
using namespace std;
int n;
map<int,int>per;
int main()
{
	scanf("%d",&n);
	int rnk=0;
	for(int i=0;i<n;i++){
		scanf("%d",&rnk);
		per[rnk]=i+1;
	}
	int cnt=0;
	for(map<int,int>::iterator i=per.begin();i!=per.end();i++){
		if(cnt++) printf(" ");
		printf("%d",i->second);
	}
	return 0;
} 

Measured memory_bytes: 5504
def f(h, w):
    t = [input() for _ in range(h)]
    U = [[0] * (w + 2) for _ in range(h + 2)]
    D = [[0] * (w + 2) for _ in range(h + 2)]
    L = [[0] * (w + 2) for _ in range(h + 2)]
    R = [[0] * (w + 2) for _ in range(h + 2)]
    ans = 0
    Ui1 = U[0]
    for i in range(1, 1 + h):
        Ui = U[i]
        Li = L[i]
        ti1 = t[i - 1]
        for j, tk in enumerate(ti1):
            j += 1
            if tk == "#":
                Ui[j] = 0
                Li[j] = 0
            else:
                Ui[j] = Ui1[j] + 1
                Li[j] = Li[j - 1] + 1
        Ui1 = Ui
        Di1 = D[-1]
    for i in range(h, 0, -1):
        Ui = U[i]
        Li = L[i]
        Di = D[i]
        Ri = R[i]
        ti1 = t[i - 1]
        for j,tk in enumerate(ti1[::-1]):
            j=w-j
            if tk == "#":
                Di[j] = 0
                Ri[j] = 0
            else:
                Di[j] = Di1[j] + 1
                Ri[j] = Ri[j + 1] + 1
                tmp = Ui[j] + Di[j] + Li[j] + Ri[j]
                if tmp > ans:
                    ans = tmp
        Di1 = Di
    print(ans - 3)

h, w = map(int, input().split())
f(h, w)


Measured memory_bytes: 180484
#include<bits/stdc++.h>
#define endl "\n"
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int INF=1e9+5; 
int main()
{
	fastio;
	int n,k;
	cin>>n>>k;
	vector<int> h(n+1);
	for(int i=0;i<n;i++)
		cin>>h[i+1];
	vector<int>dp(n+1,INF);

	dp[1]=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=i+k && j<=n;j++)
		{
			dp[j]=min(dp[j],dp[i]+abs(h[i]-h[j]));
		}
	}
	cout<<dp[n]<<endl;
}

Measured memory_bytes: 1024
/*------------------------------------
........Bismillahir Rahmanir Rahim....
..........created by Abdul Aziz.......
------------------------------------*/
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <unordered_map>
#include <queue>
#define   mod  998244353
#define   int  long long 
#define   ld   long double
#define   pb   push_back
#define   vi  vector<int> 
#define   dbg(x)  cerr << #x << " = " << x << '\n'
#define   sz(x)  (int)x.size()
#define   all(a) (a.begin(),a.end())
#define   ff   first
#define   ss   second
#define   pii  pair<int,int> 
#define   lcm(a,b) (a*b)/__gcd(a,b) 
using namespace std;

inline void solve(){
    string s; int k;
    cin >> s >> k ; 
    for (int i=0;i<sz(s)-1;i++){
        int x = s[i] - 'a' + 1 ; 
        if (x != 1 and  k >= 27-x ){ 
            k -= (27-x);
            s[i] = 'a';
        }
    }
    k %= 26;
    for (int i=1;i<=k;i++){
      s[sz(s)-1]++;
      if (s[sz(s)-1]>'z') s[sz(s)-1]='a';
    }
    cout << s << endl;
}

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


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

typedef struct num
{
	long long int i;
	int n;
};

int main()
{
	int N;

	cin >> N;

	long long int a[N];

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

	map<int, int> mp;

	for (int i = 0; i < N; i++)
	{
		mp[a[i]]++;
	}

	long long int count = 0;

	for (auto p : mp)
	{
		if (p.first > p.second)
		{
			count += p.second;
		}
		else
		{
			count += p.second - p.first;
		}
	}

	cout << count << endl;

	return 0;
}


Measured memory_bytes: 5504
lq = []
lw = []
key = str(input()).lower()
while True:
    s = list(map(str, input().split()))
    if s[0] == "END_OF_TEXT":
        break
    lq.append(s)
for i in range(len(lq)):
    lw = lw + lq[i]
r = 0
for i in range(len(lw)):
    if lw[i].lower() == key:
        r = r + 1
print(r)


Measured memory_bytes: 5560
using System;
using System.Linq;

namespace Computation
{
    class A_B_Problem
    {
        static void Main(string[] args)
        {
            var token = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
            var d = token[0] / token[1];
            var r = token[0] % token[1];
            var f = token[0] / (double)token[1];
            Console.WriteLine("{0} {1} {2:F7}", d, r ,f);
        }
    }
}

Measured memory_bytes: 9628
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<long long> a,f;
long long k;
int n;
bool ch(long long x){
	int i;
	long long sum = 0;
	for(i=0;i<n;i++){
		if(a[i]*f[i]<=x) continue;
		long long y = x/f[i];
		sum += max(0LL,a[i] - y);
	}
	if(sum<=k) return true;
	return false;
}

int main(){
	int i;
	cin >> n >> k;
	for(i=0;i<n;i++){
		long long x; cin >> x;
		a.push_back(x);
	}
	for(i=0;i<n;i++){
		long long y; cin >> y;
		f.push_back(y);
	}
	long long s = 0;
	for(i=0;i<n;i++){
		s += a[i];
	}
	if(s<=k){
		cout << 0 << endl;
		return 0;
	}
	sort(a.begin(),a.end());
	sort(f.rbegin(),f.rend());
	long long l = 0,r = 10000000000000;
	while(r - l>1){
		long long mid = (l + r)/2;
		if(ch(mid)) r = mid;
		else l = mid;
	}
	cout << r << endl;
}

Measured memory_bytes: 4848
import bisect
N=int(input())
X=list(map(int,input().split()))

if N==2:
    print(X[-1])
    print(X[0])
else:
    sortedX=sorted(X)
    num=N//2-1
    for x in X:
        if x<=sortedX[num]:print(sortedX[num+1])
        else:print(sortedX[num])


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

inline void toLower(string& s) {
	for (int i = 0; i < s.length(); i++) {
		if (isupper(s[i])) s[i] = tolower(s[i]);
	}
}

int main() {
	string k, w, e("END_OF_TEXT");
	int c = 0;
	cin >> k;
	toLower(k);
	while (cin >> w) {
		toLower(w);
		if (w == k) c++;
		if (w == e) break;
	}
	cout << c << endl;
	return 0;
}

Measured memory_bytes: 1196
#include "bits/stdc++.h"

using namespace std;
typedef long long ll;
#define rep(i, j, n) for (int i = j; i < n; i++)
#define out(ans) cout << ans << endl;
const long long mod = 1e9 + 7;

int main(){

  int n;cin>>n;

  out(n*800-200*(n/15));

  return 0;
}


Measured memory_bytes: 256
#include <cassert>
#include <algorithm>
#include <cctype>
#include <complex>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <sstream>
#include <tuple>
#include <typeinfo>
#include <unordered_set>
#include <unordered_map>
#include <vector>
using namespace std;

#define REP2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define REPD(i, n) for(int i = (int)(n) - 1; i >= 0; i--)
#define REP(i, n) REP2(i, 0, n)
#define ALL(c) (c).begin(), (c).end()
#define PB(e) push_back(e)
#define FOREACH(i, c) for(auto i = (c).begin(); i != (c).end(); ++i)
#define MP(a, b) make_pair(a, b)
#define BIT(n, m) (((n) >> (m)) & 1)

typedef long long ll;

template <typename S, typename T> ostream &operator<<(ostream &out, const pair<S, T> &p) {
  out << "(" << p.first << ", " << p.second << ")";
  return out;
}

template <typename T> ostream &operator<<(ostream &out, const vector<T> &v) {
  out << "[";
  REP(i, v.size()){
    if (i > 0) out << ", ";
    out << v[i];
  }
  out << "]";
  return out;
}

int main(int argc, char *argv[])
{
  string s;
  int n;
  cin >> s >> n;
  string res;
  for (int i = 0; i < s.size(); i += n) {
    res += s[i];
  }
  cout << res << 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 REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define pi M_PI

int main(){
  int a, b;
  char op;
  while(1){
    cin >> a >> op >> b;
    if(op == '?') return 0;
    else if(op == '+') cout << a + b << endl;
    else if(op == '-') cout << a - b << endl;
    else if(op == '*') cout << a * b << endl;
    else if(op == '/') cout << a / b << endl;
  }
}



Measured memory_bytes: 3108
///A drunk man will find his way home, but a drunk bird may get lost forever...
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair <int, int> pii;
#define pb push_back
#define f first
#define s second
#define sz(x) (int)x.size()
int a[1000 * 100 + 5];
bool b[1000 * 100 + 5];
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
	cout.tie(0);
	int n, t = 0, t1 = 0, t2 = 0;
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> a[i];
		if(!b[a[i]]){
			b[a[i]] = 1;
			t++;
		}
	}
	sort(a , a + n);
	if(a[0] == a[n - 1]){
		cout << (a[0] == n - 1 || 2 * a[0] <= n ? "Yes" : "No") << endl;
		return 0;
	}
	if(t == 2){
		for(int i = 0; i < n; i++){
			if(a[i] == a[n - 1] - 1)
				t1++;
			else
				t2++;
		}
		cout << (t1 + 1 <= a[n - 1] && t1 + t2 / 2 >= a[n - 1] ? "Yes" : "No") << endl;
	}
	else
		cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 1152
/* ITP1_9_B */
#include <stdio.h>
#include <string.h>

#define MAX_CARD_CNT 201

/* ??????????????????????????¢??° */
void init_char_array(char array[], short length);
/* ?????£?????????????????? */
void do_shuffle(char array[], short pos, short length);

int main(void)
{
	char cards[MAX_CARD_CNT];
	short shuffle_cnt, shuffle_pos, length;
	short ii;
	
	while(1)
	{
		init_char_array(cards, MAX_CARD_CNT);
		
		shuffle_cnt = 0;
		shuffle_pos = 0;
		
		scanf("%s", cards);
		
		length = strlen(cards);
		
		if( '-' == cards[0] )
		{
			break;
		}
		
		scanf("%hd", &shuffle_cnt);
		
		for( ii = 0; ii < shuffle_cnt; ii++ )
		{
			scanf("%hd", &shuffle_pos);
			do_shuffle(cards, shuffle_pos, length);
		}
		printf("%s\n", cards);
	}
	return 0;
}

/* ??????????????????????????¢??° */
void init_char_array(char array[], short length)
{
	short ii;
	for( ii = 0; ii < length; ii++ )
	{
		array[ii] = '\0';
	}
}

/* ?????£?????????????????? */
void do_shuffle(char array[], short pos, short length)
{
	// ????????¨?????????
	char start_to_pos[pos];
	char pos_to_end[length - pos];
	
	init_char_array(start_to_pos, pos);
	init_char_array(pos_to_end, length - pos);
	
	// ???????????????
	short ii;
	short idx_start_to_pos = 0;
	for( ii = 0; ii < pos; ii++ )
	{
		start_to_pos[idx_start_to_pos++] = array[ii];
	}
	
	short idx_pos_to_end = 0;
	for( ii = pos; ii < length; ii++ )
	{
		pos_to_end[idx_pos_to_end++] = array[ii];
	}
	
	// ???????????\???????????????????´?
	short idx_array = 0;
	for( ii = 0; ii < length - pos; ii++ )
	{
		array[idx_array++] = pos_to_end[ii];
	}
	for( ii = 0; ii < pos; ii++ )
	{
		array[idx_array++] = start_to_pos[ii];
	}
}

Measured memory_bytes: 584
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <tuple>

using namespace std;

template< typename T >
struct edge {
    int src, to;
    T cost;

    edge(int to, T cost) : src(-1), to(to), cost(cost) {}

    edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}

    edge &operator=(const int &x) {
        to = x;
        return *this;
    }

    operator int() const { return to; }
};

template< typename T >
using Edges = vector< edge< T > >;

struct UnionFind {
    vector< int > data;

    UnionFind(int sz) {
        data.assign(sz, -1);
    }

    bool unite(int x, int y) {
        x = find(x), y = find(y);
        if(x == y) return (false);
        if(data[x] > data[y]) swap(x, y);
        data[x] += data[y];
        data[y] = x;
        return (true);
    }

    int find(int k) {
        if(data[k] < 0) return (k);
        return (data[k] = find(data[k]));
    }

    int size(int k) {
        return (-data[find(k)]);
    }
};

template< typename T >
T kruskal(Edges< T > &edges, int V) {
    sort(begin(edges), end(edges), [](const edge< T > &a, const edge< T > &b) {
        return (a.cost < b.cost);
    });
    UnionFind tree(V);
    T ret = 0;
    for(auto &e : edges) {
        if(tree.unite(e.src, e.to)) ret += e.cost;
    }
    return (ret);
}

int64_t cost(tuple<int,int,int> a, tuple<int,int,int> b) {
    return min(abs(get<0>(a) - get<0>(b)), abs(get<1>(a) - get<1>(b)));
}

int main(void) {
    int N;
    cin >> N;
    vector< tuple<int,int,int> > points;
    for(int i=0; i<N; i++) {
        int x, y;
        cin >> x >> y;
        points.emplace_back(x, y, i);
    }

    Edges<int64_t> g;
    sort(points.begin(), points.end());
    for(int i=0; i<N-1; i++) {
        g.emplace_back(get<2>(points[i]), get<2>(points[i+1]), cost(points[i], points[i+1]));
    }

    sort(points.begin(), points.end(), [](auto &lhs, auto &rhs) {return get<1>(lhs) < get<1>(rhs);});
    for(int i=0; i<N-1; i++) {
        g.emplace_back(get<2>(points[i]), get<2>(points[i+1]), cost(points[i], points[i+1]));
    }

    cout << kruskal(g, N) << endl;
    return 0;
}


Measured memory_bytes: 8432
/**
 *    This code has been written by YueGuang, feel free to ask me question. Blog: http://www.yx.telstudy.xyz
 *    created:
 */
#include <cstdio>
#include <iostream>
#include <set>
#include <map>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#define REP(i, a, b) for(int i = a; i < b; i++)
#define REP_(i, a, b) for(int i = a; i <= b; i++)
#define sl(n) scanf("%lld", &n);
#define si(n) scanf("%d", &n);
#define RepAll(a) for(auto x: a)
#define cout(ans) cout << ans << endl;
typedef long long ll;

using namespace std;
int aa[256];
int main(){
    int a, b, k, cnt = 0; scanf("%d%d%d",&a, &b, &k);
    for(int i = a; i <= b; i++){
        if(i <= a+k-1){aa[cnt++] = i;}
        else if(i >= b-k+1 && i <= b){aa[cnt++] = i;}
    }
    sort(aa, aa+cnt);
    for(int i = 0; i < cnt; i++){cout << aa[i] << '\n';}
}


Measured memory_bytes: 256
#include <cstdio>
#include <set>

std::multiset<int> as;

int main(){
  int N;
  scanf("%d",&N);
  int D=1;
  for(int i=0;i<N;i++){
    int A;
    scanf("%d",&A);
    D=std::max(D,A);
    as.insert(A);
  }
  int min=1e9;
  for(int i=0;i<=D;i++){
    int take=std::max(i,D-i);
    min=std::min(min,take);
    if(!as.count(take)){
      printf("Impossible\n");
      return 0;
    }
    as.erase(as.find(take));
  }
  for(int a:as){
    if(a<=min){
      printf("Impossible\n");
      return 0;
    }
  }
  printf("Possible\n");
  return 0;
}


Measured memory_bytes: 256
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<math.h>
#include<numeric>
#include<cassert>
#include<random>
#include<deque>
#include<chrono>
#include<unordered_map>
#include<list>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
const ll E=1e18+7;
#define F first
#define S second
#define MK make_pair
const ll MOD=1000000007;

ll edit_dist(string a,string b){
    ll E=1e18+7;
    ll n=a.size();
    ll m=b.size();
    vector<vector<ll>> dp(n+1,vector<ll>(m+1,E));
    for(int i=0;i<n;i++){
        dp[i][0]=i;
    }
    for(int i=0;i<m;i++){
        dp[0][i]=i;
    }
    for(ll i=1;i<=n;i++){
        for(ll t=1;t<=m;t++){
            if(a[i-1]==b[t-1]){dp[i][t]=dp[i-1][t-1];}
            dp[i][t]=min(dp[i][t],dp[i-1][t-1]+1);
            dp[i][t]=min(dp[i][t],dp[i-1][t]+1);
            dp[i][t]=min(dp[i][t],dp[i][t-1]+1);
        }
    }
    return dp[n][m];
}


int main(){
    string a,b;
    cin>>a>>b;
    cout<<edit_dist(a,b)<<endl;
    
    return 0;
}


Measured memory_bytes: 10748
def search(N, s, start, depth):
    if depth == 0 and s == 0:
        return 1
    if depth == 0 and s != 0:
        return 0

    ans = 0
    for i in range(start, 10):
        if N[i] == 1:
            N[i] = 0
            ans += search(N, s-i, i, depth-1)
            N[i] = 1
    return ans

n,s = [int(i) for i in input().split()]
while n != 0 or s != 0:

    N = [1 for i in range(10)]
    print(search(N, s, 0, n))

    n,s = [int(i) for i in input().split()]



Measured memory_bytes: 5596
#include<cstdio>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;
int main()
{
	int n;
	int ans = 1;
	scanf("%d",&n);
	for(int i = 2; i <= n; i++) {
		int t = pow(i,2);
		for(int j = 3; t <= n; j++){
			ans = max(ans,t);
			t = pow(i,j);
		}
	}
	printf("%d",ans);
	return 0;
 } 

Measured memory_bytes: 128
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] w = new int[n];
        int ttl = 0;
        for (int i = 0; i < n; i++) {
            w[i] = scanner.nextInt();
            ttl += w[i];
        }
        int lo = 1;
        int hi = ttl;
        int p = 0;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (canLoad(w, k, mid)) {
                p = mid;
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        System.out.println(p);
    }

    private static boolean canLoad(int[] w, int k, int p) {
        int t = 0;
        int ck = 0;
        for (int cw : w) {
            if (cw > p) {
                return false;
            }
            if (t + cw > p) {
                ck++;
                if (ck == k) {
                    return false;
                }
                t = 0;
            }
            t += cw;
        }
        return true;
    }
}

Measured memory_bytes: 71148
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int a,b;
  cin>>a>>b;
  if(a*500>b || a*500==b)
  {
    cout<<"Yes"<<endl;
    return 0;
  }
  else
  {
    cout<<"No"<<endl;
    return 0;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define ll long long
#define rep(i,n) for(int i = 0; i < int(n); i++)
#define vi vector<int>
using namespace std;
const int INF = 1001001001;
const int MOD = 1e9+7;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
template<class T> inline bool chmax(T &a, const T &b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b){ if(b<a){ a=b; return 1; } return 0; }

int main(){
  cin.tie(0), ios::sync_with_stdio(false);
  string s; cin >> s;
  if(s == "ABC") cout << "ARC";
  if(s == "ARC") cout << "ABC";
  cout << endl;
  return 0;
}


Measured memory_bytes: 3620
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
typedef long long ll;




int main()
{

    int s,w;
    scanf("%d %d",&s,&w);


    if(w>=s)
    {
        printf("unsafe\n");
    }
    else
    {    
    printf("safe\n");
    }

    return 0;
}

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

typedef __int128 ll;
typedef vector<ll> vl;

ll n,q,l,r;
vl a;
vl query,x,s,t;
ll ans_l,ans_r,ans;

bool judge(ll a,ll thresh){
	for(ll i = 0;i < q;i++){
		if(query[i] == 1){
			if(a >= x[i]){
				a = t[i]*(a+s[i]);
			}
		}else if(query[i] == 2){
			if(a <= x[i]){
				a = (a-s[i])/t[i];
			}
		}
	}
	if(a >= thresh) return true;
	else return false;
}

int main(){
	// cerr << ((ll)1 << 63)-1 << endl;
	// cerr << (((ll)1 << 63)-1)*-1 << endl;
	long long N,Q,L,R;
	cin >> N >> Q >> L >> R;
	n = N;
	q = Q;
	l = L;
	r = R;
	a = vl(n);
	for(ll i = 0;i < n;i++){
		long long tmp;
		cin >> tmp;
		a[i] = tmp;
	}
	// for(ll i = 0;i < n;i++) cin >> a[i];
	query = x = s = t = vl(q);
	for(ll i = 0;i < q;i++){
		long long hoge,fuga,zaki,o;
		cin >> hoge >> fuga >> zaki >> o;
		query[i] = hoge;
		x[i] = fuga;
		s[i] = zaki;
		t[i] = o;
	}
	// for(ll i = 0;i < q;i++) cin >> query[i] >> x[i] >> s[i] >> t[i];
	ll top = ((ll)1 << 63)-1;
	ll bottom = top*-1;
	while(top-bottom > 1){
		ll middle = (top+bottom)/2;
		if(judge(middle,l)) top = middle;
		else bottom = middle;
	}
	ans_l = top;
	top = ((ll)1 << 63)-1;
	bottom = top*-1;
	while(top-bottom > 1){
		ll middle = (top+bottom)/2;
		if(judge(middle,r+1)) top = middle;
		else bottom = middle;
	}
	ans_r = top;
	// cerr << (long long)ans_l << " " << (long long)ans_r << endl;
	sort(a.begin(),a.end());
	cout << lower_bound(a.begin(),a.end(),ans_r)-lower_bound(a.begin(),a.end(),ans_l) << endl;
}


Measured memory_bytes: 18116
N = int(input())
SP = []

for i in range(N):
  sp = list(input().split())+[i+1,]
  sp[1] = int(sp[1])
  SP.append(sp)

SP = sorted(SP, key=lambda x:x[1],reverse=True)

SP = sorted(SP, key=lambda x:x[0])


for _ in SP:
  print(_[2])


Measured memory_bytes: 3060