akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <iostream>
using namespace std;

void a(int x);

int main(){
  int n;
  int a1, a2, a3, a4, a5, a6;
  float t[40];

  a1 = a2 = a3 = a4 = a5 = a6 = 0;

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

  for (int i = 0; i < n; i++){
    if (t[i] < 165.0){
      a1++;
    }
    else if (t[i] < 170.0){
      a2++;
    }
    else if (t[i] < 175.0){
      a3++;
    }
    else if (t[i] < 180.0){
      a4++;
    }
    else if (t[i] < 185.0){
      a5++;
    }
    else {
      a6++;
    }
  }

  printf("1:");
  a(a1);

  printf("\n2:");
  a(a2);

  printf("\n3:");
  a(a3);

  printf("\n4:");
  a(a4);

  printf("\n5:");
  a(a5);

  printf("\n6:");
  a(a6);

  printf("\n");
}

void a(int x){
  for (int i = 0; i < x; i++){
    printf("*");
  }
}

Measured memory_bytes: 1204
#include<bits/stdc++.h>
using namespace std;
///Welcome to Nasif's Code
#define bug printf("bug\n");
#define bug2(var) cout<<#var<<" "<<var<<endl;
#define co(q) cout<<q<<endl;
#define all(q) (q).begin(),(q).end()
#define pi acos(-1)
#define inf 1000000000000000LL
#define FastRead    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define MODADD(ADD_X,ADD_Y)  (ADD_X+ADD_Y)%MOD;
#define MODSUB(SUB_X,SUB_Y)  (SUB_X-SUB_Y)+MOD)%MOD;
#define MODMUL(MUL_X,MUL_Y)  (MUL_X*MUL_Y)%MOD;
#define LCM(LCM_X,LCM_Y) (LCM_X*LCM_Y)/__gcd(LCM_X,LCM_Y);
typedef long long int ll;
typedef unsigned long long int ull;
const int MOD = (int)1e9+7;
const int MAX = 1e6;
int dx[]= {1,0,-1,0,1,-1,1,-1};
int dy[]= {0,1,0,-1,1,-1,-1,1};
int arr[MAX];
int main()
{
    FastRead
    //freopen("output.txt", "w", stdout);
    ll n,cnt=0;
    cin>>n;
    for(int i=0; i<n; i++)
        cin>>arr[i];
    sort(arr,arr+n);
    reverse(arr,arr+n);
    for(int i=0; i<=n-3; i++)
    {
        for(int j=i+1; j<n; j++)
        {
            int l=j+1,r=n-1,ans=0;
            while(l<=r)
            {
                int mid=(l+r)>>1;
                int cur=arr[j]+arr[mid];
                if(cur>arr[i])
                {
                    ans=mid-j;
                    l=mid+1;
                }
                else
                    r=mid-1;
            }
            cnt+=ans;
        }
    }
    cout<<cnt<<endl;


    return 0;
}


Measured memory_bytes: 3656
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) (int)((x).size())
#define debug(x) cout << #x << ":" << x << ' ';
#define debugg(x) cout << #x << ":" << x << ' ' << "\n";
#define endl "\n"
#define L(X) ((X)<<1)
#define R(X) (((X)<<1)|1)
#define M(X,Y) (((X)+(Y))>>1)

using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int MAXN = 1e5 + 5;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const long long int LLINF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-9;
const double PI = acos(-1);

template<typename T>   T max_self(T& a, T b) { if (a < b) a = b; return a; }
template<typename T>   T min_self(T& a, T b) { if (a > b) a = b; return a; }
template<typename T>   T add(T x, T y) { return ((x % MOD)  + (y % MOD)) % MOD;}
template<typename T>   T mul(T x, T y) { return ((x % MOD) * (long long)(y % MOD)) % MOD;}
template<typename T>   T sub(T x, T y) { return add(x, -y + MOD);}
template<typename T>   T gcd(T a, T b) { return b ? gcd(b, a % b) : a;}
template<typename T>   T lcm(T a, T b) { return a / gcd(a, b) * b;}
template<typename T>   vector<T> read(vector<T>& v, int n) {v.resize(n); for (auto &x : v)cin >> x;}
template<typename T>   void trav(vector<T> &v) {for (int i = 0 ; i < (int)v.size() ; ++i) {cout << v[i]; if (i != (int)v.size() - 1) cout << ' ';}}
int lg2(long long x)   {   return 64 - __builtin_clzll(x) - 1;  }
int lg2(int x)   {   return 32 - __builtin_clz(x) - 1;  }
#define NMAX 100005



int main()
{
    int X,Y;
    cin>>X>>Y;
    for (int i = 0; i <= 100; ++i)
    {
        for (int j = 0; j <= 100; ++j)
        {
            if(i+j == X  &&  i*4 + j*2 == Y){
                cout<<"Yes"<<endl;
                return 0;
            }
        }
    }
    cout<<"No"<<endl;

   return 0;
}


Measured memory_bytes: 3600
#include <cstdio>
#include <map>

const int MaxN = 100000 + 5;

struct Graph {
  int cnte;
  int Head[MaxN], To[MaxN * 2], Next[MaxN * 2];

  Graph() {
    cnte = 1;
  }

  inline void addEdge(int from, int to) {
    cnte++; To[cnte] = to;
    Next[cnte] = Head[from]; Head[from] = cnte;
  }
};

int N, K;
int Deg[MaxN];
int Col[MaxN];
Graph G;
std::map<int, bool> Mp[MaxN];

void init() {
  scanf("%d", &N);
  for (int i = 1; i < N; ++i) {
    int u, v;
    scanf("%d %d", &u, &v);
    G.addEdge(u, v); G.addEdge(v, u);
    Deg[u]++, Deg[v]++;
  }
}

void dfs(int u, int f) {
  int col = 1;
  for (int i = G.Head[u]; i; i = G.Next[i]) {
    int v = G.To[i];
    if (v == f) continue;
    while (Mp[u][col] == true) col++;
    Mp[u][col] = Mp[v][col] = true;
    Col[i >> 1] = col;
    dfs(v, u);
  }
}

void solve() {
  int mx = 0;
  for (int i = 1; i <= N; ++i)
    if (Deg[i] > Deg[mx]) mx = i;
  K = Deg[mx];
  printf("%d\n", K);
  dfs(mx, 0);
  for (int i = 1; i < N; ++i) printf("%d\n", Col[i]);
}

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

Measured memory_bytes: 18944
#include <iostream>
#include <list>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <map>
#include <chrono>
#include <math.h>
using namespace std;

using lli = long long int;
using Vint = std::vector<int>;
using Vlli = std::vector<lli>;
using Wint = std::vector<Vint>;
using Wlli = std::vector<Vlli>;
using Vbool = std::vector<bool>;
using pii = std::pair<int, int>;
using pll = std::pair<lli, lli>;
template <class T>
using Vec = std::vector<T>;

constexpr int MOD = 1e9 + 7;
constexpr int INFi = 2e9 + 1;
constexpr lli INFl = (lli)(9e18) + 1;
const vector<pii> DXDY = {std::make_pair(1, 0), std::make_pair(-1, 0), std::make_pair(0, 1), std::make_pair(0, -1)};
constexpr char BR = '\n';

#define FOR(i, a, b) for(int (i) = (a); (i) < (b); (i)++)
#define FOReq(i, a, b) for(int (i) = (a); (i) <= (b); (i)++)
#define rFOR(i, a, b) for(int (i) = (b); (i) >= (a); i--)
#define FORstep(i, a, b, step) for(int (i) = (a); i < (b); i += (step))
#define REP(i, n) FOR(i, 0, n)
#define rREP(i, n) rFOR(i, 0, (n-1))
#define vREP(ele, vec) for(auto &(ele) : (vec))
#define vREPcopy(ele, vec) for(auto (ele) : (vec))
#define SORT(A) std::sort((A).begin(), (A).end())
// 座標圧縮 (for vector) : ソートしてから使うのが一般的 ; SORT(A) => COORDINATE_COMPRESSION(A)
#define COORDINATE_COMPRESSION(A) (A).erase(unique((A).begin(),(A).end()),(A).end())



template <class T> inline int argmin(std::vector<T> vec){return min_element(vec.begin(), vec.end()) - vec.begin();}
template <class T> inline int argmax(std::vector<T> vec){return max_element(vec.begin(), vec.end()) - vec.begin();}
template <class T> inline void chmax(T &a, T b){a = max(a, b);}
template <class T> inline void chmin(T &a, T b){a = min(a, b);}
inline int BitI(int k){return 1 << k;}
inline lli BitL(int k){return 1L << k;}
inline int toInt(string &s){int res = 0; for(char a : s) res = 10 * res + (a - '0'); return res;}
inline int toInt(const string s){int res = 0; for(char a : s) res = 10 * res + (a - '0'); return res;}
inline long long int toLong(string &s){lli res = 0; for(char a : s) res = 10 * res + (a - '0'); return res;}
inline long long int toLong(const string s){lli res = 0; for(char a : s) res = 10 * res + (a - '0'); return res;}
template <class T> inline std::string toString(T n){
  if(n == 0) return "0";
  std::string res = "";
  if(n < 0){n = -n;while(n != 0){res += (char)(n % 10 + '0'); n /= 10;}
  std::reverse(res.begin(), res.end()); return '-' + res;}
  while(n != 0){res += (char)(n % 10 + '0'); n /= 10;} std::reverse(res.begin(), res.end()); return res;
}

// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~





int main(void){
  int a, b; scanf("%d%d", &a, &b); if(a > b) swap(a, b);
  int res = b; b--; if(a > b) swap(a, b);
  res += b; printf("%d\n", res);
  return 0;
}

Measured memory_bytes: 256
n, k = map(int, input().split())
s = input()
s1 = []
count = 0
if s[0] == "0":
    s1.append(0)
for i in range(n-1):
    if s[i+1] == s[i]:
        count += 1
    elif s[i+1] != s[i]:
        count += 1
        s1.append(count)
        count = 0
s1.append(count+1)
if s[-1] == "0":
    s1.append(0)

#print(s1)

# s1の累積和
s2 = [0]*(len(s1)+1)
s2[1] = s1[0]
for i in range(1, len(s1)):
    s2[i+1] = s1[i] + s2[i]
#print(s2)

ans = 0
if len(s2) > 2*k+1:
    for l in range(len(s2)-(2*k+1))[::2]:
        res = s2[2*k+1+l] - s2[l]
        ans = max(ans, res)
else:
    ans = s2[-1]
print(ans)

Measured memory_bytes: 46320
#include <bits/stdc++.h>
const long long INF = 1LL << 60;
const long long MOD = 1000000007;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i <= (n); ++i)
#define rrep(i, n) for (ll i = (n - 1); i >= 0; --i)
#define perm(c) sort(ALL(c));for(bool c##p=1;c##p;c##p=next_permutation(ALL(c)))
#define ALL(obj) (obj).begin(), (obj).end()
#define RALL(obj) (obj).rbegin(), (obj).rend()
#define MAX max<ll>
#define MIN min<ll>
#define pb push_back
#define to_s to_string
#define len(v) (ll)v.size()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define print(x) cout << (x) << '\n'
#define drop(x) cout << (x) << '\n', exit(0)
#define debug(x) cout << #x << ": " << (x) << '\n'
using namespace std;
using ll = long long;
typedef pair<ll, ll> P;
typedef vector<ll> vec;
typedef vector<vector<ll>> vec2;
typedef vector<vector<vector<ll>>> vec3;
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; }
ll devc(ll x, ll y) { return (x + y - 1) / y; }

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

    ll N;
    cin >> N;
    ll ans = 0;
    vec A = {};
    bool flag;
    rep(i, N){
        ll a;
        cin >> a;
        if(A.empty()) A.pb(a);
        if(len(A) == 1){
            if(a == A[0]) continue;
            flag = a > A[0];
            A.pb(a);
            continue;
        }

        if(flag) if(a < A.back()) ++ans, A = {};
        if(!flag) if(a > A.back()) ++ans, A = {};
        A.pb(a);
    }
    print(++ans);

    return 0;
}

Measured memory_bytes: 1400
import math

def getCount(K,i) :
    return math.log(K/i,2)

N, K = map(int, input().split(" "))
score = 0

for i in range(1,N+1) :
    if i >= K :
        score += 1/N
        continue
    count = math.ceil(getCount(K,i))
    score += 1/N * (1/2)**count
print(score)

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

typedef long long int ll;
typedef pair<int,int> pii;

ll minJump(vector<ll>a, int n){
    vector<ll>dp(n,0);
    dp[0] = 0;
    dp[1] = abs(a[0]-a[1]);

    for(int i=2;i<n;i++)
        dp[i] = min(dp[i-2]+abs(a[i-2]-a[i]), dp[i-1]+abs(a[i-1]-a[i]));

    return dp[n-1];
}

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

    vector<ll>a(n);
    for(auto &it:a) scanf("%lld",&it);

    ll ans = minJump(a,n);
    printf("%lld\n",ans);

    return 0;
}


Measured memory_bytes: 5552
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
using namespace std;
int a[300000], b[300000], c[300000], n, m, dist[600000];
vector<pair<int, int>>r[200000], x[600000];
int dijkstra() {
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>Q;
	for (int i = 0; i < 600000; i++)dist[i] = 999999999;
	for (int i = 0; i < r[1].size(); i++) {
		dist[r[1][i].second] = 0; Q.push(make_pair(0, r[1][i].second));
	}
	while (!Q.empty()) {
		int a1 = Q.top().first, a2 = Q.top().second; Q.pop();
		for (int i = 0; i < x[a2].size(); i++) {
			int to = x[a2][i].first, cost = x[a2][i].second;
			if (dist[to] > a1 + cost) {
				dist[to] = a1 + cost; Q.push(make_pair(dist[to], to));
			}
		}
	}
	int minx = 999999999;
	for (int i = 0; i < r[n].size(); i++)minx = min(minx, dist[r[n][i].second]);
	return minx;
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> a[i] >> b[i] >> c[i];
		r[a[i]].push_back(make_pair(c[i], i * 2));
		r[b[i]].push_back(make_pair(c[i], i * 2 + 1));
		x[i * 2].push_back(make_pair(i * 2 + 1, 0));
		x[i * 2 + 1].push_back(make_pair(i * 2, 0));
	}
	for (int i = 1; i <= n; i++) {
		sort(r[i].begin(), r[i].end());
		for (int j = 0; j < r[i].size(); j++) {
			x[m * 2 + i].push_back(make_pair(r[i][j].second, 0));
			x[r[i][j].second].push_back(make_pair(m * 2 + i, 1));
		}
		for (int j = 1; j < r[i].size(); j++) {
			if (r[i][j].first == r[i][j - 1].first) {
				x[r[i][j].second].push_back(make_pair(r[i][j - 1].second, 0));
				x[r[i][j - 1].second].push_back(make_pair(r[i][j].second, 0));
			}
		}
	}
	int ret = dijkstra() + 1; if (ret == 1000000000)ret = -1;
	cout << ret << endl;
	return 0;
}

Measured memory_bytes: 58996
s = int(input())

MOD = 10**9+7

def comb(n,k):
    MOD = 10**9+7
    nCk = 1
    for i in range(n-k+1, n+1):
        nCk *= i
        nCk %= MOD

    for i in range(1,k+1):
        nCk *= pow(i,MOD-2,MOD)
        nCk %= MOD
    return nCk

nmax = s // 3

if s < 3:
    print(0)
else:
    kai = 0
    for n in range(1,nmax+1):
        cir = s - 3 * n
        bar = n - 1
        #print("{} {} {}".format(n,cir,bar))
        kai = (kai + comb(cir+bar,bar)) % MOD
    print(kai)

Measured memory_bytes: 9204
#include <bits/stdc++.h>
#define PII pair<int, int>
#define LL long long
using namespace std;
const int MAXN = 200005;
const int INF = 100;

int K, dist[MAXN];
deque<int> deq;

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

	cin >> K;
	fill(dist, dist + K, INF);
	deq.push_back(1);
	dist[1] = 1;
	while (!deq.empty()) {
		int v = deq.front(), to1 = v * 10 % K, to2 = (v + 1) % K;
		deq.pop_front();
		if (dist[to1] > dist[v]) {
			dist[to1] = dist[v];
			deq.push_front(to1);
		}
		if (dist[to2] > dist[v] + 1) {
			dist[to2] = dist[v] + 1;
			deq.push_back(to2);
		}
	}
	
	cout << dist[0] << '\n';

	return 0;
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
using P = pair<ll, ll>;

int main(){
    string s;
    cin >> s;
    ll ans = 0;
    for(ll i = 0; i < s.size(); i++){
        if(i < s.size() / 2 + s.size() % 2){
            if(s[i] == 'p') ans--;
        }else{
            if(s[i] == 'g') ans++;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int l,r;
    cin>>l>>r;
    double a[l][r];
    for(int i=0;i<l;i++){
            for(int j=0;j<r;j++){
        cin>>a[i][j];
      }
    }
    double d;
    long long int e=0,ans=0;
    for(int i=0;i<l;i++){
        for (int j=i+1;j<l;j++){
                d=0;
            if (i!=j){
                for(int k=0;k<r;k++){
                    d+=(a[i][k]-a[j][k])*(a[i][k]-a[j][k]);
                }
        d=sqrt(d);
        e=d;
        if(e==d){
            ans++;
        }
            }
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <numeric>
#include <fstream>
using namespace std;
typedef long long ll;

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

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

string str, tmp;
char ch;
int pos;
void opr(int d=0) {
	if (d==0) {
		ch = str[pos];
	} else if (str[pos]=='\0' || str[pos]!=ch) {
		int nums[3] = { 0, 0, 0};
		int i;
		for (i=0; i<3; i++) {
			nums[i] = d % 10;
			d /= 10;
			if (d==0) break;
		}
		char ds[2] = { '0', '\0' };
		while (i>=0) {
			ds[0] = (char) ((int) '0' + nums[i]);
			tmp += ds;
			i--;
		}
		ds[0] = ch;
		tmp += ds;
		if (str[pos] == '\0') return;
		else {
			ch = str[pos];
			d = 0;
		}
	}
	pos++;
	return opr(d+1);
}

int main() {
	int N;
	while (cin >> N, N) {
		cin >> str;
		
		while (N--) {
			pos = 0;
			tmp = "";
			opr();
			str = tmp;
		}

		cout << str << endl;
	}
	return 0;
}

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

using namespace std;
int k,ans,now;
int main()
{
    scanf("%d",&k);
    while(ans<=80000000){
        ans++;
        now=(now*10+7)%k;
        if(now==0){printf("%d",ans);
        return 0;
        }
    }
    printf("-1");
    return 0;
}

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

int main(){
    int n;
    cin >> n;
    string s,sf,sl;
    vector <int> m(n,0);
    cout << 0 << endl;
    cin >> s;
    if(s=="Vacant"){
        exit(0);

    }
    else{
        /*if(s=="Male"){
            m[0]=1;
        }
        else{
            m[0]=-1;
        }*/
        sf=s;
    

    cout << n-1 << endl;
    cin >> s;
    if(s=="Vacant"){
        exit(0);
    }
    else{
        /*if(s=="Male"){
            m[n-1]=1;
        }
        else{
            m[n-1]=-1;
        }*/

        sl=s;


        int mi,r,l;
        r=n-1;
        l=0;
        while(r-l!=1){
            mi=(r+l)/2;
            cout << mi << endl;
            cin >> s;
            if(s=="Vacant"){
                exit(0);
        
                //break;
            }
            else{
                if(s==sf){
                    if((mi-l)%2==0){
                        l=mi;
                    }
                    else{
                        r=mi+1;
                    }
                }
                else{
                    if((mi-l)%2==0){
                        r=mi;
                    }
                    else{
                        l=mi-1;
                    }
                    
                }
            }
        }

    }

    

    }
    
    

    return 0;
}

Measured memory_bytes: 4020
#include <iostream>
#include <stack>

int main(){
  std::stack<int> s;
  std::string buf;

  while(std::cin >> buf){
    try{
      int i = stoi(buf);
      s.push(i);
    }
    catch(...){
      int a = s.top();
      s.pop();
      if(buf == "+"){
        s.top() += a;
      }
      else if(buf == "-"){
        s.top() -= a;
      }
      else{
        s.top() *= a;
      }
    }
  }
  std::cout << s.top() << std::endl;
}

Measured memory_bytes: 1308
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=1LL<<61;

int main() {
  ll n;
  cin >> n;
  vec a(n);
  for(ll i=0;i<n;i++) cin >> a[i];
  ll l=-1,r=-1;
  ll ans=1000;
  for(ll i=0;i<n;i++) {
    if(l==-1||l>a[i]||r>a[i]) {
      if(r!=-1) {
        ans=ans-ans/l*l+ans/l*r;
        r=-1;
      } 
      l=a[i];
    }
    else if(r==-1||r<a[i]) {
      r=a[i];
    }
  }
  if(r!=-1) ans=ans-ans/l*l+ans/l*r;
  cout << ans << endl;
}

Measured memory_bytes: 3620
#include <iostream>
#include <string>
#include <algorithm>

#define f for( int i=0; i<n; i++)
#define e '\n'
#define ll long long int

#define ii InputInteger()
#define il InputLong()
#define is InputString()

using namespace std;

void Ia(int arr[], int n)
{
    f
    {
        cin >> arr[i];
    }
}
void Pa(int arr[], int n)
{
    f
    {
        cout << arr[i] << e;
    }
}
int InputInteger()
{
    int n;
    cin >> n;
    return n;
}
ll InputLong()
{
	ll n;
	cin >> n;
	return n;
}
string InputString()
{
	string s;
	cin >> s;
	return s;
}
void Ca(int arr[], int n)
{
    for(int i=0; i<n; i++)
    {
        arr[ i ] = 0;
    }
}
int main()
{
    ios_base::sync_with_stdio( false );

        int n = ii, p = 0;
        int a[n], s[n];
        Ia(a, n);
        f
        {
            s[i] = a[i];
        }
        sort(s, s+n);
        f
        {
            if(a[i] != s[i]) p++;
        }
       if (p>2) cout << "NO";
       else cout << "YES";

    return 0;
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(v) (v).begin(), (v).end()
typedef long long int lint;
using namespace std;

int main() {
    string s;
    int k;
    cin >> s >> k;
    set<string> cands;
    for (int i = 1; i <= k; i++) {
        for (int j = 0; j + i <= s.length(); j++) {
            cands.insert(s.substr(j, i));
        }
    }
    auto itr = cands.begin();
    for (int i = 0; i < k - 1; i++) {
        itr++;
    }
    cout << (*itr) << endl;
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0; i<(int)(n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using Graph = vector<vi>;  // vi <=> vl
using vb = vector<bool>;
using boolGraph = vector<vb>;
using P = pair<int, int>;  // int <=> ll
const int MOD = 1e9+7;
const double EPS = 1e-9;

int main() {
  string s; cin >> s;
  int K; cin >> K;

  set<string> substr;
  rep(i,s.size()) {
    string tmp;
    rep(j,K) {
      if (i+j >= s.size()) break;
      tmp.push_back(s[i+j]);
      substr.insert(tmp);
    }
  }

  rep(i,K-1) substr.erase(*begin(substr));
  cout << *begin(substr) << endl;
  return 0;
}


Measured memory_bytes: 1664
#include<stdio.h>

int A[2000],n,B[2000];
void change(int,int);

int main(){

    int m,i,k;
        
    scanf("%d",&n);
    for(i = 0;i < n;i++){
        scanf("%d",&A[i]);
    }
    change(0,0);
    scanf("%d",&m);
    for(i = 0;i < m;i++){
        scanf("%d",&k);
        if(B[k]) printf("yes\n");
        else printf("no\n");
    }
    return 0;
}

void change(int count, int x){
    if(x == n){
        B[count] = 1;
        return;
    }
    change(count,x+1);
    if(count+A[x] <= 2000) change(count+A[x],x+1);
}


Measured memory_bytes: 2084
N,K = map(int,input().split())

if K == 0:
    print(N*N)
    exit()
ans = 0
for i in range(K+1,N+1):
    t,r = divmod(N,i)
    ans += t * (i-K) + ((r-K+1) if r-K+1 > 0 else 0)
print(ans)

Measured memory_bytes: 3060
#include "bits/stdc++.h"
#define MOD 1000000007
#define INF 11234567890
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

LL N, W, w[112], v[112];
std::vector<LL>list[4];
LL ans;

int main()
{
	in >> N >> W;
	rep(i, N) { in >> w[i] >> v[i]; }

	for (LL i = w[0]; i <= w[0] + 3; ++i)
	{
		rep(j, N)
		{
			if (i == w[j]) { list[i - w[0]].push_back(v[j]); }
		}
		if (list[i - w[0]].size() > 0)
		{
			std::sort(list[i - w[0]].begin(), list[i - w[0]].end(), std::greater<LL>());
			rep(j, list[i - w[0]].size() - 1) { list[i - w[0]][j + 1] += list[i - w[0]][j]; }
		}
	}
	rep(i, std::min<LL>(N, list[0].size()) + 1)
	{
		rep(j, std::min<LL>(N, list[1].size()) + 1)
		{
			rep(k, std::min<LL>(N, list[2].size()) + 1)
			{
				rep(l, std::min<LL>(N, list[3].size()) + 1)
				{
					LL v_sum = 0, w_sum = 0;
					LL a[] = { i,j,k,l };
					if (i + j + k + l > N) { continue; }
					rep(m, 4)
					{
						if (a[m] > 0)
						{
							v_sum += list[m][a[m] - 1];
							w_sum += (w[0] + m)*a[m];
						}
					}
					if (w_sum <= W) { ans = std::max(ans, v_sum); }
				}
			}
		}
	}

	out << ans << std::endl;
	return 0;
}

Measured memory_bytes: 256
def calc_primes(N):
    is_prime = {i: True for i in range(2, N+1)}
    primes = []
    for i in range(2, N+1):
        if is_prime[i]:
            primes.append(i)
            if i**2 <= N:
                for j in range(i**2, N+1, i):
                    is_prime[j] = False
    return primes


def main():
    N = int(input())
    arr = [str(x) for x in calc_primes(55555) if x % 5 == 1]
    print(" ".join(arr[:N]))


if __name__ == "__main__":
    main()


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

int main(){
  int N;
  cin>>N;
  
  int count=0;
  for(int a=0;a<=N/4;a++){
    for(int b=0;b<=N/7;b++){
      int sum=4*a+7*b;
      if(sum==N) count++;
    }
  }
  if(count!=0){
    cout<<"Yes"<<endl;
  }else cout<<"No"<<endl;
}

Measured memory_bytes: 256
// 2011/11/02 Tazoe

#include <iostream>
using namespace std;

int main()
{
	while(true){
		int m;
		cin >> m;
		if(m==0)
			break;

		int DP[8][1001];
		DP[0][0] = 1;
		for(int j=1; j<=1000; j++)
			DP[0][j] = 0;

		for(int i=1; i<=m; i++){
			for(int j=0; j<=1000; j++)
				DP[i][j] = DP[i-1][j];

			int a, b;
			cin >> a >> b;

			for(int j=0; j<=1000; j++){
				if(DP[i-1][j]==0)
					continue;

				for(int k=1; k<=b; k++){
					if(j+a*k>1000)
						break;

					DP[i][j+a*k] += DP[i-1][j];
				}
			}
		}

		int g;
		cin >> g;

		for(int i=0; i<g; i++){
			int n;
			cin >> n;

			cout << DP[m][n] << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using G = vector<vector<int>>;
    
int main(){
    int n, w;
    cin >> n >> w;
    vector<P> ob(n);
    rep(i,n){
        ll w,v;
        cin >> w >> v;
        ob[i] = P(w,v);
    }

    vector<vector<ll>> dp(n+1, vector<ll>(w+1, 0));
    for(int i=1; i<n+1; i++){
        for(int j=1; j<w+1; j++){
            if(j<ob[i-1].first) dp[i][j] = dp[i-1][j];
            else{
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-ob[i-1].first] + ob[i-1].second);
            }
        }
    }

    cout << *max_element(dp[n].begin(), dp[n].end()) << endl;

    return 0;
}

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

using namespace std;

#define ll long long
#define mod 1000000007

const ll INF = 1e11;

void solve(){

    int n, m; cin >> n >> m;
    vector<vector<int>> graph (n+1, vector<int> (0));
    vector<int> indeg (n+1, 0);
    vector<int> dp (n+1, 0);
    vector<int> toProcess;

    for(int i = 0; i < m; ++i){
        int u, v; cin >> u >> v;
        graph[u].push_back(v);
        indeg[v]++;
    }
    for(int i = 1; i <= n; ++i)
        if(!indeg[i]) toProcess.push_back(i);

    for(int i = 0; i < (int)toProcess.size(); ++i){
        int u = toProcess[i];
        for(int v : graph[u]){
            indeg[v]--;
            if(!indeg[v]) toProcess.push_back(v);
            dp[v] = max(dp[v], dp[u]+1);
        }
    }
    int ans = *max_element(dp.begin(), dp.end());

    cout << ans << endl;
    
    return;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
	return 0;
}

Measured memory_bytes: 10108
#include<stdio.h>
#include<stdlib.h>
int main(){
  int i,*num,n,j,t,judge;
  int lowkey,lowest,cnt=0,k;
  scanf("%d",&n);
  num = (int *)malloc(n * sizeof(int));
  for(i=0;i<n;i++)scanf("%d",&num[i]);

  for(i=0;i<n;i++){
    judge = 0;
    lowkey = num[i];
    lowest = i;
    for(j=i+1;j<n;j++){
      if(lowkey > num[j]){
        lowkey = num[j];
        lowest = j;
        judge = 1;
      }
    }
    t = num[i];
    num[i] = num[lowest];
    num[lowest] = t;
    if(judge == 1)cnt++;
  }
 
  for(i=0;i<n;i++){
    if(i == n-1){
      printf("%d\n",num[i]);
      break;
    }
    printf("%d ",num[i]);
  }
  printf("%d\n",cnt);
  return 0;
}


Measured memory_bytes: 2080
#include<cmath>
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<set>
#include<vector>
#include<bitset>
#define int long long
using namespace std;
const int maxn=100005,mod=1e9+7;
int n,a,b;
inline 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<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
inline void write(int a)
{
	if(a<0)
	{
		putchar('-');
		write(-a);
	}
	else
	{
		if(a>=10)
			write(a/10);
		putchar(a%10+'0');
	}
}
signed main()
{
	cin>>n>>a>>b;
	int a1=n/(a+b)*a,a2=min(n%(a+b),a);
	cout<<a1+a2;
	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <string>
#include <algorithm>
#include <bitset>
using namespace std;

typedef long long ll;

//#define dbg(arg) (printf arg)
#define dbg(arg)

ll find_same(vector<ll> &es, vector<ll>::iterator &it) {
  if (it == es.end()) return 0LL;
  ll num = *it;
//  cout << num << endl;
  while (it != es.end()) {
    ++it;
    if (num == (*it)) {
      ++it;
      return num;
    } else {
      num = (*it);
    }
  }
  return 0LL;
}

int main() {
    int n;
    scanf("%d", &n);
    vector<ll> es;
    for (int i = 0; i < n; ++i) {
      ll e;
      scanf("%lld", &e);
      es.emplace_back(e);
    }
    sort(es.begin(), es.end(), greater<ll>());
    auto it = es.begin();
    ll l[2] = { 0, 0 };;
    for (int i = 0; i < 2; ++i) {
      l[i] = find_same(es, it);
//      cout << it - es.begin() << ": " << l[i] << endl;
    }
    printf("%lld\n", l[0] * l[1]);
    return 0;
}


Measured memory_bytes: 1400
#include <iostream>

using namespace std ;

int main()
{

 int x,y;
 cin>>x>>y;
 if(x>20 || x<3 || y>20 || y<3)
    return 0;
int c=x+(x-1);
if(x+y>c)
    c=x+y;
if(y+(y-1)>c)
    c=y+(y-1);
cout<<c;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
    int h, w;
    while (true) {
        cin >> h >> w;
        if (h == 0 && w == 0) {
            break;
        }
        for (int j = 0; j < h; j++) {
            for (int i = 0; i < w; i++) {
                if (i > 0 && i < (w - 1) && j > 0 && j < (h -1)) {
                    cout << ".";
                } else {
                    cout << "#";
                }
            }
            cout << endl;
        }
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 3088
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> ii;

int mod = 998244353;
long long qexp(long long b, long long p){
    long long res = 1;
    while(p){
        if(p&1) res = (res * b) % mod;
        b = (b * b) % mod;
        p >>= 1;
    }
    return res;
}

int memo[3005][3005];
int a, b, c, d;
int dp(int H, int W){
	if(H == a && W == b){
		return 1;
	}
	if(H == a){
		return qexp(a, W-b);
	}
	if(W == b){
		return qexp(b, H-a);
	}
	if(memo[H][W] != -1) return memo[H][W];
	
	int ans = W * dp(H-1,W);
	ans += H * dp(H, W-1);
	ans -= (H-1)*(W-1)*dp(H-1,W-1);
	
	ans %= mod;
	if(ans < 0) ans += mod;
	
	memo[H][W] = ans;
	return ans;
}

signed main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	
	for(int i = 0;i < 3005;i++) for(int j = 0;j < 3005;j++) memo[i][j] = -1;
	cin >> a >> b >> c >> d;
	
	cout << dp(c,d);
}



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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int n, a[200005];
vector<int> v;
vector<int> G[200005];
int ans[200005];

void dfs(int n, int p = -1) {
	//cout << "DFS " << n << " " << p << endl;
	if (v.empty()) {
		v.push_back(a[n]);
		ans[n] = v.size();
		//cout << "DFS " << n << " " << ans[n] << endl;
		for (int h : G[n]) if (h != p) { dfs(h, n); }
	} else {
		int pos = lower_bound(all(v), a[n]) - v.begin();
		bool pop_type = false; int bak = 0;
		if (v.begin() + pos == v.end()) {
			pop_type = true;
			v.push_back(a[n]);
		} else {
			bak = v[pos];
			v[pos] = a[n];
		}
		ans[n] = v.size();
		//cout << "Res: " << n << " " << ans[n] << endl;

		for (int h : G[n]) if (h != p) { dfs(h, n); }
	
		if (pop_type) {
			v.pop_back();
		} else {
			v[pos] = bak;
		}
	}

}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	
	for (int i = 1; i < n; i++) {
		int u, v; cin >> u >> v;
		G[u].push_back(v); G[v].push_back(u);
	}
	
	dfs(1);
	rep(i, 1, n + 1) cout << ans[i] << endl;
}


Measured memory_bytes: 30476
get_number(Number) :-
    get_string(String),
    number_string(Number, String).

get_number(A, B) :-
    get_number(A),
    get_number(B).

get_number(A, B, C) :-
    get_number(A, B),
    get_number(C).

get_string(String) :-
    current_input(Input),
    read_string(Input, ' \n', '', _, String).

get_chars(Xs) :-
    get_string(S),
    string_chars(S, Xs).

/* memo
    code(int)
    string_code(1, S, C), (C: code)
    char_code(X, Y) (X: char, Y: code)
    string_chars(S, S2) (S: string, S2: [char])
    to_lower(C, C2) (C: char? C2: code?)
    sub_string

    f(0, [], []).
    f(Z, [X|Xs], [Y|Ys]) :- X = Y, f(Z1, Xs, Ys), Z is Z1 + 1.
    f(Z, [_|Xs], [_|Ys]) :- f(Z, Xs, Ys).

    match: =, \=

    numeric: <,=<, >, >= (eval)
    lexicographically: @<. @=<, @>, @>=
    value?: =:=, =\= (eval)
    identical: ==, \==
*/

main :-
    get_number(N, K),
    get_number(X, Y),
    Z is min(K, N) * X + max(0, N - K) * Y,
    writeln(Z).


Measured memory_bytes: 8148
#include<map>
#include<queue>
#include<cstdio>

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

using namespace std;

const int V_MAX=6000;
const int CAPA_INF=1<<29;
const int COST_INF=1<<29;

template<class T,class U>
struct edge{
	int v,rev;
	T capa;
	U cost;
	T flow;
};

template<class T,class U>
void add_directed_edge(vector< edge<T,U> > *G,int u,int v,T capa,U cost){
	G[u].push_back((edge<T,U>){v,G[v].size()  ,capa, cost,0});
	G[v].push_back((edge<T,U>){u,G[u].size()-1,   0,-cost,0});
}

template<class T,class U>
pair<T,U> augment(int n,vector< edge<T,U> > *G,int s,int t,U *pot){
	static int pre[V_MAX];
	static U d[V_MAX];
	rep(u,n) d[u]=(u==s?0:COST_INF);

	bool ok=false;
	priority_queue< pair<U,int> > Q; Q.push(make_pair(0,s));
	while(!Q.empty()){
		int u=Q.top().second;
		U cost=-Q.top().first; Q.pop();

		if(cost<d[u]) continue;
		if(u==t) ok=true;

		rep(i,G[u].size()){
			edge<T,U> &e=G[u][i];
			U cost2=cost+e.cost+pot[u]-pot[e.v];
			if(e.capa-e.flow>0 && cost2<d[e.v]){
				d[e.v]=cost2;
				pre[e.v]=e.rev;
				Q.push(make_pair(-cost2,e.v));
			}
		}
	}

	if(!ok) return make_pair(0,0);

	T water=CAPA_INF;
	for(int v=t;v!=s;){
		edge<T,U> &e1=G[v][pre[v]];
		edge<T,U> &e2=G[e1.v][e1.rev];
		water=min(water,e2.capa-e2.flow);
		v=e1.v;
	}

	U cost=0;
	for(int v=t;v!=s;){
		edge<T,U> &e1=G[v][pre[v]];
		edge<T,U> &e2=G[e1.v][e1.rev];
		e1.flow-=water;
		e2.flow+=water;
		cost+=water*e2.cost;
		v=e1.v;
	}

	rep(u,n) pot[u]+=d[u];

	return make_pair(water,cost);
}

template<class T,class U>
pair<T,U> primal_dual(int n,vector< edge<T,U> > *G,int s,int t){
	static U pot[V_MAX];
	rep(u,n) pot[u]=0;

	T ans1=0;
	U ans2=0;
	while(1){
		pair<T,U> tmp=augment(n,G,s,t,pot);
		if(tmp.first==0) break;
		ans1+=tmp.first;
		ans2+=tmp.second;
	}
	return make_pair(ans1,ans2);
}

struct train{
	int t1,t2,cost;
};

int main(){
	for(int n;scanf("%d",&n),n;){
		vector<train> T[99];
		rep(i,n-1){
			int m; scanf("%d",&m);
			T[i].resize(m);
			rep(j,m) scanf("%d%d%d",&T[i][j].t1,&T[i][j].t2,&T[i][j].cost);
		}
		int n_class; scanf("%d",&n_class);

		int V=0;
		map<int,int> f[100][2];
		map<int,int>::iterator it,jt;
		rep(i,n-1) rep(j,T[i].size()) {
			int t1=T[i][j].t1,t2=T[i][j].t2;
			if(f[ i ][0].count(t1)==0) f[ i ][0][t1]=V++;
			if(f[i+1][0].count(t2)==0) f[i+1][0][t2]=V++;
			if(f[i+1][1].count(t2)==0) f[i+1][1][t2]=V++;
		}

		int s=V++;
		int t=V++;
		static vector< edge<int,int> > G[V_MAX];
		rep(u,V) G[u].clear();

		add_directed_edge(G,s,f[0][0].begin()->second,n_class,0);
		add_directed_edge(G,f[n-1][0].rbegin()->second,t,n_class,0);
		rep(i,n){
			for(it=f[i][0].begin();it!=f[i][0].end();++it){
				jt=it;
				++jt;
				if(jt!=f[i][0].end()){
					add_directed_edge(G,it->second,jt->second,n_class,0);
				}
			}
			for(it=f[i][1].begin();it!=f[i][1].end();++it){
				int t=it->first;
				add_directed_edge(G,it->second,f[i][0][t],1,0);
			}
		}
		rep(i,n-1) rep(j,T[i].size()) {
			add_directed_edge(G,f[i][0][T[i][j].t1],f[i+1][1][T[i][j].t2],1,T[i][j].cost);
		}

		pair<int,int> ans=primal_dual(V,G,s,t);
		printf("%d %d\n",ans.first,ans.second);
	}

	return 0;
}

Measured memory_bytes: 0
from collections import deque, Counter, defaultdict
from itertools import chain, combinations
import json
# import numpy as np
import bisect
import sys
import math
import bisect
from functools import lru_cache

sys.setrecursionlimit(10 ** 8)

M = 10 ** 9 + 7
INF = 10 ** 17


def main():
    K = int(input())
    A, B = [int(a) for a in input().split()]

    for i in range(A, B + 1):
        if i % K == 0:
            print('OK')
            return
    print('NG')


if __name__ == "__main__":
    main()


Measured memory_bytes: 10120
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
ll c[30],s[400][30];
ll las[30];

int main()
{
	int D;
	cin >> D;
	rep(i,26)
	{
		cin >> c[i];
	}
	rep(i,D)
	{
		rep(j,26)
		{
			cin >> s[i][j];
		}
	}
	ll tmp = 0;
	//cout << "a" << endl;
	rep(i,D)
	{
		ll v;
		cin >> v;
		v--;
		tmp += s[i][v];
		las[v] = i+1;
		rep(j,26)
		{
			tmp -= c[j] * (i+1 - las[j]);
		}
		cout << tmp << endl;
	}
	return 0;
}

Measured memory_bytes: 3708
n = int(input())
AC= 0
WA= 0
TLE = 0
RE = 0

for x in range(n):
    s = input()
    if s == "AC":
        AC = AC +1
    elif s == "WA":
        WA += 1
    elif s == "TLE":
        TLE += 1
    elif s == "RE":
        RE +=1
print("AC x", AC)
print("WA x", WA)
print("TLE x", TLE)
print("RE x", RE)

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

int main() {
  ll n, x, m;
  cin >> n >> x >> m;

  vector<ll> v{0, x};
  ll h;
  {
    set<ll> s{x};
    ll e = x;
    while (s.count(e = e * e % m) == 0) {
      v.push_back(e);
      s.insert(e);
    }
    h = find(v.begin(), v.end(), e) - v.begin() - 1;
  }
  ll l = v.size() - 1;
  bool z = v.back() == 0;
  for (int i = 0; i + 1 < v.size(); i++) v[i + 1] += v[i];

  ll r = 0;
  if (n < h || z) {
    r += v[min(l, n)];
  } else {
    r += (n - h) / (l - h) * (v[l] - v[h]);
    r += v[h + (n - h) % (l - h)];
  }
  cout << r << endl;
}


Measured memory_bytes: 5844
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
signed main(){
  string s;
  cin>>s;
  int n=s.size();
  vector<int> v(n+1);
  v[0]=0;
  for(int i=0;i<n;i++){
    v[i+1]=v[i]^(1<<(s[i]-'a'));
  }
  vector<int> dp(n+1,1<<28);
  map<int,int> mm;
  dp[0]=0;
  for(int i=0;i<=n;i++){
    int b=v[i];
    if(!mm.count(b)) mm[b]=dp[i];
    mm[b]=min(mm[b],dp[i]);
    dp[i]=min(dp[i],mm[b]+1);
    for(int j=0;j<26;j++){
      b^=(1<<j);
      //if(mm.count(b)) cout<<i<<":"<<b<<" "<<mm[b]<<endl;
      if(mm.count(b)) dp[i]=min(dp[i],mm[b]+1);
      b^=(1<<j);
    }
    mm[b]=min(mm[b],dp[i]);
    //cout<<i<<":"<<dp[i]<<" "<<bitset<26>(b)<<endl;
    if(i<n) dp[i+1]=min(dp[i+1],dp[i]+1);
  }
  cout<<dp[n]<<endl;
  return 0;
}


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

int N;
int arr[10005];

int f(int x, int y, int z) {
	
	return x*x+y*y+z*z+x*y+x*z+y*z;
}

int main() {
	
	ios_base::sync_with_stdio(false);
	cin >> N;
	for(int i = 1; i <= 100; i++) {
		for(int j= 1; j <= 100; j++) {
			for(int k = 1; k <= 100; k++) {
				int p = f(i, j, k);
				if(p <= 10000) {
					arr[p]++;
				}
			}
		}
	}
	for(int i = 1; i <= N; i++) {
		if(arr[i] == 0) cout << "0\n";
		else {
			cout << arr[i] << "\n";
		}
	}
}

Measured memory_bytes: 3564
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <cmath>
#include <list>
#include <chrono>
#include <thread>
#include <thread>
#include <fstream>

using namespace std;

//const bool debug = false;

#ifndef M_PI
    const double M_PI = acos(-1.0);
#endif // M_PI

#define y1 roman_kaban
#define rank oryshych_konb
#define ull unsigned long long
//#define ll long long
const int mod = int(1e9) + 7;
//const int inf = 1e7;
//const long long infLL = 1e16;
//const int MX2 = 10100500; //  e7
//const long long INF = 1e18 + 0.5;
const int MX = 100500; //       e6
const int SZ = 110;

int b[SZ][SZ];
int a[MX];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    //freopen("/Users/ozzy/Documents/in.txt","r", stdin);
    int h, w, n;
    cin >> h >> w >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    int pos = 1;
    for(int i = 0; i < h; i++){
        for(int y = 0; y < w; y++){
            int j = y;
            if(i & 1) j = w - y - 1;
            //cerr << i << ' ' << j << ' ' << pos << endl;
            b[i][j] = pos;
            a[pos]--;
            if(a[pos] == 0) pos++;
        }
    }
    for(int i =0 ; i < h; i++){
        for(int j =0 ;j < w; j++){
            cout << b[i][j] << ' ';
        }
        cout << "\n";
    }
    return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define perl(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define pb push_back
#define ins insert
#define pqueue(x) priority_queue<x,vector<x>,greater<x>>
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
#define vtpl(x,y,z) vector<tuple<x,y,z>>
#define rev(x) reverse(x);
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
using vvpl=vector<vpl>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[8]={1,0,-1,0,1,1,-1,-1};
const ll dx[8]={0,-1,0,1,1,-1,1,-1};
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;
}
int main(){
    ll n;cin >> n;
    vl v(n);rep(i,n)cin >> v[i];
    vector<bool> check(n,false);
    set<ll> s;
    rep(i,n){
        if(s.count(v[i]+1)==0)check[v[i]-1]=true;
        s.ins(v[i]);
    }
    check[n-1]=false;
    ll ans=0;
    ll i=0;
    while(i<n){
        if(check[i]){
            ll k=0;
            while(check[i]){
                k++;
                i++;
            }
            chmax(ans,k);
        }
        i++;
    }
    cout << n-ans-1 <<endl;
}

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

signed main(){
  int n,k,s;cin>>n>>k>>s;
  if(s==INF){
    for(int i=0;i<k;i++)cout<<s<<" ";
    for(int i=0;i<n-k;i++)cout<<1<<" ";
  }
  else{
    for(int i=0;i<k;i++)cout<<s<<" ";
    for(int i=0;i<n-k;i++)cout<<INF<<" ";
  }
  cout<<endl;
}


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

int main(){
    int n;
    cin >> n;
    int ans = 0;
    while(true){
        if(n >= 1000){
            n = n - 1000;
        }
        
        if(n < 1000) break;

    }

    if(n==0){
    cout << 0 << endl;
    }
    else {
        cout << 1000 - n << endl;
    }
}

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

// string S = "SAT";
string S;
string weekdays[] = {"SUN", "MON", "TUE", "WED" ,"THU", "FRI", "SAT"};

int main() {
    cin >> S;

    for (int i = 0; i < 7; i++) {
        if (S == weekdays[i]) {
            printf("%d\n", 7 - i);
            return 0;
        }
    }
}

Measured memory_bytes: 256
using System;
class Program
{
	static void Main(string[] args)
	{
		// 整数の入力
		//int a = int.Parse(Console.ReadLine());
		// スペース区切りの整数の入力
		string[] input = Console.ReadLine().Split(' ');
		int a = int.Parse(input[0]);
		int b = int.Parse(input[1]);
        int c = int.Parse(input[2]);
		// 文字列の入力
		//string s = Console.ReadLine();

        int limit = b /a;
        if(limit < 0){
            Console.WriteLine(0);
        }else if(limit < c){
            Console.WriteLine(limit);
        }else{
            Console.WriteLine(c);
        }
		//出力
		//Console.WriteLine((a+b+c) + " " + s);
	}
}

Measured memory_bytes: 11092
#include <bits/stdc++.h>
using namespace std;
#define cerr if (false) cerr
#define db(x) cerr << #x << "=" << x << endl
#define db2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define db3(x, y, z) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define dbv(v) cerr << #v << "="; for (auto _x : v) cerr << _x << ", "; cerr << endl
#define dba(a, n) cerr << #a << "="; for (int _i = 0; _i < (n); ++_i) cerr << a[_i] << ", "; cerr << endl
template <typename A, typename B>
ostream& operator<<(ostream& os, const pair<A, B>& x) {
	return os << "(" << x.first << "," << x.second << ")";
}
typedef long long ll;
typedef long double ld;
int main() {
	int n;
	scanf("%d", &n);
	vector<int> a(n + 2);
	vector<int> vals = {0};
	int st = 0;
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
	}
	for (int i = 1; i <= n + 1; ++i) {
		vector<pair<int, int>> vs;
		for (int j = 0; j < vals.size(); ++j) {
			// 0 .. vals[j] - 1;
			// 0 .. vals[j] - 1 - (a[i - 1] - a[i])
			int d = a[i - 1] - a[i];
			int x = st - j;
			if (vals[j] - 1 >= 0) ++x;
			if (vals[j] - 1 - d >= 0) ++x;
			vs.emplace_back(0, x);
			if (d >= 0) {
				if (vals[j] - 1 - d >= 0) vs.emplace_back(vals[j] - d, --x);
				if (vals[j] - 1 >= 0) vs.emplace_back(vals[j], --x);
			} else {
				if (vals[j] - 1 >= 0) vs.emplace_back(vals[j], --x);
				if (vals[j] - 1 - d >= 0) vs.emplace_back(vals[j] - d, --x);
			}
		}
		sort(vs.begin(), vs.end());
		int mn = INT_MAX;
		st = INT_MAX;
		vals = {0};
		for (auto& v : vs) {
			if (v.first > a[i]) break;
			mn = min(mn, v.second);
			if (v.first == 0) st = min(st, mn);
			else {
				if (mn <= st - 1 && vals.size() < 2) vals.push_back(v.first);
				if (mn == st - 2 && vals.size() < 3) vals.push_back(v.first);
			}
		}
	}
	printf("%d\n", st);
}


Measured memory_bytes: 1024
list1=input().split(' ')
n=int(list1[0])
m=int(list1[1])
c=int(list1[2])
list2=input().split(' ')
correct=0
for i in range(n):
    list=input().split(' ')
    amount=0
    for j in range(m):
        amount+=int(list2[j])*int(list[j])
    amount+=c
    if amount>0:
        correct+=1
print(correct)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int main(){
	scanf("%d%d",&n,&k);
	if(k>(n-1)*(n-2)/2){puts("-1");return 0;}
	m=n-1+(n-1)*(n-2)/2-k;
	printf("%d\n",m);
	for(int j=2;j<=n;j++)printf("1 %d\n",j);
	m-=n-1;
	for(int i=2;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(m==0)break;m--;
			printf("%d %d\n",i,j);
		}
		if(m==0)break;
	}
	return 0;
}

Measured memory_bytes: 256
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		String s = scan.next();
		int s_length = s.length();
		String message = "no";
		Set<String> set = new HashSet<String>();
		for(int i = 0; i < s_length; i++) {
			set.add(s.charAt(i) + "");
		}
		if(s_length == set.size()) {
			message = "yes";
		}
		System.out.println(message);
	}
}

Measured memory_bytes: 23124
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>
using namespace std;
typedef long long ll;
ll const INF = 1LL << 60;
ll const HUGE_NUM = 1000000007;
ll MEMO[1001][1001];
ll const MOVE[2][2] = {{0, 1}, {1, 0}};

ll dfs(ll h, ll w, ll H, ll W, vector<vector<char>>& A) {
  if (MEMO[h][w] != -1) {
    return MEMO[h][w];
  }
  if (h == H && w == W) {
    return 1;
  }
  ll path_num = 0;
  for (auto m : MOVE) {
    ll next_h = h + m[0];
    ll next_w = w + m[1];
    bool is_searchable = next_h <= H && next_w <= W;
    if (is_searchable && A[next_h][next_w] == '.')
      path_num = (path_num + dfs(next_h, next_w, H, W, A)) % HUGE_NUM;
  }
  MEMO[h][w] = path_num;
  return path_num;
}

int main() {
  ll H, W;
  cin >> H >> W;
  vector<vector<char>> A(H);
  char a;
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      cin >> a;
      A[i].push_back(a);
    }
  }
  for (int h = 0; h < H; h++) {
    for (int w = 0; w < W; w++) {
      MEMO[h][w] = -1;
    }
  }

  ll ans = dfs(0, 0, H - 1, W - 1, A);
  cout << ans % HUGE_NUM << endl;
  return 0;
}

Measured memory_bytes: 9216
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll N,K;ll dp[100001];
ll a[101];ll mini =numeric_limits<ll>::max();
ll ans(ll k){
      if(k<mini)return 1;
      if(dp[k]!=-1)return dp[k];
      for(ll i=0;i<N;i++){
            if(k>=a[i] && ans(k-a[i])==1){
                  dp[k] = 0;
                  return dp[k];
            }
      }
      dp[k] = 1;
      return dp[k];
}
int main(){
      cin>>N>>K;for(ll i=0;i<N;i++)cin>>a[i],mini = min(mini,a[i]);
      memset(dp,-1,sizeof(dp));
      if(ans(K)==0)cout<<"First"<<endl;
      else cout<<"Second"<<endl;
      return 0;
}


Measured memory_bytes: 4096