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

using ll = long long;

const int mod = 1000000007;
// const int INF = 1000000000;
const ll INF = (ll)1e18 + 2;
const double EPS = 1e-9;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, K;
    cin >> N >> K;
    vector<ll> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    sort(A.begin(), A.end());
    ll l = -INF, r = INF;
    while (l + 1 < r) {
        ll x = (l + r) / 2;
        bool ok = [&]() {
            ll total = 0;
            for (int i = 0; i < N; ++i) {
                int l = -1, r = N;
                if (A[i] > 0) {
                    while (l + 1 < r) {
                        int c = (l + r) / 2;
                        if (A[i] * A[c] <= x) l = c;
                        else r = c;
                    }
                    total += l + 1;
                } else {
                    while (l + 1 < r) {
                        int c = (l + r) / 2;
                        if (A[i] * A[c] <= x) r = c;
                        else l = c;
                    }
                    total += N - r;
                }
                if (A[i] * A[i] <= x) total--;
            }
            total /= 2;
            return total < K;
        }();
        if (ok) l = x;
        else r = x;
    }
    cout << r << endl;
}


Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int,int> pii;
int H,W;
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};

struct Solver{
  queue< vector<int> > _que;
  vector< vector<char> > _grid;
  explicit Solver(queue< vector<int> > que, vector< vector<char> > grid)
    : _que(que), _grid(grid){}
  bool check(int i, int j){
    if(_grid[i][j]=='#'){
      return false;
    }else{
      return true;
    }
  }
  int solve(){
    while(!_que.empty()){
      vector<int> vec = _que.front();
      for(int k=0; k<4; k++){
        int y = vec[0]+dir[k][0];
        int x = vec[1]+dir[k][1];
        if(y<0 || x<0 || y>=H || x>=W) continue;
        int count = vec[2];
        if(check(y,x)){
          _grid[y][x] = '#';
          vector<int> vec_new=vector<int>(3);
          vec_new.at(0)=y;
          vec_new.at(1)=x;
          vec_new.at(2)=count+1;
          _que.push(vec_new);
        }
      }
      _que.pop();
    }
    return _que.back()[2];
  }
};

int main(){
  cin >> H >> W;
  queue< vector<int> > pos_black;
  vector< vector<char> > grid(H, vector<char>(W));
  for(int i=0; i<H; i++){
    for(int j=0; j<W; j++){
      cin >> grid[i][j];
      if(grid[i][j]=='#'){
        vector<int> vec_init(3);
        vec_init.at(0)=i;
        vec_init.at(1)=j;
        vec_init.at(2)=0;
        pos_black.push(vec_init);
      }
    }
  }
  
  Solver solver(pos_black,grid);
  cout << solver.solve() << "\n";
}

Measured memory_bytes: 169524
#include <iostream>
#include <stdio.h>
#include <numeric>
#include <algorithm>
using namespace std;
int main(){
    while(true){
        int h,w;
        cin>>h>>w;
        if(h==0&&w==0){
            break;
        }
        for(int i=0;i<h;++i){
            for(int j=0;j<w;++j){
                cout<<"#";
            }
            cout<<endl;
        }
        cout<<endl;
    }
    return 0;
}



Measured memory_bytes: 3100
const val MOD = 1000000007L

fun main(args: Array<String>) {
    val (X, Y) = listOfInt()
    var s = X + Y
    if (s % 3 != 0) {
        println(0)
        return;
    }
    s /= 3
    val x = X - s
    val y = Y - s
    if (x < 0 || y < 0) {
        println(0)
        return;
    }
    val ans = FermatCombination(x + y).combine(x + y, x)
    println(ans)
}
fun next() = readLine()!!
fun listOfString() = next().split(" ")
fun listOfInt() = listOfString().map(String::toInt)

class FermatCombination(size: Int) {
    var factrial = LongArray(size + 1)
    var inverse = LongArray(size + 1)
    init {
        factrial[0] = 1
        inverse[0] = 1
        for (i in 1 .. size) {
            factrial[i] = factrial[i - 1] * i % MOD
            inverse[i] = pow(factrial[i], MOD.toInt() - 2) % MOD
        }
    }
    fun combine(n: Int, k: Int): Long {
        if (n < k || n < 0 || k < 0) return 0
        return factrial[n] * inverse[k] % MOD * inverse[n - k] % MOD
    }
    fun pow(x: Long, n: Int): Long {
        var x = x
        var n = n
        var ans: Long = 1
        while (n > 0) {
            if (n and 1 == 1) {
                ans = ans * x % MOD
            }
            x = x * x % MOD
            n = n shr 1
        }
        return ans
    }
}


Measured memory_bytes: 48484
#include <cstdio>
#include <iostream>
#include <string>
#include <stack>
#include <cmath>

#define loop(i,a,b) for(int i = a; i < b; i++)
#define rep(i,a) loop(i,0,a)
using namespace std;


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

  if(N == 25){
    cout<<"Christmas"<<endl;
    }
  else if(N == 24){
    cout<<"Christmas Eve"<<endl;
    }else if(N == 23){
    cout<<"Christmas Eve Eve"<<endl;
    }else if(N == 22){
    cout<<"Christmas Eve Eve Eve"<<endl;
    }
    
  return 0;
}


Measured memory_bytes: 256
#pragma gcc optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort(ALL(V)) //小さい方からソート
#define REV(V) reverse(ALL(V)) //リバース
#define RSORT(V) SORT(V);REV(V) //大きい方からソート
#define NPN(V) next_permutation(ALL(V)) //順列
#define pb(n) push_back(n)
#define endl '\n'
#define Endl '\n'
#define DUMP(x)  cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define Yay(n) cout << ((n) ? "Yay!": ":(") << endl
#define RAPID cin.tie(0);ios::sync_with_stdio(false)
#define VSUM(V) accumulate(ALL(V), 0)
#define MID(a,b,c) (a) < (b) && (b) < (c)
#define MIDe(a,b,c) (a) <= (b) && (b) <= (c)
#define IN(n) cin >> n
#define IN2(a,b) cin >> a >> b
#define IN3(a,b,c) cin >> a >> b >> c 
#define IN4(a,b,c,d) cin >> a >> b >> c >> d
#define VIN(V) for(int i = 0; i < (V).size(); i++) {cin >> (V).at(i);}
#define OUT(n) cout << n << endl
#define VOUT(V) REP(i, (V).size()) {cout << (V)[i] << endl;}
#define VOUT2(V) REP(i, (V).size()) {cout << (V)[i] << " ";} cout<<endl;

// 型マクロ定義
#define int long long
#define P pair<ll,ll>
#define Vi vector<ll>
#define Vd vector<double>
#define Vs vector<string>
#define Vc vector<char>
#define M map<ll,ll>
#define S set<ll>
#define PQ priority_queue<ll>
#define PQG priority_queue<ll,V,greater<ll>
//

const int MOD = 1000000007;
const int INF = 1061109567;
const double EPS = 1e-10;
const double PI  = acos(-1.0);

int gcd(int a,int b){return b != 0 ? gcd(b, a % b) : a;} //最大公約数
int lcm(int a, int b){return a * b / gcd(a, b);}
string toStrUp(string str){char diff = 'A'-'a';REP(i,str.size()) str[i] += diff;return str;}
string gCh(string str, int key){return str.substr(key,1);}

signed main() {
  RAPID;
  // デフォルト変数定義
  int n=0,m=0,a=0,b=0,c=0,d=0,x=-INF,y=INF,z=0;
  string s="",t="";
  //

  // ここから
  IN4(a,b,c,d);
  Vi xv(a);
  Vi yv(b);
  VIN(xv)
  VIN(yv)
  REP(i,a){
    x = max(xv[i],x);
  }
  REP(i,b){
    y = min(yv[i],y);
  }
  x++;
  bool final_flg = false;
  FOR(i,x,y+1){
    final_flg = c < i && i <= d;
    if (final_flg) break;
  }
  if(final_flg) OUT("No War");
  else OUT("War");
}

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(v) begin(v),end(v)
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
using ll = long long;
using pii = pair<int, int>;
constexpr ll INF = 1ll<<30;
constexpr ll longINF = 1ll<<60;
constexpr ll MOD = 1000000007;
constexpr bool debug = 0;
//---------------------------------//

int main() {
	int N;
	string S;
	cin >> N >> S;
	
	
	string T = S.substr(0, N / 2);
	bool ans = N % 2 == 0;
	ans &= T + T == S;
	puts(ans ? "Yes": "No");
	
	
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/integer/common_factor.hpp>
#include <boost/integer/common_factor_rt.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>

using std::string;
using std::vector;
using std::set;
using std::multiset;
using std::unordered_set;
using std::map;
using std::multimap;
using std::unordered_map;
using std::pair;
using std::cin;
using std::cout;

typedef uintmax_t    ull;
typedef intmax_t     ll;
typedef uint64_t     ul;
typedef uint32_t     ui;
typedef uint8_t      uc;

typedef boost::multiprecision::number<boost::multiprecision::cpp_dec_float<1000>> cpp_dec_float_1000;

constexpr char CRLF  = '\n';
constexpr char SPACE = ' ';
constexpr char VECTOR_COUT_SEPARATOR = SPACE;
constexpr ll INF = 1000'000'007;

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; }
template<class T> std::ostream& operator<< (std::ostream& os, const std::vector<T>& vc) { for(auto it = vc.begin(); it != vc.end(); ++it) { if (std::next(it) == vc.end()) os << *it; else os << *it << VECTOR_COUT_SEPARATOR; } return os; }
template<class T1, class T2> inline std::ostream & operator<< (std::ostream & os, const std::pair<T1, T2> & p) { return os << p.first << ' ' << p.second; }

void solve(void)
{
  string s{}; cin >> s;
  ll res{};
  for (size_t i = 0; i < s.size(); ++i) {
    if (i % 2 == 0) {
      if (s[i] == 'p') {
        --res;
      }
    } else {
      if (s[i] == 'g') {
        ++res;
      }
    }
  }

  cout << res << CRLF;
  return;
}

int main(void)
{
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);

  solve();

  return 0;
}


Measured memory_bytes: 512
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace Contest
{
    class Scanner
    {
        private string[] line = new string[0];
        private int index = 0;
        public string Next()
        {
            if (line.Length <= index)
            {
                line = Console.ReadLine().Split(' ');
                index = 0;
            }
            var res = line[index];
            index++;
            return res;
        }
        public int NextInt()
        {
            return int.Parse(Next());
        }
        public long NextLong()
        {
            return long.Parse(Next());
        }
        public string[] Array()
        {
            line = Console.ReadLine().Split(' ');
            index = line.Length;
            return line;
        }
        public int[] IntArray()
        {
            return Array().Select(int.Parse).ToArray();
        }
        public long[] LongArray()
        {
            return Array().Select(long.Parse).ToArray();
        }
    }

    class Program
    {
        private long A, B;
        private void Scan()
        {
            var sc = new Scanner();
            A = sc.NextLong();
            B = sc.NextLong();
        }

        public void Solve()
        {
            Scan();
            Console.WriteLine((A & B) % 2 == 0 ? "Even" : "Odd");
        }

        static void Main(string[] args)
        {
            new Program().Solve();
        }
    }
}

Measured memory_bytes: 11092
#include <stdio.h>

int main() {
	double max, min;
	double cur;

	max = 0; min = 1000000;
	while(scanf("%lf", &cur) != EOF) {
		if(cur > max)
			max = cur;
		else if(cur < min)
			min = cur;
	}

	printf("%lf\n", max - min);

	return 0;
}

Measured memory_bytes: 648
import sys
N, M = map(int, input().split())
A = set(int(sys.stdin.readline()) for _ in range(M))
MOD = 10 ** 9 + 7

ans = 0
if N == 1:
    ans = 1
elif N == 2:
    if M == 0:
        ans = 2
    else:
        ans = 1
else:
    if 1 in A:
        p2 = 0
    else:
        p2 = 1
    if 2 in A:
        p1 = 0
    else:
        p1 = p2 + 1
    for i in range(3, N + 1):
        if i in A:
            p2 = p1
            p1 = 0
        else:
            c = (p1 + p2) % MOD
            p2 = p1
            p1 = c
    ans = p1
print(ans)

Measured memory_bytes: 17208
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<sstream>
#include<cmath>
#include<numeric>
#include<map>
#include<stack>
#include<queue>
#include<list>
#include<set>
using namespace std;
int mod = 1e9+7;

int main() {

  int a, b, c, d;
  cin >> a >> b >> c >> d;
  if( abs(a-c) <= d || (abs(a-b) <= d && abs(b-c) <= d ) ) cout << "Yes" << endl;
  else cout << "No" << 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++)
typedef long long int ll;
typedef pair<ll, ll> P;
#define INF 1e9 + 7

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

    int n,l;
    cin >> n >> l;
    
    int m = INF, sum = 0, a = 0;
    rep(i,n){
        m = min(abs(l + i), m);
        a = (l + i > 0)? 1 : -1;
        sum += l + i;
    }
    
    cout << sum - m * a << endl;

    return 0;
}

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

int main() {
  long long int X, K, D;
  cin >> X >> K >> D;
  if (D > abs(X) / K) {
    long long int t = K / 2 - X / (2 * D);
    long long int ans = 10000000000000000;
    if (t >= 0 && t <= K) ans = abs(X + (2 * t - K) * D);
    if (t - 1 >= 0) ans = min(ans, abs(X + (2 * t - K - 2) * D));
    if (t + 1 <= K) ans = min(ans, abs(X + (2 * t - K + 2) * D));
    cout << ans << endl;
  }
  else if (X < 0) cout << abs(X + K * D) << endl;
  else cout << abs(X - K * D) << endl;
}

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

int main() {
  
  int N, f, s, t;
  f = 0;
  s = 1;
  t = 10;
  cin >> N;
  
  for (int i = 0; i < 9; i++) {
    f += (N % t) / s;
    s *= 10;
    t *= 10;
  }
  
  if (N % f == 0) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
   
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
	int a,s[10001],d[10001],f,g,h,i,j,x[10001],z,c,v;
	v=0;
	scanf("%d",&a);
	for(i=1;i<=a;i++){
		scanf("%d %d",&s[i],&d[i]);
		f=s[i];
		x[i]=f*100+d[i];
	}
	scanf("%d",&g);
	h=a+g;
	for(i=1;i<=g;i++){
		scanf("%d %d",&s[a+i],&d[a+i]);
		f=s[a+i];
		x[a+i]=f*100+d[a+i];
	}
	for(i=1;i<=h;i++){
		for(j=i+1;j<=h;j++){
			if(x[i]==x[j]){
				x[j]=100000;
				s[j]=100000;
				d[j]=100000;
			}
			if(x[i]>x[j]){
				c=x[i];
				x[i]=x[j];
				x[j]=c;
				c=s[i];
				s[i]=s[j];
				s[j]=c;
				c=d[i];
				d[i]=d[j];
				d[j]=c;
			}
		}
	}
//	for(i=1;i<=h;i++)	printf("%d\n",x[i]);
	for(i=1;i<=h;i++){
		if(x[i]>10000){
			v++;
		}
	}
	for(i=1;i<=h-v;i++){
		printf("%d:%02d",s[i],d[i]);
		if(i<h-v){
			printf(" ");
		}
	}
	printf("\n");
	return 0;
}

Measured memory_bytes: 1064
#include <bits/stdc++.h>
#define N 100005
#define task "t"
#define mu(x) x*x

using namespace std;
using ll=long long;
using pii=pair<int,int>;
using piii=pair<int,pii>;
const int inf=1e9+7;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie();cout.tie();
    #ifndef ONLINE_JUDGE
  //  freopen(task".inp","r",stdin);
  //  freopen(task".out","w",stdout);
    #endif // ONLINE_JUDGE
    int a;
    string s;
    cin>>a;
    cin>>s;
    if (a<3200) cout<<"red";
    else cout<<s;
    return 0;
}


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


int main(){
    int N;
    cin >> N;
    vector<int> t(N+1), x(N+1), y(N+1);
    t[0] = x[0] = y[0] = 0;
    for(int i=1; i<=N; i++) cin >> t[i] >> x[i] >> y[i];
    
    bool F=true;
    for(int i=1; i<=N; i++){
        int d, dt;
        d = abs(x[i]-x[i-1])+abs(y[i]-y[i-1]);
        dt = t[i]-t[i-1];
        if(d>dt) { F=false; break; }
        
        if(d%2==1 && dt%2==0){ F=false; break; }
        else if(d%2==0 && dt%2==1) { F=false; break; }
    }
    cout << (F?"Yes":"No") << endl;
}


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

int main() {
    int n;
    cin >> n;
    int a[n], k;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int m = *max_element(a, a + n), dist = 2 * m;
    for (int i = 0; i < n; i++) {
        if (abs(2 * a[i] - m) < dist && a[i] != m) {
            dist = abs(2 * a[i] - m);
            k = a[i];
        }
    }
    cout << m << ' ' << k;
    return 0;
}


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

ll A[100000];
ll B[100000];

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

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

	ll sum = 0;
	for(int i = N - 1; i >= 0; i--) {
		A[i] += sum;
		if(A[i] % B[i] == 0) continue;
		ll x = A[i] / B[i];
		ll rem = (x + 1) * B[i] - A[i];
		sum += rem;
	}

	cout << sum << endl;
}

Measured memory_bytes: 1920
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define len(v) ll(v.size())
#define fi first
#define se second

template <class T>
void cout_vec(const vector<T> &vec){
  for(auto itr:vec) cout<<itr<<' ';
  cout<<endl;
}

typedef pair<ll,ll> P;
const ll mod=1e9+7;
const ll inf=1e15;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n,m;
  cin>>n>>m;
  priority_queue<ll> a;
  rep(i,n){
    ll now;
    cin>>now;
    a.push(now);
  }
  rep(i,m){
    ll now=a.top();
    a.pop();
    now/=2;
    a.push(now);
  }
  ll ans=0;
  rep(i,n){
    ans+=a.top();
    a.pop();
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 1400
a=int(input())

s=[input() for i in range(a)]

print("AC x {:d}".format(s.count("AC")))
print("WA x {:d}".format(s.count("WA")))
print("TLE x {:d}".format(s.count("TLE")))
print("RE x {:d}".format(s.count("RE")))


Measured memory_bytes: 16160
a,b,c,d=map(int,input().split())
if c%b==0:
    x=c//b
else:
    x=c//b+1
if a%d==0:
    y=a//d
else:
    y=a//d+1


if x>y:
    print("No")
else:
    print("Yes")

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

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

int main(){
  ll n;
  cin >> n;
  vector<ll> v(n+1,0);
  r(i,n+1)cin >> v.at(i);
  sort(v.begin(),v.end());
  r(i,n)v.at(i)=v.at(i+1)-v.at(i);
  r(i,n-1)v.at(i+1)=gcd(v.at(i),v.at(i+1));
  cout << v.at(n-1)<<endl;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <queue>

using namespace std;
static const int INF = 99999999;
typedef pair<int, int> P;
typedef pair<P, int> PP;
int dx[] = {-1, 0, 0, 1};
int dy[] = {0, -1, 1, 0};

void solve()
{
	int H, W, N;
	cin >> H >> W >> N;
	vector< vector<char> > Field(H, vector<char>(W));
	P start(0, 0);
	for(int i = 0; i < H; ++i)
	{
		for(int j = 0; j < W; ++j)
		{
			cin >> Field[i][j];
			if(Field[i][j] == 'S')
			{
				start.first = j;
				start.second = i;
			}
		}
	}
	int sum = 0;
	int Target_Num = 1;
	P goal(start.first, start.second);
	while(Target_Num <= N)
	{
		vector< vector<int> > d(H, vector<int>(W));
		for(int i = 0; i < H; ++i)
		{
			for(int j = 0; j < W; ++j)
			{
				d[i][j] = INF;
			}
		}

		start = goal;
		for(int i = 0; i < H; ++i)
		{
			for(int j = 0; j < W; ++j)
			{
				if(Field[i][j] == '0' + Target_Num)
				{
					goal.first = j;
					goal.second = i;
				}
			}
		}
		queue<PP> Que;
		Que.push(PP(start, 0));
		while(!Que.empty())
		{
			PP pp = Que.front();
			Que.pop();
			if(pp.first.first == goal.first && pp.first.second == goal.second)
			{
				sum += pp.second;
				break;
			}
			else
			{
				for(int i = 0; i < 4; ++i)
				{
					int nx = pp.first.first + dx[i];
					int ny = pp.first.second + dy[i];
					if(0 <= nx && nx < W && 0 <= ny && ny < H && Field[ny][nx] != 'X' && d[ny][nx] > pp.second + 1)
					{
						d[ny][nx] = pp.second + 1;
						Que.push(PP(P(nx, ny), pp.second + 1));
					}
				}
			}
		}
		++Target_Num;
	}
	cout << sum << endl;
}

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

Measured memory_bytes: 5796
import java.util.*; 

class Main{
public static void main(String[] args){
	Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
		int[] p=new int[n];
  		int d=0;
		for(int c=0;c<n;c++){
    		p[c]=sc.nextInt();
          	if(p[c]!=c+1){
            	d++;
            }
              
    	}
  		
  
 	if(d<=2){
    		System.out.println("YES");
    	}else{
     		System.out.println("NO");
   	 }

    	
    }
}


Measured memory_bytes: 23764
n = int(input())
a, b, c = [], [], []
for i in range(n):
    s = [int(i) for i in input().split()]
    a.append(s[0])
    b.append(s[1])
    c.append(s[2])


def happydc(n):
    hdc = {}
    hdc[0] = {"A": a[0], "B": b[0], "C": c[0]}
    
    for i in range(1, n):
        ai, bi, ci = a[i], b[i], c[i]
        lastdc = hdc[i-1]
        al, bl, cl = lastdc["A"], lastdc["B"], lastdc["C"]
        hdc[i] =  {"A": max(bl,cl)+ai, "B": max(al,cl)+bi, "C": max(al,bl)+ci}
    return hdc

print(max(happydc(n)[n-1].values()))

Measured memory_bytes: 63460
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<string>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;

#define MAX 1000000

static bool gosei[MAX];

void b() {
	for (int i = 2; i <= sqrt(MAX); i++)
		if (gosei[i] == false) {
			for (int j = 2, k = 0; (k = i*j) <= MAX; j++)
				gosei[k] = true;
		}
}

int c(int n) {
	int cnt = 0;
	for (int i = 2; i <= n; i++)
		if (!(gosei[i]))cnt++;
	return cnt;
}

int main() {
	b();
	int n;
	while (cin >> n)
		cout << c(n) << endl;
	return 0;
}

Measured memory_bytes: 2136
// Header {{{
#include <bits/stdc++.h>

using namespace std;
template<typename T>
using reversed_priority_queue = std::priority_queue<T, std::vector<T>, std::greater<T> >;
typedef unsigned long long int ull;
typedef long long int ll;
#define rep(i,a,b) for (ll i=(a); i<(b); i++)
typedef pair<ll,ll> PLL;
// }}}

ll N,M;
bool edge[51][51];
vector<PLL> e;

bool connected(){
    vector<bool> con(51,false);

    list<ll> nexts = {0};
    while(nexts.size()>0){
        ll pos = *nexts.begin();
        nexts.pop_front();
        if (con[pos])
            continue;
        con[pos]=true;
        rep(nex,0,N){
            if (edge[pos][nex]){
                nexts.push_back(nex);
            }
        }
    }

    rep(i,0,N)
        if(!con[i])
            return false;
    return true;
}

signed main() {
    cin>>N>>M;
    rep(i,0,M){
        ll a,b;
        cin>>a>>b;
        a--; b--;
        edge[a][b] = edge[b][a] = true;
        e.emplace_back(a,b);
    }

    ll ans=0;
    rep(i,0,M){
        ll a = e[i].first, b = e[i].second;
        edge[a][b] = edge[b][a] = false;
        if(!connected())
            ans++;
        edge[a][b] = edge[b][a] = true;
    }
    cout<<ans<<endl;
    return 0;
}


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

int main()
{
    int n, m, l;
    cin >> n >> m >> l;
    long long a[n][m], b[m][l], c[n][l];
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin >> a[i][j];
        }
    }
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<l;j++)
        {
            cin >> b[i][j];
        }
    }
    
    for(int k=0;k<l;k++)
    {
        for(int i=0;i<n;i++)
        {
            c[i][k] = 0;
            for(int j=0;j<m;j++)
            {
                c[i][k] += a[i][j] * b[j][k];
            }
        }
    }
    
    for(int i=0;i<n;i++)
    {    
        for(int k=0;k<l;k++)
        {
            cout << c[i][k];
            if(k != l-1) cout << " ";
        }
        cout << endl;
    }
    return 0;
}


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

long long n, d, a, tree[200002], ans=0, pre=0;
pair<long long, long long>mon[200002]; // pos, health
queue<pair<long long, long long> >q;

long long sum(long long k){
	long long ret=0;
	while (k>=1){
		ret+=tree[k];
		k-=k&(-k);
	}
	return ret;
}

void update(long long k ,long long x){
	while (k<=n){
		tree[k]+=x;
		k+=k&(-k);
	}
}

int main(){
	memset(tree,0,sizeof tree);
	cin >> n >> d >> a;
	for (int i=0;i<n;i++) cin >> mon[i].first >> mon[i].second;
	sort(mon,mon+n);
	for (int i=0;i<n;i++){
		while (!q.empty() && q.front().first<i){
			pre-=q.front().second;
			q.pop();
		}
		if (pre>mon[i].second) continue;
		long long center=mon[i].first+d, right, l, r;
		l=i, r=n-1;
		while (l<=r){
			long long mid=(l+r)/2;
			if (center+d>=mon[mid].first){
				l=mid+1;
				right=mid;
			}
			else r=mid-1;
		}
		long long bomb=((mon[i].second-pre)/a)+((mon[i].second-pre)%a>0);
//		cout << center << " " << right << " " << bomb << "\n";
		ans+=bomb;
		pre+=bomb*a;
		q.push({right,bomb*a});
	}
	cout << ans << "\n";
}

Measured memory_bytes: 6528
#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(v) (v).begin(),(v).end()
#define fi first
#define se second

template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }

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

const ll INF = 1ll<<29;
const ll MOD = 1000000007;
const double EPS  = 1e-10;

int main() {
	ll n, a, b;
	cin >> n >> a >> b;

	ll ans;
	
	if (n == 1) {
		if (a != b) ans = 0;
		else ans = 1;
	}
	else if (a > b) ans = 0;
	else ans = (b * (n - 1) + a) - (a * (n - 1) + b) + 1;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctype.h>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i, n) REP(i, 0, n)

//4方向ベクトル→↑←↓
int dx[] ={1,0,-1,0};
int dy[] ={0,-1,0,1};

int h_s,m_s,s_s;
int h_f,m_f,s_f;
int main()
{
  for(int i = 0;i <3;i++){
    scanf("%d %d %d",&h_s,&m_s,&s_s);
    scanf("%d %d %d",&h_f,&m_f,&s_f);
    int h =h_f-h_s;
    int m =m_f-m_s;
    int s =s_f-s_s;
    if(s <0){
      s +=60;
      m -=1;
    }
    if(m <0){
      m +=60;
      h -=1;
    }
    if(h <0)
      h +=24;
    cout <<h <<" "<<m<<" "<<s<<endl;
  }
  return 0;
}

Measured memory_bytes: 1208
a,b,n = map(int,input().split())
import math
if n < b-1:
    x = n
    ans = math.floor(a*x/b) - a*math.floor(x/b)
else:
    x = b-1
    ans = math.floor(a*x/b) - a*math.floor(x/b)
print(ans)

Measured memory_bytes: 62024
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int main() {
	typedef long long ll;
	int n; cin >> n;
	ll s = 0;
	ll sum = 0;
	for (int i = 0; i < n; i++){
		ll a; cin >> a;
		if (a == 0) {
			sum += floor(s / 2);
			s = 0;
		}
		else s += a;
	}
	sum += floor(s / 2);
	cout << sum << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include <algorithm>
#include<iostream>
#include<string.h>
#include<vector>
#include<stdlib.h>
#include<math.h>
#include<queue>
#include<deque>
#include<ctype.h>
#include<map>
#include<set>
#include<stack>
#include<string>
#include<algorithm>
#define INF 0x3f3f3f3f
#define FAST_IO ios::sync_with_stdio(false)
const double PI = acos(-1.0);
const double eps = 1e-6;
const int MAX=1e5+10;
const int mod=1e9+7;
typedef long long ll;
using namespace std;
#define gcd(a,b) __gcd(a,b)
inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
inline ll qpow(ll a,ll b){ll r=1,t=a; while(b){if(b&1)r=(r*t)%mod;b>>=1;t=(t*t)%mod;}return r;}
inline ll inv1(ll b){return qpow(b,mod-2);}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll r=exgcd(b,a%b,y,x);y-=(a/b)*x;return r;}
inline ll read(){ll x=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) x=x*10+c-'0';return x*f;}

long long n, x,ans;
ll gcdgcd(ll x,ll n)
{
    if(n%x==0)
        return n*2-x;
    ans=n/x*x*2+gcdgcd(n%x, x);
    return ans;
}

int main()
{
    cin>>n>>x;
    cout<<gcdgcd(x, n-x)+n<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

#define inf (1<<30)-1
#define INF (1LL<<62)-1
#define MOD 1000000007LL
#define MP make_pair
#define PB push_back
#define ALL(x) x.begin(),x.end()
#define PI acos(-1)
#define MEM(x,y) memset(x,y,sizeof (x))
#define debug cout<<"A"<<'\n'
#define REP(i,a,b) for (int i=(a); i<=(b); i++)
#define PER(i,a,b) for (int i=(a); i>=(b); i--)
#define REPL(i,a,b) for (LL i=(a); i<=(b); i++)
#define PERL(i,a,b) for (LL i=(a); i>=(b); i--)
#define print(x) cout<<x<<'\n'
#define itrALL(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
#define UNIQUE(X) X.erase( unique( X.begin(), X.end() ), X.end() )


typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int>PII;
typedef pair<LL,LL>PLL;
typedef vector<int> VI;
typedef vector<LL> VL;


// Order Statistic Tree

/* Special functions:

        find_by_order(k) --> returns iterator to the kth largest element counting from 0
        order_of_key(val) --> returns the number of items in a set that are strictly smaller than our item
*/

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

template <class T> inline T bigmod(T p,T e,T M)
{
    T ret = 1;
    for(; e > 0; e >>= 1)
    {
        if(e & 1) ret = (ret * p) % M;
        p = (p * p) % M;
    } return (T)ret;
}

template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}
template <class T, class X> inline bool getbit(T a, X i) { T t=1; return ((a&(t<<i))>0);}
template <class T, class X> inline T setbit(T a, X i) { T t=1;return (a|(t<<i)); }
template <class T, class X> inline T resetbit(T a, X i) { T t=1;return (a&(~(t<<i)));}

/*end of header*/

int H,W,h,w;
int mat[502][502];
int main()
{
    //freopen("input_file_name.in","r",stdin);
    //freopen("output_file_name.out","w",stdout);
    scanf("%d %d %d %d",&H,&W,&h,&w);
    if(W%w==0 && H%h==0)
    {
        printf("No\n");
        return 0;
    }
    LL hh=H/h,ww=W/w;
    LL tot=hh*ww;
    hh=H%h;
    ww=W%w;
    LL cc=hh*W+ww*H-hh*ww;
    LL bosha=tot/cc+1;
    REP(i,1,H)
    {
        REP(j,1,W)
        {
            if(i%h==0 && j%w==0)mat[i][j]=-(bosha*(h*w-1)+1);
            else mat[i][j]=bosha;
        }
    }
    printf("Yes\n");
    REP(i,1,H)
    {
        printf("%d",mat[i][1]);
        REP(j,2,W)printf(" %d",mat[i][j]);
        printf("\n");
    }
    return 0;
}



Measured memory_bytes: 2304
S = list(input())
Q = int(input())
left, right = [], []
flag = 0
for q in range(Q):
    query = input().split()
    if query[0] == '1':
        flag = (flag + 1) % 2
        left, right = right, left
    else:
        F, C = query[1], query[2]
        if F == '1':
            left.append(C)
        else:
            right.append(C)
if flag == 1:
    S.reverse()
left.reverse()
left = ''.join(left)
right = ''.join(right)
S = ''.join(S)
print(left + S + right)


Measured memory_bytes: 5664
import java.util.Scanner;

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

		for (int i = n; i <= 999; i++) {
			if (i % 111 == 0) {
				ans = i;
				break;
			}
		}

		System.out.println(ans);

		sc.close();
	}

}


Measured memory_bytes: 22100
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <map>
#include <queue>
#include <list>
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,a,b) for(int i=int(a);i<int(b);++i)
#define crep(i) for(char i='a';i<='z';i++)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define psortfirst(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.first<b.first;});
#define ALL(x) (x).begin(),(x).end()
int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}
using namespace std;
using pii  = pair<int,int>;
long long gcd(long long a, long long b){return (b == 0 ? a : gcd(b, a%b));}
long long lcm(long long a, long long b){return a*b/gcd(a,b);}
typedef long long ll;
#define MOD 1000000007
#define EPS 10e-8

int main(){
  ll N,M;
  long double ti,kaku,k;
  cin >> N >> M;
  kaku=1/pow(2,M);
  k=kaku;
  rep(i,100000){
    ti+=(1900*M+100*(N-M))*(i+1)*kaku;
    kaku*=(1-k);
  }
  ti+=0.0000001;
  ll f=(int)ti;
  cout << f << endl;
}

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

using namespace std;
typedef long long ll;
const int mod=1e9+7;
int dp[2050];
int main(){ 
    int s;
    cin>>s;
    dp[0]=1;
    for(int i=3;i<=s;++i)
        for(int j=3;j<=i;++j){ 
            dp[i]=(dp[i]+dp[i-j])%mod;
        }
    cout<<dp[s]<<endl;
    return 0;
}


Measured memory_bytes: 3592
#include<cstdio>
#include<cctype>
#include<bitset>
inline int getint() {
	register char ch;
	while(!isdigit(ch=getchar()));
	register int x=ch^'0';
	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
	return x;
}
const int N=401,M=1e5+1;
bool die[N];
int x[M],y[M];
std::bitset<N> b[N];
int main() {
	const int n=getint(),m=getint();
	for(register int i=1;i<=m;i++) {
		x[i]=getint(),y[i]=getint();
	}
	int ans=0;
	for(register int i=1;i<=n;i++) {
		b[i][i]=true;
		for(register int j=m;j>=1;j--) {
			if(b[i][x[j]]&&b[i][y[j]]) b[i].set();
			if(b[i][x[j]]) b[i][y[j]]=true;
			if(b[i][y[j]]) b[i][x[j]]=true;
		}
		for(register int j=1;j<i;j++) {
			if((b[i]&b[j]).count()==0) ans++;
		}
	}
	printf("%d\n",ans);
	return 0;
}

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

int main() {
    int64_t X;
    std::cin >> X;

    for (int64_t i = -120; i <= 120; ++i) {
        for (int64_t j = -120; j <= 120; ++j) {
            const int64_t v = std::pow(i, 5) - std::pow(j, 5);
            if (X == v) {
                std::printf("%ld %ld\n", i, j);
                return 0;
            }
        }
    }

    return 0;
}



Measured memory_bytes: 4148
#include<iostream>
using namespace std;
int main()
{
	int A,B,C,tmp;
	cin >> A >> B >> C;
	(C/A)==0 ? (tmp=(C/A)+1):(tmp=C/A);
	if(C<A) tmp = 0;
	cout << (tmp*B) <<endl;
	return 0;
}



Measured memory_bytes: 256
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
#pragma GCC optimize("Ofast")

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
#define int long long int
typedef complex<long double> cd;
const long double pi=acos(-1);
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <db, db> pdd;
typedef vector<int> vi;
typedef vector<vector<int> > matrix;

#define m1 make_pair
#define pb push_back
#define flush fflush(stdout)
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define reset(x,v) memset(x,v,sizeof(x))

#define fi first
#define se second
#define endl "\n"
#define debug(x) (cerr << #x << ": " << x << "\n")
#define setbits(x) __builtin_popcount(x)
#define setbitsll(x) __builtin_popcountll(x)
#define all(x) x.begin(),x.end()
#define pii pair<int,int>

inline ll gcd(ll a,ll b){if(a==0) return b;return gcd(b%a,a);}
inline ll power(ll a,ll n,ll m){if(n==0)return 1;ll p=power(a,n/2,m);p=(p%m*p%m)%m;if(n%2) return (p%m*a%m)%m;else return p;}
const ll MOD =998244353;
const ll hell=1000000007;
const int INF = 1e16;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
typedef tree<int, null_type, less<int>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
std::mt19937 rng(seed);

const int N=100005;


void solve()
{
    int n,p;
    cin>>n>>p;
    string s;
    cin>>s;
    if(p==2||p==5)
    {
        int dp[n+1][p];
        memset(dp,0,sizeof(dp));int ans=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<p;j++)
            {
                int z=(j*10+s[i-1]-'0')%p;
                dp[i][z]+=dp[i-1][j];
            }
            dp[i][(s[i-1]-'0')%p]++;
            ans=ans+dp[i][0];
        }
        cout<<ans<<endl;
        return;
        
    }
        
    map<int,int>mp;
    mp[0]++;
    int vl=0;
    int pr=1;int ans=0;
    for(int i=0;i<n;i++)
    {
        vl=(vl*10+s[i]-'0')%p;
        int z=(vl*power(pr,p-2,p))%p;
        ans=ans+mp[z];
        mp[z]++;
        pr=(pr*10)%p;
    }
    cout<<ans<<endl;
    
}

int32_t main()
{
    
    IOS;
    //FILE *fin = freopen("in","r",stdin);
    //FILE *fout = freopen("out","w",stdout);
    
    int t;
    t=1;
     //cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}



Measured memory_bytes: 8340
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<iomanip>
using namespace std;

int main(){
    int a,b,c,d,e,k;
    cin>>a>>b>>c>>d>>e>>k;
    if(e-a<=k)cout<<"Yay!"<<endl;
    else cout<<":("<<endl;
     return 0;
}

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using pi = pair<int, int>;
const ll INF = 1LL << 60;

int main() {
	int n,a,f=0,t=0,b=0;
	bool ans = false;
	cin >> n;
	rep(i, n){
		cin >> a;
		if (a % 4 == 0)f++;
		else if (a % 2 == 0)t++;
		else b++;
	}
	if (b-1 <= f && t == 0)ans = true;
	else if (b <= f)ans = true;
	if (ans) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}



Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define ld long double
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rloop(i,a,b) for(int i=a;i>=b;i--)
const int inf=1e9+7;
 
static bool compare(vector<int> v1,vector<int> v2)
{
    return (v1[1]<v2[1] || (v1[1]==v2[1] && v1[0]<v2[0]));
}
bool isprime(ll x)
{
	for(ll i=2;i*i<=x;i++)
	{
		if(x%i==0)
		return false;
	}
	return true;
}


int numberOfSubarrays(vector<int>& nums, int k) {
        int n=nums.size();
        for(int i=0;i<n;i++)
        {
            if(nums[i]%2==1) nums[i]=1;
            else nums[i]=0;
        }
        loop(i,0,n)
        cout<<nums[i]<<" ";
        cout<<endl;
        vector<int> prsum(n);
            prsum[0]=nums[0];
        map<int,int>  mp;
        mp[prsum[0]]++;
        for(int i=1;i<n;i++)
        {
            prsum[i]=prsum[i-1]+nums[i];
            mp[prsum[i]]++;
        }
        loop(i,0,n)
        cout<<prsum[i]<<" ";
        cout<<endl;
        int ans=0;
        for(int i=prsum[n-1];i>=k;i--)
        {
            if(i!=k)
            {
                ans+=mp[i]*mp[i-k];
            }
            else
            {
                ans+=mp[i]*(mp[0]+1);
            }
            cout<<ans<<endl;
        }
        return ans;
        
    }

int main()
{
	ll n,k;
	cin>>n>>k;
	ll a[n+1];
	loop(i,1,n+1)
	{
		cin>>a[i];
	}
	vector< vector<ll> > dp(n+1, vector<ll> (k+1,1));
	loop(i,1,k+1)
	{
		if(a[1]>=i)
		dp[1][i]=1;
		else 
		dp[1][i]=0;
	}
	loop(i,2,n+1)
	{
		ll pre[k+1];
		pre[0]=dp[i-1][0];
		loop(j,1,k+1)
		{
			pre[j]=(dp[i-1][j]+pre[j-1])%inf;
			
			if(j<=a[i])
			dp[i][j]=pre[j];
			else
			dp[i][j]=(pre[j]-pre[j-a[i]-1]+inf)%inf;
//			cout<<dp[i][j]<<" ";
		}
//		cout<<endl;
	}
	cout<<dp[n][k]%inf;
	return 0;
}


//5 3
//1 1 2 1 1


//10 2
//2 2 2 1 2 2 1 2 2 2


Measured memory_bytes: 83108
import math
import random
from operator import itemgetter
import re
import sys
from itertools import accumulate
from collections import defaultdict
from collections import deque
from bisect import bisect_left,bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
input = sys.stdin.readline
N = int(input())
S =input()
ans = 0
for i in range(1000):
    num1 = i//100
    num2 = (i//10)%10
    num3 = i%10
    chk = num1
    count = 0
    for j in range(N):
        if S[j] ==str(chk):
            count +=1
            if count ==1:
                chk = num2
            elif count ==2:
                chk =num3
            else:
                ans +=1
                break
print(ans)

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

using namespace std;

typedef long long ll;

string to_string(string s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename T>
string to_string(vector<T> v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

const int MAX = (int) 1e5 + 5;

int dp[MAX][3];

int main() {
	ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<vector<int>> a(n);
  for (int i = 0; i < n; i++) {
    int aa, bb, cc;
    cin >> aa >> bb >> cc;
    a[i].push_back(aa);
    a[i].push_back(bb);
    a[i].push_back(cc);
  }
  dp[0][0] = a[0][0];
  dp[0][1] = a[0][1];
  dp[0][2] = a[0][2];
  for (int i = 1; i < n; i++) {
    for (int j = 0; j < 3; j++) {
      dp[i][j] = a[i][j];
      for (int k = 0; k < 3; k++) {
        if (k != j) {
          dp[i][j] = max(dp[i][j], a[i][j] + dp[i - 1][k]);
        }
      }
    }
  }
  cout << max({dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]}) << '\n';
	return 0;
}



Measured memory_bytes: 9784
#include <stdio.h>
#include <math.h>
#define P 3
int main(void)
{
	int n, x[100], y[100], i, j;
	double D, DD;
	scanf("%d", &n);
	for(i=0; i<n; i++){
		scanf("%d", x+i);
	}
	for(i=0; i<n; i++){
		scanf("%d", y+i);
	}
	for(j=1; j<=P; j++){
		D=0;
		for(i=0; i<n; i++){
			D += pow(fabs(*(x+i)-*(y+i)), j);
		}
		printf("%.8f\n", pow(D, 1.0/j));
	}
	D=0;
	for(i=0; i<n; i++){
		DD = fabs(*(x+i)-*(y+i));
		D = (D<DD ? DD : D);
	}
	printf("%.8f\n", D);
	return 0;
}

Measured memory_bytes: 700
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 1000000007

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;

int n, sum;

int main(){
	sum = 0;
	REP(i, 4){
		cin >> n;
		sum += n;
	}
	cout << sum / 60 << endl;
	cout << sum % 60 << endl;
}

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

using namespace std;

int a, b;

int main(void)
{
	scanf("%d %d", &a, &b);
	
	for(int i = 1 ; i <= 10000 ; i++)
	{
		if(i * 8 / 100 == a && i / 10 == b)
		{
			printf("%d", i);
			return 0;
		}
	}
	
	printf("-1");
	return 0;
}

Measured memory_bytes: 256
A,B,C,X,Y=map(int,input().split())

ans=10**9

my_min=min(X,Y)
my_max=max(X,Y)

ans1=2*C*my_min+A*(X-my_min)+B*(Y-my_min)
ans2=2*C*my_max
ans3=A*X+B*Y
print(min(ans1,ans2,ans3))

Measured memory_bytes: 3060
#include<bits/stdc++.h>
    using namespace std;
     
    int main(){
      int a,b,c,k;
      cin>>a>>b>>c>>k;
      if(a>=b&&a>=c) while(k!=0) {a*=2;k--;}
      else if(b>=a&&b>=c) while(k!=0) {b*=2;k--;}
      else if(b<=c&&a<=c) while(k!=0) {c*=2;k--;}
    cout<<a+b+c<<endl;
    }

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define INFLL (1ll<<60)
typedef pair<int, int> P;
typedef pair<int, P> E;
#define MOD (1000000007ll)
#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	b += MOD;
	a += b;
	a %= MOD;
}

ll rwpw(ll a, ll p){
	ll ret = 1ll;
	while(p){
		if(p%2){
			mul_mod(ret,a);
		}
		mul_mod(a,a);
		p /= 2;
	}
	return ret;
}

int main(void){
	ll n,i,a[123456],c[123456],ans=0ll,tmp;
	c[0] = 0ll;
	cin >> n;
	for(i=0ll; i<n; ++i){
		c[i+1] = c[i];
		add_mod(c[i+1],rwpw(i+1,MOD-2));
	}
	for(i=0ll; i<n; ++i){
		cin >> a[i];
		tmp = (c[i+1]+c[n-i]+MOD-1)%MOD;
		mul_mod(tmp,a[i]);
		add_mod(ans,tmp);
	}
	for(i=0ll; i<n; ++i){
		mul_mod(ans,i+1);
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1792
#include<stdio.h>
#include<string.h>
int main(){
  char s[20],d[][5]={"BD","AEC","BF","AEG","BDFH","CEI","DH","EGI","FH"};
  int i;
  while(~scanf("%s",s)){
    for(i=1;s[i];i++){
      if(!strchr(d[s[i-1]-'A'],s[i]))break;
    }
    if(s[i]==0)printf("%s\n",s);
  }
  return 0;
}

Measured memory_bytes: 528
#include <bits/stdc++.h>
using namespace std;
int N,a,b,ans;
int fac[10000005],inv[10000005];
const int fish=998244353;
int Pow(int x,int y){
	int ans=1;
	for (;y;y>>=1,x=1ll*x*x%fish) if (y&1) ans=1ll*ans*x%fish;
	return ans;
}
void Pre(){
	fac[0]=1;
	for (int i=1;i<=10000000;i++)
		fac[i]=1ll*fac[i-1]*i%fish;
	inv[10000000]=Pow(fac[10000000],fish-2);
	for (int i=9999999;i>=0;i--)
		inv[i]=1ll*inv[i+1]*(i+1)%fish;
}
int C(int n,int r){return 1ll*fac[n]*inv[r]%fish*inv[n-r]%fish;}
int catalan(int x,int y){return ((C(x+y,y)-C(x+y,y-1))+fish)%fish;}
int main(){
	Pre();
	scanf("%d%d%d",&N,&a,&b);
	if (b==0){
		cout<<1;
		return 0;
	}
	for (int i=0;i<=min(min(a,N-b),b-1);i++){
		int tot=catalan(b-1,i);
		if (i+b==N){
			if (a==i)
				(ans+=tot)%=fish;
		}
		else {
			int x=N-b-i-1;
			int y=b-i-(b-a)+1;
			(ans+=1ll*tot*C(x+y-1,x)%fish)%=fish;
		}
	}
	cout<<ans;
} 

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


typedef long long ll;
typedef pair<ll, ll> P;

struct edge {int to, cost; };

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

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

ll LCM(ll a, ll b){
  if(a<b) swap(a,b);
  return a/GCD(a,b)*b;
}

int par[200005];
int rank_[200005];
void init(int n){
  for(int i=0; i<n; i++){
    par[i] = i;
    rank_[i] = 1;
  }
}

int find(int x){
  if(x==par[x]){
    return x;
  }else{
    return par[x] = find(par[x]);
  }
}

void unite(int x, int y){
  x = find(x);
  y = find(y);
  if(x==y) return;
  if(rank_[x]<rank_[y]){
    par[x]=y;
    rank_[y] += rank_[x];
    rank_[x] = rank_[y];
  }else{
    par[y]=x;
    rank_[x] += rank_[y];
    rank_[y] = rank_[x];
  }
}

int main(){
  int n;
  cin >> n;
  int tmp = 0;
  for(int i=0; i<n; i++){
    int a, b;
    cin >> a >> b;
    if(a==b) tmp++;
    else tmp = 0;
    if(tmp >=3){
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
  return 0;
}


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

#include<cstring>

int map[102][102] = { 1 };

int main(){
	memset(map, 1, sizeof(map));
	int n, m, d;
	cin >> n >> m >> d;

	for (int i = 0; i < n; ++i) {
		for (int i2 = 0; i2 < m; ++i2) {
			char str;
			cin >> str;
			if (str == '.') { map[i][i2] = 0; }
		}
	}

	int cnt = 0;
	for (int i = 0; i < n; ++i) {
		for (int i2 = 0; i2 < m; ++i2) {
			if (map[i][i2] == 0) {

				bool flg = true;
				for (int j = 1; j < d; ++j) {
					if (map[i + j][i2] != 0) {
						flg = false;
						break;
					}
				}
				if (flg) { ++cnt; }

				flg = true;
				for (int j = 1; j < d; ++j) {
					if (map[i][i2 + j] != 0) {
						flg = false;
						break;
					}
				}
				if (flg) { ++cnt; }
			}
		}
	}
	cout << cnt << endl;

	return 0;
}

Measured memory_bytes: 3132