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

#define x first
#define y second
#define int64 long long
#define debug(x) cerr << #x << " is " << x << endl;
#define MaxN 300000

int64 P, Q, R, S, maxim, minim, res;
int64 pr[MaxN+1];
int64 su[MaxN+1];
int v[MaxN+1];
int N;

void test(int st, int i, int dr)
{
    P = pr[st];
    Q = su[st+1] - su[i+1];
    R = pr[dr] - pr[i];
    S = su[dr+1];

    maxim = max(max(max(P, Q), R), S);
    minim = min(min(min(P, Q), R), S);
    res = min(res, maxim - minim);
}

int main(){


    int i, st, dr, mid, pos1, pos2;
    res = 1LL << 62;

    scanf("%d", &N);
    for(i = 1; i <= N; ++i) scanf("%d", &v[i]);
    for(i = 1; i <= N; ++i) pr[i] = pr[i-1] + v[i];
    for(i = N; i >= 1; --i) su[i] = su[i+1] + v[i];
    for(i = 2; i < N-1; ++i)
    {
        pos1 = 1;
        for(st = 1, dr = i-1; st <= dr; )
        {
            mid = (st + dr) / 2;
            if(pr[mid] > su[mid+1] - su[i+1]) dr = mid - 1;
            else{
                st = mid + 1;
                pos1 = mid;
            }
        }

        pos2 = i+1;
        for(st = i+1, dr = N-1; st <= dr; )
        {
            mid = (st + dr) / 2;
            if(pr[mid] - pr[i] > su[mid+1]) dr = mid - 1;
            else{
                st = mid + 1;
                pos2 = mid;
            }
        }

        test(pos1, i, pos2);
        if(pos1 + 1 < i) test(pos1 + 1, i, pos2);
        if(pos2 + 1 < N) test(pos1, i, pos2 + 1);
        if(pos1 + 1 < i && pos2 + 1 < N) test(pos1 + 1, i, pos2 + 1);
    }

    printf("%I64d\n", res);


return 0;
}


Measured memory_bytes: 4992
#include<stdio.h>
int main(){

	int n,x,i,j,k,count=0;
	
	while(1){
	scanf("%d %d",&n,&x);
	if(n==0 && x==0) break;

	for(i=1; i<=n; i++){
		for(j=i+1; j<=n; j++){
			for(k=j+1; k<=n; k++){
				if(i+j+k==x )
					count++;
			}}}
	printf("%d\n",count);
	count=0;
	}
	return 0;
}

Measured memory_bytes: 600
n, m = map(int, input().split())
s = []
for i in range(m):
    s.append(list(map(int, input().split()[1:])))
p = [int(x) for x in input().split()]

ans = 0

for i in range(2 ** n):
    isLightOn = [False] * m
    for k in range(m):
        count = 0
        for j in range(len(s[k])):
            if (i >> s[k][j] - 1) & 1:
                count += 1
        if count % 2 == p[k]:
            isLightOn[k] = True
    if sum(isLightOn) == m:
        ans += 1

print(ans)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define pi acos(-1)
#define maxn 100001
using namespace std;
typedef long long ll;
const int mx=200005;
//ll a[mx];
//ll tree[mx*4];
//ll n;
//ll solve(ll arr[], ll x, ll n)
//{
//  ll *low = lower_bound(arr, arr+n, x);
//  if (low == (arr + n) || *low != x)
//     return 0;
//  ll *high = upper_bound(low, arr+n, x);
//  return high - low;
//}
//void init(int node, int b, int e)
//{
//    if (b == e)
//    {
//        tree[node] = a[b];
//        return;
//    }
//    int Left = node * 2;
//    int Right = node * 2 + 1;
//    int mid = (b + e) / 2;
//    init(Left, b, mid);
//    init(Right, mid + 1, e);
//    ll x= max(tree[Left],tree[Right]);
//    tree[node]=solve(a,x,n);
//}
//int query(int node, int b, int e, int i, int j)
//{
//    if (i > e || j < b)
//        return 0;
//    if (b >= i && e <= j)
//        return tree[node];
//    int Left = node * 2;
//    int Right = node * 2 + 1;
//    int mid = (b + e) / 2;
//    int p1 = query(Left, b, mid, i, j);
//    int p2 = query(Right, mid + 1, e, i, j);
//    ll x= max(p1,p2);
//    return solve(a,x,n);
//}
//void update(int node, int b, int e, int i, int newvalue)
//{
//    if (i > e || i < b)
//        return;
//    if (b >= i && e <= i) {
//        tree[node] = newvalue;
//        return;
//    }
//    int Left = node * 2;
//    int Right = node * 2 + 1;
//    int mid = (b + e) / 2;
//    update(Left, b, mid, i, newvalue);
//    update(Right, mid + 1, e, i, newvalue);
//    tree[node] = __gcd(tree[Left] , tree[Right]);
//}
//void euiler()
//{
//    for(int i=1;i<maxn;i++)phi[i]=i;
//    for(int p=2;p<maxn;p++){
//        if(phi[p]==p){
//            phi[p]=p-1;
//            for(int i=2*p;i<maxn;i+=p){
//                phi[i]=(phi[i]/p)*(p-1);
//            }
//        }
//    }
//}
//void update(ll idx,ll val)
//{
//    while(idx<=n){
//        tree[idx]=max(tree[idx],val);
//        idx+=(idx&-idx);
//    }
//}
//ll query(ll idx)
//{
//    ll sum=0;
//    while(idx>0){
//        sum=max(sum,tree[idx]);
//        idx-=(idx&-idx);
//    }
//    return sum;
//}

int main()
{
   ll n;
   cin>>n;
   ll x=n/500;
   n%=500;
   ll y=n/5;
   cout<<(1000*x)+(y*5)<<endl;
}


Measured memory_bytes: 256
#ifdef OJ_MISC_OFFLINE

#include "prolog.h"

#else
#define PRINT
#define LCERR
#endif

#include <algorithm>
#include <array>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <map>
#include <string>
#include <vector>

namespace {

using namespace std;

class Solution {
public:
    int sequence_decomposing(const vector<int>& a) {
        vector<int> subseq_last;
        multimap<int, size_t> lookup_table;
        for (int num : a) {
            auto iter = lookup_table.lower_bound(num);
            if (iter == lookup_table.begin()) { // need a new subsequence
                subseq_last.emplace_back(num);
                lookup_table.insert(make_pair(num, subseq_last.size() - 1));
            } else {
                --iter;
                int subseq_idx = iter->second;
                lookup_table.erase(iter);
                subseq_last[subseq_idx] = num;
                lookup_table.insert(make_pair(num, subseq_idx));
            }
        }
        return subseq_last.size();
    }
private:

};

int solve() {
    Solution solution;
    // handle IO here
    int N;
    cin >> N;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
    }
    cout << solution.sequence_decomposing(a) << endl;
    return 0;
}

} // anonymous namespace

#ifdef OJ_MISC_OFFLINE

#include "epilog.h"

#else

int main() {
    return solve();
}

#endif


Measured memory_bytes: 7288
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
using namespace std;

int N;

int main() {
    cin >> N;
    int mx = 0, sum = 0;
    for (int i = 0; i < N; i++) {
        int l;
        cin >> l;
        sum += l;
        if (mx < l) {
            mx = l;
        }
    }
    cout << (sum - mx > mx? "Yes": "No") << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <numeric>
#include <set>

using namespace std;

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define REPO(i, n) for(int i = 1;i <= n;i++)
#define ll long long
#define INF 999999999
#define MINF -999999999
#define ALL(n) n.begin(),n.end()

int main() {
	int n, a, b,c = 0,d = 0,e = 0;
	cin >> n >> a >> b;
	REP(i, n) {
		int m;
		cin >> m;
		if (m <= a) c++;
		else if (m <= b) d++;
		else e++;
	}
	cout << min(c, min(d, e)) << endl;
}



Measured memory_bytes: 256
#pragma GCC optimize("O3")
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("unroll-loops")

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

using namespace std;
using namespace __gnu_pbds; 

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define f first
#define s second
#define sz(x) ll(x.size())
#define endl '\n'
#define forn(i,n) for(int i=0;i<n;++i)
#define fore(i,l,r) for(int i=int(l);i<=int(r);++i)
#define rep(i,begin,end) for(__typeof(end) i=(begin);i!=(end);i++)
#define fill(a,value) memset(a,value,sizeof(a));
#define gcd(a,b) __gcd((a),(b))
#define watch1(x) cout << (x) << endl
#define watch2(x,y) cout << (x) << " " << (y) << endl
#define watch3(x,y,z) cout << (x) << " " << (y) << " " << (z) << endl
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define int long long
 
typedef long long ll;
typedef long double ld; 
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> oset;

// find_by_order(k) returns iterator to kth element starting from 0;
// order_of_key(k) returns count of elements strictly smaller than k;

const int mod = 998244353;
const int inf = 9e18;
const int N = 1e6 + 5;

int freq[2005];
vi g[2005];

void solve(){
    int i,j,n,x,y;
    cin>>n>>x>>y;
    for(i=1;i<n;++i){
        g[i].pb(i+1);
        g[i+1].pb(i);
    }
    g[x].pb(y);
    g[y].pb(x);
    for(i=1;i<=n;++i){
        vi vis(n+1),d(n+1);
        queue<int> q;
        q.push(i);
        vis[i]=1;
        while(!q.empty()){
            int v=q.front();
            q.pop();
            for(int u:g[v]){
                if(!vis[u]){
                    vis[u]=1;
                    q.push(u);
                    d[u]=d[v]+1;
                }
            }
        }
        for(j=1;j<=n;++j){
            freq[d[j]]++;
        }
    }
    for(i=1;i<n;++i){
        cout<<freq[i]/2<<endl;
    }
}

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

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
const int Maxn = 100 + 10;
char S1[Maxn], S2[Maxn];
int N;
int main()
{
#ifdef hk_cnyali
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
#endif
	scanf("%d%s%s", &N, S1, S2);
	for (int i = N; i >= 0; --i)
	{
		int fl = 0;
		for (int j = 0; j < i; ++j)
			if (S2[j] != S1[j + N - i])
			{
				fl = 1;
				break;
			}
		if (!fl)
		{
			cout<<N * 2 - i<<endl;
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

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

int main() {
  int t;
  cin >> t;
  while (t--) {
    int y, m, d;
    cin >> y >> m >> d;
    int res = (999 - y) * 200 + (10 - m) * 20 + (21 - d);
    rep (i, 1000) if (i % 3 > 0) rep (j, 10) if (j % 2 == 1) {
	if (y < i || (y == i && m <= j + 1)) --res;
    }
    cout << res << endl;
  }
  return 0;
}

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

int main(){
    int a,b[100000],c,d[50000],e,f,g=0;
    cin>>a;
    for(int i=0;i<a;i++){
        cin>>b[i];
    }
    cin>>c;
    for(int i=0;i<c;i++){
        cin>>d[i];
    }
    for(int i=0;i<c;i++){
        e=0;
        f=a;
        while(e<f){
            if(d[i]==b[(e+f)/2]){
                g++;
                break;
            }
            if(d[i]<b[(e+f)/2]){
                f=(e+f)/2;
                continue;
            }else if(d[i]>b[(e+f)/2]){
                e=(e+f)/2+1;
                continue;
            }
        }
    }
    cout <<g<<endl;
    return 0;
}

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

#define dump(n) cout<<"# "<<#n<<'='<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;

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

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& a){
	os<<'[';
	rep(i,a.size()) os<<(i?" ":"")<<a[i];
	return os<<']';
}

int calc(vi a,vi b)
{
	if(count(all(a),1)!=count(all(b),1))
		return INF;
	int n=a.size(),cnt=0;
	for(int i=0,j;i<n;i++){
		if(a[i]==b[i]) continue;
		for(j=i;j<n && b[j]!=a[i];j++);
		for(;j>i;j--,cnt++) swap(b[j],b[j-1]);
	}
	return cnt;
}

int main()
{
	for(int n,m;cin>>n>>m && n|m;){
		vi a(n),b;
		rep(i,n) cin>>a[i];
		rep(i,m){
			int t; cin>>t;
			int x=b.empty()?0:!b.back();
			rep(j,t) b.push_back(x);
		}
		
		int res=calc(a,b);
		rep(i,n) b[i]^=1;
		res=min(res,calc(a,b));
		cout<<res<<endl;
	}
}

Measured memory_bytes: 1216
#include <bits/stdc++.h>
typedef long long ll;
#define  rep(i,a,b)for(long long i=a;i<b;++i)
#define  rrep(i,a,b)for(int i=a;i>=b;--i)
#define  yesno(flag)if(flag)cout<<"Yes"<<endl; else cout<<"No"<<endl;
using namespace std;
const ll INF=1000000000000LL;
const ll r197=1000000007;
typedef pair<int,int>P;
typedef pair<int,P>Pa;
bool Inframe(int a,int b,int c,int d,int h,int w){
	if(a+b>=0&&a+b<h&&c+d>=0&&c+d<w)return true;
	return false;
}
ll mad=998244353;
double a,b,x;
int main() {
	cin>>a>>b>>x;
	double m=x/a;
	double ans;
	if(2*x<=a*a*b){
		ans=atan(a*b*b/(2*x));
		ans=ans*180.0/M_PI;
	}else{
		ans=atan(2*(b-x/(a*a))/a);
		ans=ans*180.0/M_PI;
	}
	cout<<fixed;
	cout<<setprecision(6)<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String S = sc.next();
        int a = 0;
        int b = 0;
        char[] C = S.toCharArray();

        for (int i=1; i < C.length; i += 2) {
            if (C[i] == 'R') {
                System.out.println("No");
                System.exit(0);
            }
        }
        for (int i=0; i < C.length; i += 2) {
            if (C[i] == 'L') {
                System.out.println("No");
                System.exit(0);
            }
        }
        System.out.println("Yes");
    }
}

Measured memory_bytes: 23892
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <iomanip>
#include <sstream>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;
typedef long long ll;

int main() {
	int h; cin >> h;
	int w; cin >> w;
	vector<string> a(h);
	for (int i = 0; i < h; i++) {
		cin >> a[i];
	}

	vector<bool> row(h, false);
	vector<bool> col(w, false);
	for (int i = 0; i < h; ++i) {
		for (int j = 0; j < w; ++j) {
			if (a[i][j] == '#') {
				row[i] = true;
				col[j] = true;
			}
		}
	}
	
	for (int i = 0; i < h; ++i) {
		if (row[i]) {
			for (int j = 0; j < w; ++j) {
				if (col[j]) {
					cout << a[i][j];
				}
			}
			cout << endl;
		}
	}
}


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

#define int long long int
#define mp make_pair
#define mod 1000000007
using namespace std;

int n,m;
vector <string> v(1002);
int dp[1002][1002] ;

int fun(int i , int j)
{
    if(i == n-1 && j == m-1){
        return 1;
    }
    if(dp[i][j] != -1) {
        return dp[i][j];
    }
    dp[i][j] = 0;
    if(j + 1 < m && v[i][j+1] == '.'){
        dp[i][j] = (dp[i][j]%mod + fun(i , j+1)%mod)%mod;
    }
    if(i + 1 < n && v[i+1][j] == '.'){
        dp[i][j] = (dp[i][j]%mod + fun(i + 1 , j)%mod)%mod;
    }
    return dp[i][j];
}

int32_t main() {
    scanf("%lld", &n);
    scanf("%lld", &m);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
    /*for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cout << v[i][j];
        }
        printf("\n");
    }*/
    for (int i = 0; i < 1002; ++i) {
        for (int j = 0; j < 1002; ++j) {
            dp[i][j] = -1;
        }
    }
    int ans = fun(0 ,0);
    printf("%lld",ans);
    return 0;
}

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

using namespace std;
using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;
using pll = pair<ll,ll>;

#define INF (1LL << 60)
#define MOD 1000000007
#define PI 3.14159265358979323846

#define REP(i,m,n) for(ll (i)=(m),(i_len)=(n);(i)<(i_len);++(i))
#define FORR(i,v) for(auto (i):v)
#define ALL(x) (x).begin(), (x).end()
#define PR(x) cout << (x) << endl
#define PS(x) cout << (x) << " "
#define SZ(x) ((ll)(x).size())
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define REV(x) reverse(ALL((x)))
#define ASC(x) sort(ALL((x)))
#define DESC(x) ASC((x)); REV((x))
#define pb push_back
#define eb emplace_back

int main()
{
    ll N, A, B;
    cin >> N >> A >> B;

    ll cnt = 0;
    REP(i,1,N+1) {
        ll s = i%10 + (i/10)%10 + (i/100)%10 + (i/1000)%10 + i/10000;
        if(A <= s && s <= B) cnt += i;
    }
    PR(cnt);

    return 0;
}

/*



*/

Measured memory_bytes: 3632
#include <stdio.h>

int main(void){
	int a,b[10000],i,c;
	c=0;
	scanf("%d",&a);
	for(i=0;i<a;i++){
		scanf("%d",&b[i]);
		for(b[i];b[i]>0;b[i]=b[i]/2){
			if(b[i]%2==0){
				c=c+1;
			} else {
				b[i]=0;
			}
		}
	}

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


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
#include<cstdlib>
#include<cctype>
#include<cmath>
#define ll  long long
#define inf 99999999
using namespace std;

map<int ,int>num_count;
int main()
{
    int n;
    cin>>n;
    int temp;
    for(int i=1;i<=n;i++){
        scanf("%d",&temp);
        ++num_count[temp];
    }
    int res=0;
    map<int ,int>::iterator it;
    it=num_count.begin();
    while(it!=num_count.end()){
        int a = it->first;
        int b=it->second;
        if(b>a){
            res+=(b-a);
        }else if(a>b){
            res+=b;
        }
        it++;
    }
    cout<<res<<endl;
    return 0;
}

Measured memory_bytes: 4736
#include <algorithm>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define DEBUG 1
constexpr int kMod = 1000000007;
typedef long long LL;

int main() {
  std::string s; std::cin >> s;

  LL total_cnt = 0, cnt = 0;
  for (int l = s.size() - 1; l >= 0; --l) {
    if (s[l] == 'A') {
      total_cnt += cnt;
    } else if (s[l] == 'C') {
      if (l>0 && s[l-1] == 'B') {
        ++cnt;
        --l;
      } else {
        cnt = 0;
      }
    } else { // S[l] == 'B' {
      cnt = 0;
    }
  }

  std::cout << total_cnt << std::endl;
}


Measured memory_bytes: 640
# -*- coding: utf-8 -*-
"""
Created on Mon Sep 14 01:36:50 2020

@author: liang
"""

S = input()
c0 = 0
c1 = 0
for i in range(len(S)):
    if S[i] == "0":
        c0 += 1
    else:
        c1 += 1
ans = len(S) - abs(c0-c1)
print(ans)

Measured memory_bytes: 8996
#include <bits/stdc++.h>
#define LLI long long int
#define FOR(v, a, b) for(LLI v = (a); v < (b); ++v)
#define FORE(v, a, b) for(LLI v = (a); v <= (b); ++v)
#define REP(v, n) FOR(v, 0, n)
#define REPE(v, n) FORE(v, 0, n)
#define REV(v, a, b) for(LLI v = (a); v >= (b); --v)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define ITR(it, c) for(auto it = (c).begin(); it != (c).end(); ++it)
#define RITR(it, c) for(auto it = (c).rbegin(); it != (c).rend(); ++it)
#define EXIST(c,x) ((c).find(x) != (c).end())
#define fst first
#define snd second
#define popcount __builtin_popcount
#define UNIQ(v) (v).erase(unique(ALL(v)), (v).end())
#define bit(i) (1LL<<(i))

#ifdef DEBUG
#include <misc/C++/Debug.cpp>
#else
#define dump(...) ((void)0)
#endif

#define gcd __gcd

using namespace std;
template <class T> constexpr T lcm(T m, T n){return m/gcd(m,n)*n;}

template <typename I> void join(ostream &ost, I s, I t, string d=" "){for(auto i=s; i!=t; ++i){if(i!=s)ost<<d; ost<<*i;}ost<<endl;}
template <typename T> istream& operator>>(istream &is, vector<T> &v){for(auto &a : v) is >> a; return is;}

template <typename T, typename U> bool chmin(T &a, const U &b){return (a>b ? a=b, true : false);}
template <typename T, typename U> bool chmax(T &a, const U &b){return (a<b ? a=b, true : false);}
template <typename T, size_t N, typename U> void fill_array(T (&a)[N], const U &v){fill((U*)a, (U*)(a+N), v);}

struct Init{
  Init(){
    cin.tie(0);
    ios::sync_with_stdio(false);
  }
}init;

/**
 * @note Comparator = greater<T> : 傾き => 単調減少, クエリ座標 => 単調増加, クエリ => Min
 * @note Comparator = less<T> : 傾き => 単調増加, クエリ座標 => 単調増加, クエリ => Max
 */
template <typename T, typename Comparator = greater<T>> class ConvexHullTrick{
  deque<pair<T,T>> lines;
  bool is_needless(const pair<T,T> &a, const pair<T,T> &b, const pair<T,T> &c){
    return (a.snd-b.snd)*(a.fst-c.fst) >= (a.snd-c.snd)*(a.fst-b.fst);
  }
  
  T apply(const pair<T,T> &f, const T &x){
    return f.fst*x + f.snd;
  }

  Comparator comp = Comparator();

public:
  ConvexHullTrick(){}
  
  void add(const T &a, const T &b){
    if(!lines.empty()){
      pair<T,T> l = lines.back();
      
      if(l.fst == a){
        if(!comp(l.snd,b)) return;
        lines.pop_back();
      }
    }
    while(lines.size()>=2 && is_needless(make_pair(a,b), lines.back(), *(lines.end()-2))){
      lines.pop_back();
    }
    lines.push_back(make_pair(a,b));
  }

  T query(const T &x){
    while(lines.size()>=2 && comp(apply(lines[0],x), apply(lines[1],x))){
      lines.pop_front();
    }
    return apply(lines[0],x);
  }
};












LLI dp[201000];

int main(){
  LLI N,C;
  while(cin >> N >> C){

    vector<LLI> h(N); cin >> h;

    /*
      dp[i]
      = min(dp[j] + (hi-hj)^2 + C)
      = min(dp[j] + hi^2 - 2*hi*hj + hj^2 + C)
      = min(-2*hj*hi + hj^2 + dp[j]) + hi^2 + C
    */

    ConvexHullTrick<LLI,greater<LLI>> cht;

    dp[0] = 0;
    cht.add(-2*h[0],h[0]*h[0]+dp[0]);

    FOR(i,1,N){
      dp[i] = cht.query(h[i]) + h[i]*h[i] + C;
      cht.add(-2*h[i],h[i]*h[i]+dp[i]);
    }

    cout << dp[N-1] << endl;

  }
  
  return 0;
}


Measured memory_bytes: 5632
//abc068_a.cpp
//Sun Sep 30 15:56:25 2018

#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#define INTINF 2147483647
#define LLINF 9223372036854775807
using namespace std;
using ll=long long;
typedef pair<int,int> P;

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

	cout << "ABC"<< n << endl;
}

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

// definitions
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define rep(i, l, r) for (long long i = (l); i < (long long)(r); i++)
#define repb(i, r, l) for (long long i = (r); i > (long long)(l); i--)
#define pb push_back
#define mod1 998244353
#define mod 1000000007
#define MAX_CHAR 256

using namespace std;
typedef vector<long long> vl;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector< pair<long long, long long> > vp;
typedef vector<tuple<long long , long long , long long> > vtup;
typedef deque <long long> dq;
typedef long long int lli;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;


// standard functions
ll gcd(ll x, ll y) {
    if (x < y) return gcd(y, x);
    if (y == 0) return x;
    return gcd(y, x % y);
} 
 


ll modexp(ll x, ll ex, ll modp) {
    ll ans = 1ll;
    while (ex > 0) {
        if (ex & 1ll) ans = (ans * x)%modp;
        ex >>= 1ll;
        x = (x * x)%modp;
    }
    return ans;
} 
 
ll nCrModp(ll n, ll r, ll p) 
{ 
    ll C[r+1]; 
    memset(C, 0, sizeof(C)); 
  
    C[0] = 1; 
    for (ll i = 1; i <= n; i++) 
    { 
        for (ll j = min(i, r); j > 0; j--) 
            C[j] = (C[j] + C[j-1])%p; 
    } 
    return C[r]; 
}
 
bool isPrime(ll n) 
{ 
    if (n <= 1)  return false; 
    if (n <= 3)  return true;  
    if (n%2 == 0 || n%3 == 0) return false; 
  
    for (ll i=5; i*i<=n; i=i+6) 
        if (n%i == 0 || n%(i+2) == 0) 
           return false; 
  
    return true; 
} 
 
vl countFreq(ll arr[], ll n) 
{ 
    unordered_map<ll, ll> mp; 
    vector <ll> v;
    
    for (ll i = 0; i < n; i++) 
        mp[arr[i]]++; 
   
    for (auto x : mp) 
        v.pb(x.second);
    
    return v;
}

ll binarySearch(ll arr[], ll l, ll r, ll x) 
{ 
    while (l <= r) 
    { 
        ll m = l + (r - l) / 2; 
        if (arr[m] == x) 
            return m; 
        if (arr[m] < x) 
            l = m + 1; 
        else
            r = m - 1; 
    }
    return -1; 
}

const ll MAXSIEVE=(1e3);
ll spf[MAXSIEVE];
void sieve() 
{ 
    spf[1] = 1; 
    for (ll i=2; i<MAXSIEVE; i++) 
        spf[i] = i; 

    for (ll i=4; i<MAXSIEVE; i+=2) 
        spf[i] = 2; 
  
    for (ll i=3; i*i<MAXSIEVE; i++) 
    { 
        if (spf[i] == i) 
        { 
            for (ll j=i*i; j<MAXSIEVE; j+=i) 
                if (spf[j]==j) 
                    spf[j] = i; 
        } 
    } 
}

// code beigns in main
int main()
{
    
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll t=1;
    // cin >> t;
    
    while(t--)
    {
        ll n;
        cin >> n;

        vp v;
        rep(i,0,n)
        {
            ll val;
            cin >> val;
            v.pb({val,i+1});
        }

        sort(v.begin(),v.end(),greater<>());

        ll dp[n+2][n+2];
        clr(dp);

        rep(i,1,n+1)
        {
            repb(j,i,0)
            {
                ll cnt=j-i+n-1;
                dp[j][i]=max(dp[j+1][i]+v[cnt].F*abs(v[cnt].S-j),dp[j][i-1]+v[cnt].F*abs(v[cnt].S-i));
            }
        }
        
        cout << dp[1][n] << endl;
    }
}



Measured memory_bytes: 35040
//#pragma GCC optimize(2)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cassert>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<cstdlib>
#include<string>
#include<cstring>
#include<bitset>
#define heap priority_queue<int,vector<int>,greater<int> >
#define _heap priority_queue<int,vector<int>,less<int> >
#define _for(a,b,c) for((a)=(b);(a)<=(c);++(a))
#define __for(a,b,c) for((a)=b;(a)>=(c);--(a))
#define _init(a,b) memset((a),(b),sizeof (a))
#define LL long long
#define mod 1e9+7
#define INF 0x3f3f3f3f
using namespace std;

namespace FastIO {
	template<typename tp> inline void read(tp &x) {
		x=0; register char c=getchar(); register bool f=0;
		for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
		for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
		if(f) x=-x;
	}
	template<typename tp> inline void write(tp x) {
		if (x==0) return (void) (putchar('0'));
		if (x<0) putchar('-'),x=-x;
		int pr[20]; register int cnt=0;
		for (;x;x/=10) pr[++cnt]=x%10;
		while (cnt) putchar(pr[cnt--]+'0');
	}
	template<typename tp> inline void writeln(tp x) {
		write(x);
		putchar('\n');
	}
}
using namespace FastIO;

//------------Coding Area------------
int n,d[200010];
int main(){
	read(n);
	for(int i=1;i<=n;++i) read(d[i]);
	sort(d+1,d+n+1);
	int ans=-1;
	for(int i=1;i<=n;++i){
		int cache1=max(d[i],d[n]-d[i]),cache2=max(ans,d[n]-ans);
		if(cache1<cache2) ans=d[i];
	}
	printf("%d %d\n",d[n],ans);
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define pi 3.14159
using namespace std;
typedef long long LL;
const LL MOD = 1e9 + 7;
const int N = 1e5 + 7, M = 1e7, OO = 0x3f3f3f3f;
#define AC ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin.sync_with_stdio(0);
int main()
{
int a,b,w;
scanf("%d %d %d",&w,&a,&b);
int maxi=max(a,b);
int mini=min(a,b);
printf("%d",max(maxi-(mini+w),0));



    return 0;
}


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

int main(){
  long s;
  cin >> s;
  if(s==1 || s==2 || s==4){
    cout << "4" << endl;
    return 0;
  }
  long i;
  for(i=2; i<1000000; i++){
    if(s%2==0) s=s/2;
    else s=3*s+1;
    if(s==4) break;
  }
  cout << i+3 << endl;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<utility>
#define REP(i,n) for(int i = 0;i < (n);i++)
#define pb push_back
using namespace std;
const int INF = 1e9;
typedef long long ll;

int main(){
  string s;
  cin >> s;
  s[3] = '8';
  cout << s << endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(){

  int prime[10001],i,j,p,sum;

  while(scanf("%d",&p) != EOF){

    for(i = 0; i < 10001; i++){
      prime[i] = 1;
    }

    prime[0] = 0;
    prime[1] = 0;

    for(i = 2; i < 10001; i++){
      if(prime[i] == 1){
	for(j = i * 2; j < 10001; j+=i){
	  prime[j] = 0;
	}
      }
    }

    sum = 0;
    
    for(i = 1; i <= p; i++){
      if(prime[i] == 1 && prime[p - i + 1] == 1){
	  sum++;
      }
    }
      
    printf("%d\n",sum);
      
  }

  return 0;
}

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

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

typedef long long ll;

const int mod = 1e9 + 7;

using namespace std;

map<ll, int> factor(ll n) {
	map<ll, int> f;
	for (ll i = 2; i * i < n; i++) {
		int x = 0;
		while (n % i == 0)n /= i, x++;
		if (x != 0)f[i] = x;
	}
	if (n != 1)f[n] = 1;
	return f;
}

int main(void) {
	ll N; cin >> N;
	
	auto f = factor(N);

	ll ans = 0;

	for (auto x : f) {
		int i = 1;
		int y = x.second;
		while(y >= i) {
			y -= i;
			i++;
			ans++;
		}
	}

	cout << ans << endl;

	return 0;
}

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

using namespace std;

void solve()
{
	int price;
	while(cin >> price, price)
	{
		vector<int> Vec;
		for(int i = 0; i < 12; ++i)
		{
			int in, out;
			cin >> in >> out;
			Vec.push_back(in - out);
		}
		bool endFlag = false;
		int sum = 0;
		for(int i = 0; i < 12; ++i)
		{
			sum += Vec[i];
			if(sum >= price)
			{
				cout << i + 1 << endl;
				endFlag = true;
				break;
			}
		}
		if(!endFlag)
		{
			cout << "NA" << endl;			
		}
	}
}

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

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


#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
#define iout(x) printf("%d\n",x)
#define lout(x) printf("%lld\n",x)
#define REP(x,l,u) for(int x = (l);x<=(u);x++)
#define RREP(x,l,u) for(int x = (l);x>=(u);x--)
#define mst(x,a) memset(x,a,sizeof(x))
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define MP make_pair
#define se second
#define fi first
#define dbg(x) cout<<#x<<" = "<<(x)<<endl;
#define sz(x) ((int)x.size())
#define cl(x) x.clear()

typedef  long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
using namespace std;

const int maxn = 310;
const int mod = 1e9+7;
const int MAX = 1000000010;
const double eps = 1e-6;
const double PI = acos(-1);

template<typename T> inline void read(T &x){
x=0;T f=1;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do x=x*10+ch-'0',ch=getchar();while(ch<='9'&&ch>='0');x*=f;
}

template<typename A,typename B> inline void read(A&x,B&y){read(x);read(y);}
template<typename A,typename B,typename C> inline void read(A&x,B&y,C&z){read(x);read(y);read(z);}
template<typename A,typename B,typename C,typename D> inline void read(A&x,B&y,C&z,D&w){read(x);read(y);read(z);read(w);}
template<typename A,typename B> inline A fexp(A x,B p){A ans=1;for(;p;p>>=1,x=1LL*x*x%mod)if(p&1)ans=1LL*ans*x%mod;return ans;}
template<typename A,typename B> inline A fexp(A x,B p,A mo){A ans=1;for(;p;p>>=1,x=1LL*x*x%mo)if(p&1)ans=1LL*ans*x%mo;return ans;}

int n,m;

int A[maxn][maxn],ban[maxn],has[maxn];

bool check(int M){
	REP(i,1,m)ban[i]=0;
	REP(i,1,m){
		REP(j,1,m)has[j]=0;
		REP(j,1,n){
			int x;
			REP(k,1,m)if(!ban[A[j][k]]){
				x=A[j][k];
				break;
			}
			has[x]++;
		}
		int mx=0;
		REP(j,1,m)if(has[j]>has[mx])mx=j;
		if(has[mx]<=M)return true;
		ban[mx]=1;
	}
	return false;
}

void Work(){
	int l=1,r=n;
	while(l<r){
		int M=l+r>>1;
		if(check(M))r=M;else l=M+1;
	}
	iout(l);
}

void Init(){
	read(n,m);
	REP(i,1,n)REP(j,1,m)read(A[i][j]);
}

int main(){
	Init();
	Work();
	return 0;
}


Measured memory_bytes: 640
def f():
    N = int(input())
    A = []
    
    for n in range(N):
        templist = []
        for a in range(int(input())):
            templist.append(list(map(int, input().split())))
        A.append(templist)
    
    # print(A)
    J = [0]
    maxlen = len(str(bin(2**len(A)-1).replace('0b','')))
    for j in reversed((range(2**len(A)))):
        tempb = str(bin(j).replace('0b',''))
        for i in range(maxlen - len(tempb)):
            tempb = '0'+tempb
        # ここでパターン仮置き確定
        tempj = list(map(int, list(tempb)))
        counter = 0
        for jj in range(len(tempj)):
            if tempj[jj] == 1: # 正直者の場合
                # 証言の数だけループを回す
                shocounter = 0
                for s in range(len(A[jj])):
                    if tempj[A[jj][s][0]-1] != A[jj][s][1]:# 本当は違う
                        break
                    else:
                        shocounter += 1
                if shocounter == len(A[jj]):
                    counter += 1
            else:
                # 証言の数だけループを回す
                shocounter = 0
                for s in range(len(A[jj])):
                    if tempj[A[jj][s][0]-1] == A[jj][s][1]:# 本当はあってる
                        continue
                    else:
                        shocounter += 1
                if shocounter > 0:
                    counter += 1
        if counter == len(A):
            J.append(tempj.count(1))
    
    list.sort(J, reverse=True)        
    return print(J[0])
    
f()

Measured memory_bytes: 3064
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // long long64_t, long long*_t
#include <cstdio> // prlong longf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <iomanip> //setprecision
#include <limits>
using namespace std;
int main(){
    long long x,x2,a;
    cin >> x;
    x2=x*2;
    a=sqrt(x2);
    if(a*(a+1)<x2) cout << a+1 << endl;
    else cout << a << endl;
}


Measured memory_bytes: 256
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
# 20:16
N = INT()
A = LIST()
 
flag = True
# A.sort()
 
# dic = {}
dic = defaultdict(int)
for i in range(N):
    if not A[i] in dic:
        dic[A[i]] = 1
    else:
        dic[A[i]] += 1
s = sum(A)
 
 
if N % 2 == 1:
    for i in range(N):
        if i == 0:
            if dic[i] != 1:
                flag = False
        elif i % 2 == 0:
            if dic[i] != 2:
                flag = False
        else:
            if dic[i] != 0:
                flag = False
        # elif dic[i * 2] != 2:
        #     flag = False
    if flag == False:
        print(0)
    else:
        if N == 1:
            print(1)
        else:
            print(2 ** ((N) // 2) % mod)
 
else:
    for i in range(N):
        if (i - 1) % 2 == 0:
            if dic[i] != 2:
                flag = False
        else:
            if dic[i] != 0:
                flag = False
    if flag == False:
        print(0)
    else:
        print(2 ** (N//2) % mod)
 
 
 
 
 
 
        
 
 
    # c = Counter(A)
    # c = sorted(c.items(), key=lambda x: x[0], reverse = False)
    # if c[0][1] != 1:
        # print(0)
    # for i in c[1:]:
        # if c[0]

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

using namespace std;

bool is_steppable(int index, char step) {
    if (step == 'U' || step == 'D') {
        return true;
    }
    if (index % 2 == 1) {
        return step == 'R';
    }
    return step == 'L';
}

int main()
{
    string S;
    cin >> S;
    const size_t len = S.length();
    for (int i = 0; i < len; ++i) {
        if (!is_steppable(i + 1, S[i])) {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 256
def d(u):
 global t
 C[u]=1;D[u]=t;t+=1
 for v in M[u]:v=int(v)-1;C[v]or d(v)
 F[u]=t;t+=1
N=int(input());R=range(N)
M=[input().split()[2:]for _ in R]
C,D,F=[0]*N,[0]*N,[0]*N
t=1
for i in R:C[i]or d(i)
for i in R:print(i+1,D[i],F[i])


Measured memory_bytes: 5712
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<unordered_map>
#include<stdio.h>
using namespace std;
typedef long long ll;

int main(){
	int A, B, C;
	cin>>A>>B>>C;
	if(A <= C and B >= C)cout<<"Yes"<<endl;
	else if(B <= C and A >= C) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}

Measured memory_bytes: 256
/*
オーダー
10**6	余裕を持って間に合う	
10**7	おそらく間に合う	余裕を持って間に合う
10**8	非常にシンプルな処理でない限り厳しい	おそらく間に合う
10**9		非常にシンプルな処理でない限り厳しい
logn	:OK
n		:10^7
nlogn	:10^6
n**2	:10^4
n**3	:300
2**n	:20
n!		:10



// 各桁の和を計算する関数
int findSumOfDigits(int n) {
  int sum = 0;
  while (n > 0) { // n が 0 になるまで
    sum += n % 10;
    n /= 10;
  }
  return sum;
}

sort(a, a + N, greater<int>());  // a[0:N] を大きい順にソート

int num[110] = {0};  // バケット
for (int i = 0; i < N; ++i) {
    num[d[i]]++;  // d[i] が 1 個増える
}

map<string, int> mp; // 連想配列 map<キー型, 値型> オブジェクト名
for (int i = 0; i < N; ++i) {
    auto itr = mp.find(s[i]);        // s[i] が設定されているか？
    if(itr != mp.end() ) {
         mp[s[i]] += 1;
    }
    else {
         mp[s[i]] += 1 ;
    }
}
stack<int> s;	//intをデータとするスタックを用意
s.push(1);		//{} -> {1}
printf("%d\n", s.top());	// 3
s.pop();

queue<int> que;	//intをデータとするキューを用意
que.push(1);		//{} -> {1}
printf("%d\n", que.front());	// 1
que.pop();
*/

#include <iostream>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <string.h>

using namespace std;

// #define for(i,a,b) for (int i=(a);i<(b);++i)
typedef long long ll;
typedef pair<ll,ll> P;
#define REP(i,n) for(long long i = 0; i < (long long)(n); i++)
#define pb push_back // vectorに要素追加
#define INF (ll)1e18
// int 
// // 各桁の和を計算する関数
// int findSumOfDigits(int n) {
//   int amari = 0;
//   int keta = 0;
//   while (n > 0) { // n が 0 になるまで
//     amari += n % 2;
//     if (keta%2==0)
//     n /= 10;
//   }
//   return sum;
// }
 
ll gcd(ll a, ll b) {
	if(b == 0) return a;
	return gcd(b, a % b);
}

// const ll MAX_N = 1e5;
// ll N;
// ll h[MAX_N];
// ll dp[MAX_N+1]; // メモ化テーブル
 
// // i番目以降の品物から重さの総和がj以下になるように選ぶ
// void rec(ll i){
// 	if (i==0) dp[i] = 0;
// 	else if (i==1) dp[i] = abs(h[1]-h[0]);
// 	else dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]));
// 	return;
// }
 
 
int main() {
	// 入力
	string S;
	cin>>S;
	// 解法
	ll i = 0;
	ll count = 0;
	string tmp = "";
	while (i<S.size()){
		// printf("%lld %s \n", count, tmp.c_str());
		if (i==S.size()-1 & tmp==S.substr(i,1)){ // 右端処理
			// printf("flag\n");
			// count--;
			i++;
		}
		else if (i==0){
			tmp = S.substr(0,1);
			count++;
			i++;
		}
		else if (tmp.size()==1 & tmp==S.substr(i,1)){
			tmp = S.substr(i,2);
			count++;
			i += 2;
		}
		else{
			tmp = S.substr(i,1);
			count++;
			i++;
		}
	}
	// printf("%lld %s \n", count, tmp.c_str());
	//出力
	cout << count << endl;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
  	cin >> n;
  	int cnt = 0;
  	for(int i = 1 ; i <= n ; i++){
		int x;
      	cin >> x;
      	if(x != i) cnt++;
    }
  	cnt == 2 || cnt == 0 ? cout <<"YES" : cout <<"NO" ;
 	return 0; 
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define n_l '\n'

#ifndef ONLINE_JUDGE
#define dbg(...) cout << "[" << #__VA_ARGS__ << "]: "; cout << to_string(__VA_ARGS__) << endl
template <typename T, size_t N> int SIZE(const T (&t)[N]){ return N; } template<typename T> int SIZE(const T &t){ return t.size(); } string to_string(const string s, int x1=0, int x2=1e9){ return '"' + ((x1 < s.size()) ? s.substr(x1, x2-x1+1) : "") + '"'; } string to_string(const char* s) { return to_string((string) s); } string to_string(const bool b) { return (b ? "true" : "false"); } string to_string(const char c){ return string({c}); } template<size_t N> string to_string(const bitset<N> &b, int x1=0, int x2=1e9){ string t = ""; for(int __iii__ = min(x1,SIZE(b)),  __jjj__ = min(x2, SIZE(b)-1); __iii__ <= __jjj__; ++__iii__){ t += b[__iii__] + '0'; } return '"' + t + '"'; } template <typename A, typename... C> string to_string(const A (&v), int x1=0, int x2=1e9, C... coords); int l_v_l_v_l = 0, t_a_b_s = 0; template <typename A, typename B> string to_string(const pair<A, B> &p) { l_v_l_v_l++; string res = "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; l_v_l_v_l--; return res; } template <typename A, typename... C> string to_string(const A (&v), int x1, int x2, C... coords) { int rnk = rank<A>::value; string tab(t_a_b_s, ' '); string res = ""; bool first = true; if(l_v_l_v_l == 0) res += n_l; res += tab + "["; x1 = min(x1, SIZE(v)), x2 = min(x2, SIZE(v)); auto l = begin(v); advance(l, x1); auto r = l; advance(r, (x2-x1) + (x2 < SIZE(v))); for (auto e = l; e != r; e = next(e)) { if (!first) { res += ", "; } first = false; l_v_l_v_l++; if(e != l){ if(rnk > 1) { res += n_l; t_a_b_s = l_v_l_v_l; }; } else{ t_a_b_s = 0; } res += to_string(*e, coords...); l_v_l_v_l--; } res += "]"; if(l_v_l_v_l == 0) res += n_l; return res; } void dbgm(){;} template<typename Heads, typename... Tails> void dbgm(Heads H, Tails... T){ cout << to_string(H) << " | "; dbgm(T...); } 
#define dbgm(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgm(__VA_ARGS__); cout << endl
#endif

#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef double db;
typedef vector<vi> vvi;
const ll mod=1000000007;
const ll N=200005; //check this
int dx[] = {-1, 0, 1, 0, 1, 1, -1, -1};
int dy[] = {0, -1, 0, 1, 1, -1, 1, -1};

ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll powb(ll a,ll b) {ll res=1;a ; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a;a=a*a;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    #ifndef ONLINE_JUDGE
    freopen("inputf.in", "r", stdin);
    freopen("outputf.in", "w", stdout);
    #endif

    int t=1;
    //cin>>t;
    while(t--){
    	// string s;cin>>s;
    	ll a;cin>>a;
    	cout<<a+a*a+a*a*a;
    }
}



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

//repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

//container util
#define all(x) (x).begin(),(x).end()

//typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;


//conversion
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}


int main(){
  int n,q;
  cin >> n >> q;
  string s;
  cin >> s;
  VI ACcnt(n,0);
  rep(i,s.size()-1){
    if(s[i] == 'A' && s[i+1] == 'C'){
      ACcnt[i+1] = 1;
    }
  }
  rep(i,n-1){
    ACcnt[i+1] += ACcnt[i];
  }
  rep(i,q){
    int l,r;
    cin >> l >> r;
    l--,r--;
    if(l != 0) cout << ACcnt[r] - ACcnt[l] << endl;
    else cout << ACcnt[r] << endl;
  }
  return 0;
}


Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
#define SORT(x) sort(x.begin(),x.end())
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1000000000
#define mod 1000000007
typedef long long ll;
const ll LINF = 1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int main(){
    int n;
    bool flag=false;
    cin>>n;
    rep(i,n){
        char c;
        cin>>c;
        if(c=='Y')  flag=true;
    }
    if(flag)    cout<<"Four"<<endl;
    else        cout<<"Three"<<endl;
    return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#if __cplusplus >= 201103L
#include <chrono>
using namespace std::chrono;
#endif
using namespace std;
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pb push_back
#define fi first
#define se second
#ifdef LOCAL
#define prln(x) (cout << #x << ' ' << x << endl)
#define pr(x) (cout << #x << ' ' << x << ' ' )
#define prv(x) (cout << x << ' ')
#else
#define prln(x) 
#define pr(x)
#define prv(x)
#endif
#define clr(x) memset((x), 0, sizeof((x)))
#define clr1(x) memset((x), -1, sizeof((x)))
#define endl "\n"
#define pi acos(-1)
#define rep(i, st, ed) for (int i = (st); i <= (ed); ++i)
#define rep0(i, st, ed) for (int i = (st); i < (ed); ++i)
#define per(i, st, ed) for (int i = (st); i >= ed; --i)
template<class T> void _sf(T &x) {cin >> x;}
void _sf(int &x) {scanf("%d", &x);}
void _sf(ll &x) {scanf("%lld", &x);}
void _sf(double &x) {scanf("%lf", &x);}
void _sf(char &x) {scanf(" %c", &x);}
void _sf(char *x) {scanf("%s", x);}
void sf() {}
template <class T, class...U> void sf(T & head, U&... tail) { _sf(head); sf(tail...);}
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
vector<int> vec;
map<int, int> mm;
set<int> ss;
int main(){
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        #if __cplusplus >= 201103L
        auto start = steady_clock::now();
        #endif
    #endif
    ll a, b;
    sf(a, b);
    ll aa = 1;
    for (ll i = 2; i * i <= a; i += aa, aa = 2) {
        if ( a % i == 0) {
            mm[i] = 1;
            while (a % i == 0) {
                a /= i;
            }
        }
    }
    if (a > 1) mm[a] = 1;

    ll bb = 1;
    ll ans = 1;
    for (ll i = 2; i * i <= b; i += bb, bb = 2) {
        if (b % i == 0) {
            if (mm[i] == 1) ++ans;
            while (b % i == 0) {
                b /= i;
            }
        }
    }
    if (b > 1 && mm[b]) ++ans; 
    cout << ans << endl;
    #ifdef LOCAL
        #if __cplusplus >= 201103L
        auto end = steady_clock::now();
        duration<double> time_span = duration_cast<duration<double>>(end - start);;
        printf("Total time: %.6fs\n", time_span.count());
        #endif
    #endif
    return 0;
}

Measured memory_bytes: 256