akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"

#define MOD 1000000007
#define rep(i, n) for(ll i=0; i < (n); i++)
#define rrep(i, n) for(ll i=(n)-1; i >=0; i--)
#define ALL(v) v.begin(),v.end()
#define rALL(v) v.rbegin(),v.rend()
#define FOR(i, j, k) for(ll i=j;i<k;i++)
#define debug_print(var) cerr << #var << "=" << var <<endl;
#define DUMP(i, v)for(ll i=0;i<v.size();i++)cerr<<v[i]<<" "
#define fi first
#define se second

using namespace std;
typedef long long int ll;
typedef vector<ll> llvec;
typedef vector<double> dvec;
typedef pair<ll, ll> P;
typedef long double ld;
struct edge{ll x, c;};

ll mod(ll a, ll mod){
  ll res = a%mod;
  if(res<0)res=res + mod;
  return res;
}

ll modpow(ll a, ll n, ll mod){
  ll res=1;
  while(n>0){
    if(n&1) res=res*a%mod;
    a=a*a%mod;
    n>>=1;
  }
  return res;
}

ll modinv(ll a, ll mod){
  ll b=mod, u=1, v=0;
  while(b){
    ll t=a/b;
    a-=t*b; swap(a, b);
    u-=t*v; swap(u, v);
  }
  u%=mod;
  if(u<0)u+=mod;
  return u;
}

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

bool is_prime(ll n){
  ll i = 2;
  if(n==1)return false;
  if(n==2)return true;
  bool res = true;
  while(i*i <n){
    if(n%i==0){
      res = false;
    }
    i = i+1;
  }

  //if(i==1)res = false;
  if(n%i==0)res=false;
  return res;
}
/**************************************
** A main function starts from here  **
***************************************/
int main(){
  ll N, T;
  cin >> N >> T;
  llvec v(N);
  rep(i, N)cin >> v[i];
  ll ans = 0;
  rep(i, N-1){
    ans += min(T, v[i+1] - v[i]);
  }
  cout << ans +T<< endl;

  return 0;
}


Measured memory_bytes: 4840
#include<iostream>
#include<algorithm>
#include<vector>
int N, M;
int ans = 1 << 30;
int C[21][100010];
int num[21];
int NU[100010];

int DP[1 << 21][21];
int ac[1 << 21];
int main() {
	std::cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		std::cin >> NU[i];
		num[NU[i]]++;
	}
	for (int i = 1; i <= M; i++) {
		for (int j = 1; j <= num[i]; j++) {
			if (NU[j] != i)C[i][num[i]]++;
		}
		for (int j = num[i] + 1; j <= N; j++) {
			C[i][j] = C[i][j - 1];
			if (NU[j - num[i]] != i)C[i][j]--;
			if (NU[j] != i)C[i][j]++;
		}
	}
	for (int i = 0; i < 1 << (M + 1); i++) {
		for (int j = 1; j <= M; j++) {
			if ((i >> j) & 1) {
				ac[i] += num[j];
			}
		}
	}
	for (int i = 1; i < 1 << (M + 1); i++) {
		for (int j = 1; j <= M + 1; j++) {
			DP[i][j] = 1 << 30;
		}
	}
	for (int i = 0; i < (1 << (M + 1)) - 1; i++) {
		for (int j = 1; j <= M; j++) {
			if (!(i >> j & 1))continue;
			DP[i][j] = DP[i^(1<<j)][M+1]+C[j][ac[i]];
			DP[i][M + 1] = std::min(DP[i][M + 1], DP[i][j]);
		}
	}
	std::cout << DP[(1<<(M+1))-2][M + 1] << std::endl;
	return 0;
}


Measured memory_bytes: 191120
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+50;
int n, x;
typedef pair<int,pair<int,int> > ii;
ii b[N]; 
int c[N];
int sakiakali = 0, ans;
#define fi first
#define se second
bool cmp(ii a,ii b){
	int p = x*a.se.se - a.fi*(a.se.se-a.se.fi);
	int q = x*b.se.se - b.fi*(b.se.se-b.se.fi);
	return (p>q);
}
signed main(){
	cin >> n >> x;
	for(int i=1;i<=n;i++) cin >> b[i].fi >> b[i].se.fi >> b[i].se.se;
	sort(b+1,b+n+1,cmp);
	for(int i=1;i<=n;i++) c[i] = c[i-1] + x*b[i-1].se.se - b[i-1].fi*(b[i-1].se.se-b[i-1].se.fi);
	ans = n*x;
	for(int i=1;i<=n;i++) sakiakali += b[i].fi*b[i].se.fi;
	for(int i=1;i<=n;i++){
		int a = b[i].fi, L = b[i].se.fi, R = b[i].se.se;
        int l = 0, r = x*n, sum;
        while(l<r){
            int m = (l+r)>>1;
            sum = -sakiakali;
            sum += c[m/x+1];
            if(m/x+1>i&&m%x!=0) sum+=(c[m/x+2]-c[m/x+1])-(c[i+1]-c[i]);
            m%=x;
            if(m>a) sum+= (m-a)*R + a*L;
            else sum += m*L;
            m = (l+r)>>1;
         //   cout << sum << endl;
            if (sum<0) l = m + 1;
            else r = m;
        }
        ans = min(ans,l);
	} 
	cout << ans;
}

Measured memory_bytes: 3584
#include <iostream>
#include <set>
#include <vector>
#include <queue>
#include <stack>
#include <utility>
#include <algorithm>

using namespace std;

typedef long long signed int ll;

constexpr ll NIL = -20000000000;

int n,m,q,s,t,z[100000];
vector<pair<int,int>> w;

void dfs(int n,int c) {
    z[n] = c;
    auto r = lower_bound(w.begin(),w.end(),make_pair(n,0));
    auto l = lower_bound(w.begin(),w.end(),make_pair(n+1,0));
    for(auto itr = r;itr != l;itr++) if(z[itr->second] != c)dfs(itr->second,c);
}

int main() {
    for(int i = 0;i < 100000;i++)z[i] = -1;
    cin >> n >> m;
    for(int i = 0;i < m;i++) {
        cin >> s >> t;
        w.push_back(make_pair(s,t));
        w.push_back(make_pair(t,s));
    }
    sort(w.begin(),w.end());
    cin >> q;
    int cc = 1;
    for(int i = 0;i < q;i++) {
        cin >> s >> t;
        if(z[s] == -1) dfs(s,cc++);
        if(z[s] == z[t]) cout << "yes" << endl;
        else cout << "no" << endl;
    }
}



Measured memory_bytes: 8112
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define All(V) V.begin(), V.end()
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD = 1e9+7, INF = 1e9;

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

int main()
{
	ll n; cin >> n;
    if(n == 1){
        cout << 0 << endl;
        return 0;
    }
    auto prime = prime_factorize(n);
    int ans = 0;
    for(auto x : prime){
        int i = 1;
        while(i <= x.second){
            ans += 1;
            x.second -= i;
            i++;
        }
    }
    cout << ans << endl;

    system("pause");
}


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

using namespace std;

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

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<bool>> g(n, vector<bool>(m, false));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            char x;
            cin >> x;
            if (x == '.') g[i][j] = true;
        }
    }

    const int mod = 1e9 + 7;
    vector<vector<int>> dp(n, vector<int>(m));
    dp[0][0] = (int) g[0][0];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (g[i][j]) {
                dp[i][j] += ((i ? dp[i - 1][j] : 0) + (j ? dp[i][j - 1] : 0)) % mod;
            }
        }
    }

    cout << dp[n - 1][m - 1];
}

int main() {
    cout << fixed << setprecision(20);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    // cin >> t;
    while (t--) solve();

    return 0;
}


Measured memory_bytes: 4352
#define _USE_MATH_DEFINES
#include  <iostream>
#include  <algorithm>
#include  <climits>
#include  <vector>
#include  <string>
#include  <cstring>
#include  <stack>
#include  <queue>
#include  <cmath>
#include  <iomanip>
#include  <set>
#include  <map>
#include  <new>
#include <cstdint>
#include <cctype>
using namespace std;
#define rep(i,n)  for(int i = 0; i < n; i++)
#define lrep(i,n,m)  for(int i = n; i < m; i++)

using ll = long long;
using ld = long double;
using Vii = vector<vector<int> >;
using Gjudge = vector<vector<bool>>;
using Vi = vector<int>;
using Vl = vector<ll>;
using Vd = vector<double>;
using Vld = vector<long double>;
using Vll = vector<vector<ll> >;
using Vldd = vector<vector<ld> >;
using Vs = vector<string>;
using Vb = vector<bool>;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;
using Pli = pair<ll, int>;
using VPi = vector<Pi>;
using VPl = vector<Pl>;
using VPli = vector<Pli>;
using Ti = tuple<int, int, int>;
using Tl = tuple<ll, ll, ll>;

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

const int Mod = static_cast<int>(1e9 + 7);
const int INF = INT_MAX / 10;
const ll LINF = LLONG_MAX / 10;
const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,1,0,-1 };


int find(int x, Vi& p)
{
    if (p[x] == x)  return x;
    else return p[x] = find(p[x], p);
}

void unite(int x, int y, Vi& p, Vi& Rank)
{
    x = find(x, p);
    y = find(y, p);
    if (x == y) return;
    if (Rank[x] < Rank[y]) {
        p[x] = y;
    }
    else {
        p[y] = x;
        if (Rank[x] == Rank[y]) Rank[x]++;
    }
}

bool same(int x, int y, Vi& p)
{
    return find(x, p) == find(y, p);
}

int main()
{
	int n, k, l;
	cin >> n >> k >> l;
    Vi p1(n), p2(n);
    rep(i, n) {
        p1[i] = i;
        p2[i] = i;
    }
    Vi Rank1(n, 0);
    Vi Rank2(n, 0);

    rep(i, k) {
        int p, q;
        cin >> p >> q;
        p--; q--;
        unite(p, q, p1, Rank1);
    }
    rep(i, l) {
        int r, s;
        cin >> r >> s;
        r--; s--;
        unite(r, s, p2, Rank2);
    }
    
    rep(i, n) {
        find(i, p1);
        find(i, p2);
    }
    map<Pi, int> mp;
    rep(i, n) {
        mp[{p1[i], p2[i]}]++;
    }
    rep(i, n) {
        if (i) cout << " " << mp[{p1[i], p2[i]}];
        else cout << mp[{p1[i], p2[i]}];
    }
    cout << endl;
}


Measured memory_bytes: 17676
//#include <bits/stdc++.h>
#include<iostream>
#include<climits>
#include<math.h>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<stdio.h>
#include <string>
#include <complex>
#include <functional>
#include <map>
#include <queue>
#include <cctype>
#include <fstream>   // ifstream, ofstream
#include <sstream>   // istringstream
using namespace std;
using ll = long long;
const int mod = 1000000007;
 
ll gcd(ll a, ll b){return b ? gcd(b,a%b) : a;};//最大公約数
ll lcm(ll a, ll b){return a*b/gcd(a,b);};//最小公倍数
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
//typedef pair<string,string> P;
//double dat[100][100];
//int dp[6][1010];//動的計画法
//int prime[100001];
//char str[1010][1010];
typedef pair<string,ll> A;
//vector<A> pc;
//int ABS(int a){return max(a,-a);}
//ll a[100000];
//ll dom[100001];
 
 
int main(){
   ll a,b;
  cin>>a>>b;
  if(a==1||b==1) {
    cout<<1;
    return 0;
  }
  ll ans=a*b/2;
  if(a*b%2) ans++;
  cout<<ans;
  return 0;
}

Measured memory_bytes: 256
n = int(input())
s = input()

alphabet = ["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"]
#print(alphabet.index(s[0]))

for items in s:
    if alphabet.index(items) + n >= len(alphabet):
        items = alphabet[alphabet.index(items) + n - 26]
        print(items,end = "")
    else:
        items = alphabet[alphabet.index(items) + n]
        print(items,end = "")
print()

Measured memory_bytes: 4468
def main():
    N = int(input())
    h = list(map(int, input().split()))

    now = 1
    cont = False
    ans = 0
    tmp = 0
    while now < N:
        # print(now)
        if h[now-1] >= h[now]:
            if cont:
                tmp += 1
            else:
                tmp = 1
                cont = True
        else:
            cont = False
        ans = max(ans, tmp)
        now += 1
    print(ans)

        

if __name__ == "__main__":
    main()

Measured memory_bytes: 15020
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
#define  For(i,a,b) for(int i=a,i##E=b;i<=i##E;++i)
#define rFor(i,a,b) for(int i=a,i##E=b;i>=i##E;--i)
using namespace std;
typedef long long LL;
const int N=510;
template<typename T>inline bool chkmin(T &a,const T &b){return a>b?a=b,1:0;}
template<typename T>inline bool chkmax(T &a,const T &b){return a<b?a=b,1:0;}
template<typename T>inline void read(T &x)
{
	x=0;int _f(0);char ch=getchar();
	while(!isdigit(ch))_f|=(ch=='-'),ch=getchar();
	while( isdigit(ch))x=x*10+ch-'0',ch=getchar();
	x=_f?-x:x;
}
inline void file()
{
#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
}
int n,m,d,C[N][N];
int main()
{
	//file();
	read(n),read(m),read(d);
	For(i,1,n)
	{
		For(j,1,m)
		{
			int c=(((i+j-1)/d)&1)*2+(((m-j+i)/d)&1);
			C[i][j]=c;
			if(c==0)printf("R");
			else
			if(c==1)printf("Y");
			else
			if(c==2)printf("G");
			else printf("B");
		}
		puts("");
	}
	/*
	For(i,1,n)
		For(j,1,m)
		{
			For(x,0,d)
			{
				int y=d-x;
				if(i+x<=n&&j+y<=m)
					if(C[i][j]==C[i+x][j+y])
						cerr<<"error"<<endl;
				if(i+x<=n&&j-y>=1)
					if(C[i][j]==C[i+x][j-y])
						cerr<<"error"<<endl;
				if(i-x>=1&&j+y<=m)
					if(C[i][j]==C[i-x][j+y])
						cerr<<"error"<<endl;
				if(i-x>=1&&j-y>=1)
					if(C[i][j]==C[i-x][j-y])
						cerr<<"error"<<endl;
			}
		}
		*/
	return 0;
}


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

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

using ll = long long;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int INF = 1<<30;
const ll mod = 1000000007LL;

int main(){
  string S;
  cin>>S;
  ll N = S.size();
  map<char,ll> m;
  for(ll i = 0; i < N; i++) m[S[i]]++;
  ll ans = 0LL;
  for(auto x:S){
    ans+=N-m[x];
  }
  cout<<ans/2+1<<endl;
}

Measured memory_bytes: 640
#include<cstdio>
#include <iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<vector>
#include<functional>
#include<cmath>
#include<map>
#include<stack>
#include<cstdlib>
#include<list>
#include<set>
#include<numeric>

#define MOD 1000000007

using namespace std;
typedef long long ll;
typedef pair<int, int> P;


int main()
{
	int A, B; cin >> A >> B;
	cout << (A + B) % 24 << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    int N,AC,WA,TLE,RE;
    string c;    
    cin >> N;
    AC=0;
    WA=0;
    TLE=0;
    RE=0;

    for(int i=0; i<N; i++){
        cin>>c;
        if(c == "AC")AC++;
        if(c == "WA")WA++;
        if(c == "TLE")TLE++;
        if(c == "RE")RE++;
    }
            cout<<"AC x "<<AC<<endl;
            cout<<"WA x "<<WA<<endl;
            cout<<"TLE x "<<TLE<<endl;
            cout<<"RE x "<<RE<<endl;
    return 0;
}


Measured memory_bytes: 3576
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
using namespace std;
int main(){
    int a,b,c;
    cin>>a>>b>>c;
    cout<<a<<" "<<b<<" "<<3*c-a-b<<" \n" ;
    cout<<4*c-2*a-b<<" "<<c<<" "<< 2*a+b-2*c<<" \n" ;
    cout<< a+b-c<<" "<<2*c-b<<" "<<2*c-a<<" \n";
    return 0 ;
}

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

using namespace std;

#define FOE(i, s, t) for (int i = s; i <= t; i++)
#define FOR(i, s, t) for (int i = s; i < t; i++)

#define LL long long
#define mp make_pair
#define pb push_back

#define M 1000000007

int n, x, y;

#define K 600001

vector<pair<int, int> > co[K];

int val[K], col[K], ext[K], active[K];
pair<int, int> a[K];

vector<int> count;

LL fact[K], revfact[K];

LL bigmod(LL a, LL p) {
	if (!p) return 1;
	
	LL t = bigmod(a, p >> 1);
	t = t * t % M;
	
	if (p & 1) t = t * a % M;
	
	return t;	
}

LL C(LL n, LL k) {
	return fact[n] * revfact[k] % M * revfact[n - k] % M;	
}

vector<int> cols;
vector<int> cnts;

int main(){
	scanf("%d%d%d", &n, &x, &y);
	
	fact[0] = 1;
	FOE(i, 1, n * 3) fact[i] = (fact[i - 1] * i) % M;
	FOE(i, 0, n * 3) revfact[i] = bigmod(fact[i], M - 2);
	
	FOE(i, 1, n) {
		int c, w; scanf("%d%d", &c, &w);
		co[c].pb(mp(w, i));
		
		col[i] = c;
		a[i] = mp(w, i);
	}
	
	FOE(i, 1, n) if (co[i].size()) {
		sort(co[i].begin(), co[i].end());
			
		int low = -1;
		
		while (low + 1 != co[i].size() && co[i][low + 1].first + co[i][0].first <= x) low++;
		
		FOE(j, 0, low) {
			int pos = co[i][j].second;
			
			val[pos] = low + 1;				
		}
	}
	
	sort(a + 1, a + n + 1);
	
	int low = 0;
	
	int secLow = 1;
	
	while (secLow <= n && col[a[secLow].second] == col[a[1].second]) secLow++;
	
	while (low != n && a[low + 1].first + a[1].first <= y) {
		low++;
		
		int ok = (col[a[low].second] != col[a[1].second] || a[secLow].first + a[low].first <= y);
		
		if (ok) {
		
			int pos = a[low].second;
			
			active[pos] = 1;
			
		//	printf("POS %d\n", pos);
			
			if (val[pos] > 0) {
				int len = val[pos] - 1;
				int color = col[pos];	
				
				if (!ext[color]) {
					FOE(i, 0, len) {
						int pp = co[color][i].second;
						
						active[pp] = 1;
					}
					ext[color] = 1;
				}
			}
		}
	}
	
	LL ret = 1;
	
	
	FOE(i, 1, n) {
		if (active[i]) cols.pb(col[i]);
//		if (active[i]) printf("POS %d ACTIVE\n", i);
	}
	
	if (cols.size()) {
		sort(cols.begin(), cols.end());
		
		int last = -1, cnt = 0;
//		FOR(i, 0, cols.size()) printf("cols[%d] = %d\n", i, cols[i]);
		
		FOR(i, 0, cols.size()) {
			if (last == -1) {
				cnt = 1; 
				last = cols[0];	
			} else if (cols[i] != last) {
				cnts.pb(cnt);
				cnt = 1;
				last = cols[i];	
			} else {
				cnt++;	
			}
		}
		
		cnts.pb(cnt);
		
//		FOR(i, 0, cnts.size()) printf("cnts[%d] = %d\n", i, cnts[i]);
		
		int slot = 1;
		
		FOR(i, 0, cnts.size()) {
			ret = ret * C(slot + cnts[i] - 1, cnts[i]) % M;
			
			slot += cnts[i];
		}
	}
	
	cout << ret << endl;
}

Measured memory_bytes: 44020
#include"bits/stdc++.h"
#include<boost/multi_array.hpp>
#include<boost/optional.hpp>
#include<boost/range/irange.hpp>
#include<boost/range/algorithm.hpp>
#include<boost/range/adaptor/reversed.hpp>
#include<boost/operators.hpp>
#include<boost/dynamic_bitset.hpp>
namespace adaptor = boost::adaptors;
template<class T>using p_queue = std::priority_queue<T, std::vector<T>, std::greater<>>;
namespace lib
{
	template<class T>constexpr T pow(T val, std::uint64_t p)
	{
		auto ret = T(1);
		for (auto i : boost::irange(0, 63))
		{
			if (p & (1ULL << i))
			{
				ret *= val;
			}
			val *= val;
		}
		return ret;
	}
	template<std::uint64_t Mod>class modnum :
		private boost::addable<modnum<Mod>>,
		private boost::subtractable<modnum<Mod>>,
		private boost::multipliable<modnum<Mod>>,
		private boost::dividable<modnum<Mod>>
	{
		std::uint64_t val;
		void clamp()
		{
			val %= Mod;
		}
	public:
		modnum() = default;
		modnum(std::int64_t v) :val()
		{
			if (v < 0)
			{
				v += (std::abs(v) / Mod + 1) * Mod;
			}
			val = v;
			clamp();
		}
		modnum(std::uint64_t v) :val(v)
		{
			clamp();
		}
		modnum(std::int32_t v) :modnum(static_cast<std::int64_t>(v))
		{

		}
		modnum(std::uint32_t v) :modnum(static_cast<std::uint64_t>(v))
		{

		}
		friend std::ostream& operator<<(std::ostream& os, modnum const& num)
		{
			return os << num.val;
		}
		auto& operator+=(modnum const& rhs)
		{
			val += rhs.val;
			clamp();
			return *this;
		}
		auto& operator-=(modnum const& rhs)
		{
			val += Mod - rhs.val;
			clamp();
			return *this;
		}
		auto& operator*=(modnum const& rhs)
		{
			val *= rhs.val;
			clamp();
			return *this;
		}
		auto& operator/=(modnum const& rhs)
		{
			val *= pow(rhs, Mod - 2).val;
			clamp();
			return *this;
		}
		auto const& operator*()const
		{
			return val;
		}
	};
}
using mod_t = lib::modnum<1000000007>;


void Main()
{
	int N, M;
	std::cin >> N >> M;
	std::set<int> out;
	for (auto i : boost::irange(0, M))
	{
		int a;
		std::cin >> a;
		out.emplace(a);
	}
	std::vector<mod_t> dp(N + 2);
	dp[0] = 1;
	for (auto i : boost::irange(0, N))
	{
		if (!out.count(i + 1))
		{
			dp[i + 1] += dp[i];
		}
		if (!out.count(i + 2))
		{
			dp[i + 2] += dp[i];
		}
	}
	std::cout << dp[N] << std::endl;
}

int main()
{
	std::cin.tie(nullptr);
	std::ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	Main();
}

Measured memory_bytes: 5760
import java.util.*;
import java.io.*;
import java.lang.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int d = sc.nextInt();

        int fi = a*b;
        int se = c*d;
        if (fi>se)
            System.out.println(fi);
        else
            System.out.println(se);
    }
}


Measured memory_bytes: 35740
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <cmath>

using namespace std;
using ll = long long;
using ull = unsigned long long;

constexpr ll LLINF {1001002003004005006};//ll = 9*LLINF
constexpr int INTINF {1000000000};//int = 2*INTINF

#define  rep(i,n)   for(int i = 0; i < (n); ++i)
#define rrep(i,n)   for(int i = 1; i <= (n); ++i)
#define drep(i,n)   for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for(int i = s; i < t;  ++i)

template<typename T>
void maxs(T& x, T&& y) {
  x=std::max(x,y);
}
template<typename T>
void maxs(T& x, T& y) {
  x=std::max(x,y);
}

template<typename T>
void mins(T& x, T&& y) {
  x=std::min(x,y);
}
template<typename T>
void mins(T& x, T& y) {
  x=std::min(x,y);
}
using P = std::pair<int, int>;

int main() {
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int N, Q;
  cin >> N >> Q;
  string S;
  cin >> S;
  vector<P> Query(Q);
  rep(i, Q) cin >> Query[i].first >> Query[i].second;
  vector<int> cnt_answer(N+1, 0);
  srep(i, 1, N) {
    if (S[i] == 'C' && S[i-1] == 'A') {
      cnt_answer[i] = cnt_answer[i-1]+1;
    } else {
      cnt_answer[i] = cnt_answer[i-1];
    }
  }
  rep(i, Q) {
    cout << cnt_answer[Query[i].second-1] - cnt_answer[Query[i].first-1] << '\n';
  }
}


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

using namespace std;

#define x first
#define y second
#define mp make_pair
#define pb push_back

typedef long long ll;

const ll MOD = 1e9+7;

int n, k;
int r, p, si;
char ch[100005];
string s;

int main() {
	scanf("%d%d", &n, &k);
	scanf("%d%d%d", &r, &si, &p);
	scanf("%s", ch);
	s = ch;
	string sol;
	ll br = 0;
	for (int i=0 ; i<n ; i++) {
		if (s[i] == 'r') {
			if (i<k or sol[i-k] != 'p') {
				sol += 'p';
				br += p;
			}
			else sol += '_';
		}
		if (s[i] == 'p') {
			if (i<k or sol[i-k] != 's') {
				sol += 's';
				br += si;
			}
			else sol += '_';
		}
		if (s[i] == 's') {
			if (i<k or sol[i-k] != 'r') {
				sol += 'r';
				br += r;
			}
			else sol += '_';
		}
	}
	//cout <<sol<<endl;
	printf("%I64d\n", br);
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define range(i, l, r) for(int (i) = (l); (i) < (r); (i)++)
#define reversed_range(i, l, r) for (int (i) = (r) - 1; (i) >= l; (i)--)
using namespace std;
template <typename T>
using vec = vector<T>;
using lint = long long;
using ulint = unsigned long long;
using pint = pair<int, int>;
using plint = pair<lint, lint>;

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

template <typename T>
ostream& operator <<(ostream& os, vec<T> v) {
    os << "[";
    for (int i = 0; i < v.size() - 1; i++) {
        os << v.at(i) << ", ";
    }
    return os << v.at(v.size() - 1) << "]";
}

template <typename T>
ostream& operator <<(ostream& os, set<T>& s) {
    os << "{";
    auto it_first_item = s.begin();
    cout << *it_first_item;
    for (auto it = ++it_first_item; it != s.end(); it++) {
        cout << ", " << *it;
    }
    return cout << "}";
}

template <typename T>
ostream& operator <<(ostream& os, unordered_set<T>& s) {
    os << "{";
    auto it_first_item = s.begin();
    cout << *it_first_item;
    for (auto it = ++it_first_item; it != s.end(); it++) {
        cout << ", " << *it;
    }
    return cout << "}";
}

template <typename K, typename V>
ostream& operator <<(ostream& os, map<K, V> m) {
    os << "{";
    auto it_first_item = m.begin();
    cout << it_first_item->first << ": " << it_first_item->second;
    for (auto it = ++it_first_item; it != m.end(); it++) {
        cout << ", " << it->first << ": " << it->second;
    }
    return os << "}";
}

template <typename K, typename V>
ostream& operator <<(ostream& os, unordered_map<K, V> m) {
    os << "{";
    auto it_first_item = m.begin();
    cout << it_first_item->first << ": " << it_first_item->second;
    for (auto it = ++it_first_item; it != m.end(); it++) {
        cout << ", " << it->first << ": " << it->second;
    }
    return os << "}";
}

int main() {
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);
    lint N;
    cin >> N;
    vec<lint> a_list(N);
    range(i, 0, N) cin >> a_list.at(i);
    vec<lint> pref_sum;
    lint cur_sum = 0;
    for (const lint a : a_list) {
        cur_sum += a;
        pref_sum.emplace_back(cur_sum);
    }
    // cout << pref_sum << "\n";
    // split], (split
    lint min_diff = (1LL << 60);
    range(split, 0, N - 1) {
        lint x = pref_sum.at(split);
        lint y = pref_sum.at(N - 1) - pref_sum.at(split);
        min_diff = min(min_diff, abs(x - y));
    }
    cout << min_diff << "\n";
}

Measured memory_bytes: 3956
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,s,n) for(int i = (s); i < (n); i++)
#define all(v) begin(v), end(v)

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  
  ll n;
  cin >> n;
  
  vector<ll> p(n);  rep(i, 0, n) cin >> p[i];
  vector<ll> q(n);  rep(i, 0, n) cin >> q[i];
  vector<ll> a(n);  rep(i, 0, n) a[i] = i+1;
  
  ll P, Q;
  ll cnt = 0;
  
  do {
    cnt++;
    if(a == p)
      P = cnt;
    if(a == q)
      Q = cnt;
  } while(next_permutation(all(a)));
        
  cout << abs(P-Q) << "\n";

}


Measured memory_bytes: 256
s = gets.chomp

def check(s)
  return "WA" unless s[0] == 'A'
  s.slice!(0)
  return "WA" unless s[1..-2].count('C') == 1
  s = s[0] + s[1..-2].delete("C") + s[-1]

  s.split("").each do |c|
    if c != c.downcase
      return "WA"
    end
  end

  return "AC"
end

puts check(s)

Measured memory_bytes: 1788
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  int a[n],b[n],c[n];
  for(int i=0;i<n;i++)
  {
    cin>>a[i]>>b[i]>>c[i];
  }
  int d[n][3];
  d[0][0]=a[0];d[0][1]=b[0];d[0][2]=c[0];
  for(int i=1;i<n;i++)
  {
    d[i][0]=a[i]+max(d[i-1][1],d[i-1][2]);
    d[i][1]=b[i]+max(d[i-1][0],d[i-1][2]);
    d[i][2]=c[i]+max(d[i-1][0],d[i-1][1]);
  }
  cout<<max(max(d[n-1][0],d[n-1][1]),d[n-1][2]);
}


Measured memory_bytes: 5936
#include <iostream>
#include <unordered_set>
#include <queue>

using namespace std;

int main() {

    int V, E;
    cin >> V >> E;

    unordered_set<int> indeg[V], outdeg[V];
    int count = 0;

    for (int i = 0; i < E; i++) {
        int s, t;
        cin >> s >> t;
        indeg[t].insert(s);
        outdeg[s].insert(t);
    }

    //
    queue<int> que;

    for (int i = 0; i < V; i++) {
        if (outdeg[i].empty()) {
            que.push(i);
        }
    }

    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (int v: indeg[u]) {
            outdeg[v].erase(u);
            if (outdeg[v].empty()) {
                que.push(v);
            }
        }
        count++;
    }

    if (count == V) {
        cout << 0 << endl;
    } else {
        cout << 1 << endl;
    }
}


Measured memory_bytes: 3192
n=int(input())
x=list(map(int,input().split()))
a=0
b=0
for i in x:
    a=a+i
a=a/n
if a%1 < 0.5:
    a=a//1
else:
    a=(a//1)+1
for i in x:
    b=b+(i-a)*(i-a)
b=int(b//1)
print(b)


Measured memory_bytes: 3060
import java.util.*;

public class Main {

    static long DIFF = 1000000;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int h = sc.nextInt();
        int w = sc.nextInt();
        if (h % 3 == 0 || w % 3 == 0) {
            System.out.println(0);
            return;
        }
        checkDevide1(h, w);
        checkDevide1(w, h);
        checkDevide2(h, w);
        checkDevide2(w, h);
        System.out.println(DIFF);
    }

    static void checkDevide1(int height, int width) {
        for(int h = 1; h < height-1; h++) {
            long restHeight = height - h;
            long h1 = restHeight / 2;
            long h2 = restHeight - h1;
            long one = (long)h * width;
            long two = h1 * width;
            long three = h2 * width;
            long max = Math.max(Math.max(one, two), three);
            long min = Math.min(Math.min(one, two), three);
            DIFF = Math.min(DIFF, (max - min));
        }
    }

    static void checkDevide2(int height, int width) {
        for(int h = 1; h < height; h++) {
            long restHeight = height - h;
            long w1 = width / 2;
            long w2 = width - w1;
            long one = (long)h * width;
            long two = restHeight * w1;
            long three = restHeight * w2;
            long max = Math.max(Math.max(one, two), three);
            long min = Math.min(Math.min(one, two), three);
            DIFF = Math.min(DIFF, (max - min));
        }
    }
}

Measured memory_bytes: 22868
#include <iostream>

using namespace std;

int main(){
 // long long yen = 0;
  long long ck = 1;//ビスケット
  long long K;
  long long A;//ビスケット A 枚を 1 円に交換する
  long long B;//1 円をビスケット B 枚に交換する
  cin >> K;
  cin >> A;
  cin >> B;

 if(B - A <= 2){ck += K;goto f;}//たたいたほうが増えるようであれば、ずっとたたく
  for(long long i = 0;i < K;i++){
s:
   

    if((ck >= A) && !(i + 1 >= K))
{
ck += B-A;
i+=2;
if(!(i < K))break;
goto s;
}//ビスケットにできるようならする


/*
    if(ck >= A){ck -= A;yen++;i++;}
if(!(i < K))break;
*/
    ck++;//できることがなかったら叩く

  }
//cout<<yen<<endl;

f:

cout<<ck<<endl;
return 0;
}

Measured memory_bytes: 256
N = int(input())
w = list(map(int, input().split()))

min_diff = 10**9
sum_w = sum(w)
for i in range(1, N):
    former = sum(w[:i])
    diff = abs((sum_w - former) - former)
    if diff < min_diff:
        min_diff = diff
print(min_diff)

Measured memory_bytes: 3060
#define _CRT_SECURE_NO_WARNINGS
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma comment(linker, "/stack:200000000")
#include <bits/stdc++.h>
#define SIZE 1000010
#define rep(i, a, b) for (long long i = a; i <= b; ++i)
#define ll long long
#define mp make_pair
using namespace std;
void io() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); }
ll m, d, cnt;
int main() {
	io(); cin >> m >> d;
	rep(i, 1, m) {
		rep(j, 22, d) {
			ll a = j % 10, b = j / 10;
			if (a < 2 || b < 2) continue;
			if (a * b == i) ++cnt;
		}
	}
	cout << cnt;
}

Measured memory_bytes: 256
N = int(input())
W = [input() for _ in range(N)]
history = set()
prev = W[0][::-1]
for w in W:
    #print(w in history, w[0], prev[-1])
    if w in history or w[0] != prev[-1]:
        print('No')
        break

    history.add(w)
    prev = w
else:
    print('Yes')


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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;

#define REP(k, n) for (ll k = 0; k < (ll)(n); ++k)
#define REPREV(k, n) for (ll k = (ll)(n)-1; k >= 0; --k)
#define FOR(k, a, b) for (ll k = (ll)(a); k < (ll)(b); ++k)
#define FORREV(k, a, b) for (ll k = (ll)(b)-1; k >= (ll)(a); --k)
#define FOREACH(e, v) for (auto& e : v)

#define TGET(t, i) get<i>(t)
#define TSET(t, i, a) get<i>(t) = a
// MinHeap - priority_queue<ll, vll, greater<ll>> pq;

#define EVEN(n) ((n)&1) == 0
#define ODD(n) ((n)&1) == 1

#define SORT(v) sort(v.begin(), v.end())
#define SORTREV(v) sort(v.rbegin(), v.rend())
#define SHUFFLE(v) random_shuffle(v.begin(), v.end())
//srand(unsigned(time(0)));

#define REMOVEAT(v, i) v.erase(v.begin() + i)
#define REVERSE(v) reverse(v.begin(), v.end())

ll MOD(ll x, ll m) {
    ll r = x % m;
    if (r < 0) {
        r += m;
    }
    return r;
}

ostream& operator<<(ostream& str, const pll& p) {
    str << p.first << " " << p.second;
    return str;
}

template <typename T>
void join(T& arr, string sep) {
    bool first = true;
    for (auto t : arr) {
        if (first) {
            first = false;
            cout << t;
        } else {
            cout << sep << t;
        }
    }
    cout << "\n";
}

#define POS "POSSIBLE"
#define IMPOS "IMPOSSIBLE"

// #define INF LLONG_MAX
// #define MINF LLONG_MIN
#define INF 9e18
#define MINF -INF

void solve() {
    ll n;
    cin >> n;
    vll res(4);
    REP(i, n) {
        string s;
        cin >> s;
        if (s == "AC") {
            res[0]++;
        } else if (s == "WA") {
            res[1]++;
        } else if (s == "TLE") {
            res[2]++;
        } else {
            res[3]++;
        }
    }

    cout << "AC x " << res[0] << "\n";
    cout << "WA x " << res[1] << "\n";
    cout << "TLE x " << res[2] << "\n";
    cout << "RE x " << res[3] << "\n";

    // cout << fixed << setprecision(6);
    // cout << res << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int tt = 1;
    // cin >> tt;
    for (int t = 1; t <= tt; t++) {
        // cout << "Case #" << t << ": ";
        solve();
    }
    //cin.rdbuf()->in_avail()
    return 0;
}

Measured memory_bytes: 3644
#include <stdio.h>  /*入出力*/
#include <stdlib.h> /*標準ライブラリ*/
#include <string.h> /*文字列*/
#include <math.h>   /*計算*/
#include <assert.h> /*確認*/
#include <ctype.h>  /*文字操作*/
#include <stdbool.h>/*bool型*/
#include <limits.h>/*限界*/
//---------------------------------------------------
#define rep(i, n) for(int  i = 0; i < (n); i++)
#define ABS(a) (((a)>(0))?a:-(a))
#define LL long long
#define MOD 1000000007//10^9+7(素数)
//---------------------------------------------------
LL max(LL a, LL b){
  if (a > b) {
    return a;
  }else return b;
}

int main(void)
{
  LL a;
  LL b;
  LL c;
  LL k;
  LL ans = 0;
  scanf("%lld %lld %lld %lld", &a, &b, &c, &k);
  while (a > 0 && k > 0) {
    ans += 1;
    a--;
    k--;
  }
  while (k > 0 && b > 0) {
    b--;
    k--;
  }
  while (c > 0 && k > 0) {
    ans--;
    c--;
    k--;
  }
  printf("%lld\n", ans);
  return 0;
}


Measured memory_bytes: 1732
#include<bits/stdc++.h>
using namespace std;
typedef int64_t ll;
typedef long double ld;
const ll MOD=1000000007;
const ll MODA=998244353;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
long long gcd(long long a,long long b){
    ll gcdmax=max(a,b);
    ll gcdmin=min(a,b);
    while(true){
        if(gcdmax%gcdmin==0)break;
        else gcdmax%=gcdmin;
        swap(gcdmin,gcdmax);
    }
    return gcdmin;
}
ll powerup(ll N,ll P,ll M){
    if(P==0)return 1;
    else if(P%2==0){
        ll t=powerup(N,P/2,M);
        return t*t%M;
    }
    else return N*powerup(N,P-1,M)%M;
}
vector<ll> find_divisor(ll N){
  ll k=1;
  while(k*k<=N){
    k++;
  }
  vector<ll> A(1);
  rep(i,k){
    if(i==1)A.at(0)=1;
    else if(i>=2){
      if(N%i==0)A.push_back(i);
    }
  }
  ll t=0;
  t=A.size();
  rep(i,t){
    if(A.at(t-i-1)*A.at(t-i-1)!=N)A.push_back(N/A.at(t-1-i));
  }
  return A;
}
vector<ll> fac;
vector<ll> finv;
vector<ll> inv;
void COMinit(ll N,ll P){
    rep(i,N+1){
        if(i==0){
            fac.push_back(1);
            finv.push_back(1);
            inv.push_back(1);
        }
        else if(i==1){
            fac.push_back(1);
            finv.push_back(1);
            inv.push_back(1);
        }
        else{
            fac.push_back(fac.at(i-1)*i%P);
            inv.push_back(P-inv.at(P%i)*(P/i)%P);
            finv.push_back(finv.at(i-1)*inv.at(i)%P);
        }
    }
}

ll COM(ll n,ll k,ll P){
    if(n<k)return 0;
    if(n<0||k<0)return 0;
    return fac.at(n)*(finv.at(k)*finv.at(n-k)%P)%P;
}
int main()
{
    ll L,R,d;
    cin>>L>>R>>d;
    cout<<R/d-(L-1)/d<<endl;
}

Measured memory_bytes: 3628
h,w=map(int,input().split())
s=[]
for i in range(h):
	x=input()
	s.append(x)
inf=1000
dis=[[inf for _ in range(w)]for _ in range(h)]
dis[0][0]=0
lis=[[0,0]]
for i in range(1,101):
	p=[]
	for j in range(len(lis)):
		if lis[j][1]-1>=0:
			if s[lis[j][0]][lis[j][1]-1]=="." and dis[lis[j][0]][lis[j][1]-1]==1000:
				p.append([lis[j][0],lis[j][1]-1])
				dis[lis[j][0]][lis[j][1]-1]=min(i,dis[lis[j][0]][lis[j][1]-1])
		if lis[j][1]+1<w:
			if s[lis[j][0]][lis[j][1]+1]=="." and dis[lis[j][0]][lis[j][1]+1]==1000:
				p.append([lis[j][0],lis[j][1]+1])
				dis[lis[j][0]][lis[j][1]+1]=min(i,dis[lis[j][0]][lis[j][1]+1])
		if lis[j][0]-1>=0:
			if s[lis[j][0]-1][lis[j][1]]=="." and dis[lis[j][0]-1][lis[j][1]]==1000:
				p.append([lis[j][0]-1,lis[j][1]])
				dis[lis[j][0]-1][lis[j][1]]=min(i,dis[lis[j][0]-1][lis[j][1]])
		if lis[j][0]+1<h:
			if s[lis[j][0]+1][lis[j][1]]=="." and dis[lis[j][0]+1][lis[j][1]]==1000:
				p.append([lis[j][0]+1,lis[j][1]])
				dis[lis[j][0]+1][lis[j][1]]=min(i,dis[lis[j][0]+1][lis[j][1]])
	if dis[-1][-1]!=1000:
		break
	lis=p
cnt=0
for i in range(h):
	cnt+=s[i].count(".")
if dis[-1][-1]==1000:
	print(-1)
	exit()
print(cnt-dis[-1][-1]-1)

Measured memory_bytes: 3192
#include <bits/stdc++.h>
#define ALL(obj) begin(obj), end(obj)
#define debug(x) cerr << #x << ": " << x << '\n'
using namespace std;
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}

using ll = long long;
using ull = unsigned long long;
const int INF = 1e9;
// const int MOD = 1e9 + 7;
// 1次元 vector
template <class T>
ostream &operator<<(ostream &s, vector<T> vec) {
    for (int i = 0; i < (int)vec.size(); ++i) {
        if (i > 0) {
            s << " ";
        }
        s << vec[i];
    }
    return s << endl;
}
template <class T>  // 2次元 vector
ostream &operator<<(ostream &s, vector<vector<T>> vec2) {
    for (int i = 0; i < (int)vec2.size(); ++i) {
        s << vec2[i];
    }
    return s;
}

ll N;
pair<int, int> decode(int id) {
    return make_pair(id / N, id % N);
}
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};  // dx,dy は次の探索場所への距離を表す（４方向分）

void dfs(int i, int j, vector<vector<ll>> &A, vector<vector<bool>> &B) {
    if (B[i][j]) A[i][j]--;
    for (int t = 0; t < 4; t++) {
        int x = i + dx[t];
        int y = j + dy[t];
        if (y < 0 || N <= y || x < 0 || N <= x) continue;
        if (A[x][y] > A[i][j]) {
            dfs(x, y, A, B);
        }
    }
    if (!B[i][j]) A[i][j]--;
};
int main() {
    cin >> N;
    vector<int> P(N * N);
    for (int i = 0; i < N * N; i++) {
        cin >> P.at(i);
        P[i]--;
    }
    /*
    for (int i = 0; i < N * N; i++) {
        auto [id, j] = decode(P[i]);
        cerr << id << " " << j << endl;
    }
    */
    auto A = make_vec<ll>(N, N);
    auto B = make_vec<bool>(N, N);

    for (int i = 1; i < N; i++) {
        int j = N - i;
        if (i < j) {
            A[i][i]++;
            A[i][j]--;
            A[j][i]--;
            A[j][j]++;
        } else {
            break;
        }
    }
    for (int i = 1; i < N; i++) {
        for (int j = 0; j < N; j++) {
            A[i][j] += A[i - 1][j];
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 1; j < N; j++) {
            A[i][j] += A[i][j - 1];
        }
    }

    ll ans = 0;
    for (int id = 0; id < N * N; id++) {
        auto [i, j] = decode(P[id]);
        //cerr << A;
        ans += A[i][j];
        //cerr << i << " " << j << endl;
        //cerr << ans << endl;
        for (int t = 0; t < 4; t++) {
            int x = i + dx[t];
            int y = j + dy[t];
            if (y < 0 || N <= y || x < 0 || N <= x) continue;
            if (A[x][y] > A[i][j]) {
                dfs(x, y, A, B);
            }
        }
        B[i][j] = true;
    }
    cout << ans << endl;
}


Measured memory_bytes: 32768
#include <iostream>
using std::cin;
using std::cout;

inline unsigned insertion_sort(unsigned a[], unsigned n, unsigned gap){
  unsigned count = 0;
  for(unsigned i = gap; i < n; i++){
    unsigned v = a[i];
    int j = i - gap;
    while(j >= 0 && a[j] > v){
      a[j+gap] = a[j];
      j -= gap;
      count++;
    }
    a[j+gap] = v;
  }
  return count;
}

inline void shell_sort(unsigned a[], unsigned n){
  const unsigned gaps[] = {1,8,23,77,281,1073,4193,16577,65921,262913,1050113};
  // pow(4,i)+3*pow(2,i-1)+1 (prefixed with 1)

  unsigned gap_num = 11, count = 0;
  while(gaps[--gap_num] > n);

  for(int i = gap_num; i >= 0; i--) count += insertion_sort(a,n,gaps[i]);

  cout << (gap_num+1) << '\n';

  for(; gap_num; gap_num--) cout << gaps[gap_num] << ' ';
  cout << gaps[0] << '\n';

  cout << count << '\n';
}

int main(){
  std::ios::sync_with_stdio(false);
  cin.tie(0);
  unsigned n,i;
  cin >> n;
  auto a = new unsigned[n];
  for(i = 0; i < n; i++) cin >> a[i];
  shell_sort(a,n);
  for(i = 0; i < n; i++) cout << a[i] << '\n';
  delete[](a);
}

Measured memory_bytes: 4956
import sys
n,m=map(int,input().split())
par=[-1]*n
wei=[0]*n

#重み付きUnion-Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        px = find(par[x])
        wei[x] += wei[par[x]]
        par[x] = px
        return px

#xの根から距離
def weight(x):
    find(x)
    return wei[x]

#w[y]=w[x]+wとなるようにxとyを併合
def unite(x,y,w):
    w += wei[x]-wei[y]
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
            w = -w
        par[x] += par[y]
        par[y] = x
        wei[y] = w
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#x,yが同じ集合に属するときのwei[y]-wei[x]
def diff(x,y):
    return weight(y)-weight(x)


for i in range(m):
    l,r,d=map(int,input().split())
    if same(l-1,r-1):
        if d!=diff(l-1,r-1):
            print('No')
            sys.exit()
    else:
        unite(l-1,r-1,d)

print('Yes')

Measured memory_bytes: 9016
#include<bits/stdc++.h>
using namespace std;
int main()
{
	char N[3],i;
	for(int j=0;j<3;j++)
	{
		scanf("%c", &N[j]);
	}
	if(N[0]==N[2]){
		printf("Yes");;;;
	}
	else{
		printf("No");	
	}
	return 0;
}

Measured memory_bytes: 256
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

n = int(input())
a = list(myinput())

ls = []
for i in range(n):
    ls.append([ i,a[i] ])
ls = mysort(ls,1,True)
# print(ls)

dp = [ [0]*(n+1) for _ in range(n+1) ]
# dp[i][l]: Aが大きい方からi番目まで決め，左へ移動した個数がl個である時の，スコアの最大値

for i in range(n):
    f = ls[i][0]
    A = ls[i][1]
    for l in range(i+1):
        #
        # 【このi番目を右へ寄せる場合（左へ寄せない場合）】
        # 移動先t
        t = n - i + l - 1
        # スコア
        s = A*abs(t-f)
        # dpテーブルの要素としての更新候補
        dp1 = dp[i][l] + s
        # 既に入っている値より大きければ更新
        if dp1 > dp[i+1][l]:
            dp[i+1][l] = dp1
        #
        # 【このi番目を左へ寄せる場合】
        # 移動先t
        t = l
        # スコア
        s = A*abs(t-f)
        # dpテーブルの要素としての更新候補
        dp2 = dp[i][l] + s
        #
        # 既に入っている値より大きければ更新
        if dp2 > dp[i+1][l+1]:
            dp[i+1][l+1] = dp2
# pprint(dp)

print(max(dp[n]))

Measured memory_bytes: 101988
//Solution By SlavicG
#include "bits/stdc++.h"
using namespace std;
 
#define ll                          long long
 
#define forn(i,n)                   for(int i=0;i<n;i++)
#define all(v)                      v.begin(), v.end()
#define rall(v)                     v.rbegin(),v.rend()
	
#define pb                          push_back
#define sz(a)                       (int)a.size()
 
#define   endl                       "\n"
#define fastio                       ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

int  main()
{
	string s,t;
	cin >> s >> t;
	bool check = false;
	int ans = INT_MAX;
	for(int i = 0;i<sz(s);i++)
	{
		int cnt =  0;
		for(int j =0;j < sz(t);j++)
		{
			if(i + j >= sz(s)){
				cnt = INT_MAX;
				break;
			}
			if(s[i+j] != t[j])cnt++;
		}
		ans = min(ans,cnt);
	}
	cout <<ans;
}

Measured memory_bytes: 3628
#include <iostream>

using namespace std;

int main(void) {
  int A, B, C, K;
  cin >> A >> B >> C >> K;
  if (K <= A) {
    cout << K << endl;
    return 0;
  }
  K = K - A;
  if (K <= B) {
    cout << A << endl;
    return 0;
  }
  K = K - B;
  cout << A - K << endl;
  return 0;
}

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

#define fo(i,n) for(i=0;i<n;i++)
#define Fo(i,k,n) for(i=k;i<n;i++)
#define ll long long

#define pb push_back
#define mp make_pair
#define F first
#define S second

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

#define debug(x) cout<<#x<<" :: "<<x<<"\n";
#define debug2(x,y) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\n";
#define debug3(x,y,z) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<"\n";

using namespace std;
/**************************************************************************/
int main()
{
    fastIO;
    ll t,n,i,j,k,a[100001],b[100010],ans=0,x,y,ptr1,ptr2,lft,rght;
    cin>>n;
    x=0;y=n-1;
    lft=1;rght=n-2;
    fo(i,n)cin>>a[i];
    sort(a,a+n);
    ans = 0;
    x = n / 2;
    b[x] = a[0];b[x+1] = a[n-1];
    ptr1 = x-1;
    ptr2 = x+2;
    i=0;
    while(ptr1>0 and ptr2<=n)
    {
        if(i%2!=0)swap(lft,rght);
        b[ptr1] = a[rght];
        b[ptr2] = a[lft];
        if(i%2!=0)swap(lft,rght);
        lft++;rght--;i++;
        ptr1--;ptr2++;
    }
    if(n%2!=0)ans+=max(abs(b[1]-a[lft]),abs(b[n-1]-a[lft])),b[n]=b[n-1];
    Fo(i,1,n)ans+=abs(b[i+1]-b[i]);
    cout<<ans;

}
/*************************************************************************/

Measured memory_bytes: 1792
#include <iostream>
#include <cmath>
#include <algorithm>
typedef long long ll;
using namespace std;

int digit(ll n) {
	int ans = 0;
	while (n != 0) {
		n /= 10;
		ans++;
	}
	return ans;
}

int main() {
	ll n;
	cin >> n;
	int mind = 11;
	ll a, b;
	for (int i = 1; i <= sqrt(n); i++) {
		if (n % i == 0) {
			a = i;
			b = n / i;
			mind = min(mind, max(digit(a), digit(b)));
		}
	}
	cout << mind << endl;
	return 0;
}

Measured memory_bytes: 256
n,m,x,y=map(int,input().split())
xs=map(int,input().split())
ys=map(int,input().split())

xx = max(xs)
yy = min(ys)

ok = False
for z in range(x + 1, y + 1):
    if xx < z <= yy:
        ok = True

print("No War" if ok else "War")        

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;
const long long INF = 1LL << 60;
typedef pair<int, int> P;
int main()
{
    int A, B, C, K;
    cin >> A >> B >> C >> K;

    int cnt = 0;
    while (A >= B) {
        B *= 2;
        cnt++;
    }

    while (B >= C) {
        C *= 2;
        cnt++;
    }

    if (cnt <= K) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
int main(){
    int f = 1;
    set<int> s;
    int n; cin>>n;
    for(int i=0;i<n;i++){
        int x; cin>>x;
        if(s.count(x)) f = 0;
        s.insert(x);
    }
    if(f) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}


Measured memory_bytes: 9600