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

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()
#define endl "\n"

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
typedef long long ll;

void solve() {
    ll H,A;
    cin >> H >> A;
    cout << (H+A-1)/A << endl;
}

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

Measured memory_bytes: 3564
import sys
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))

def main():
    n = II()
    t, a = MII()
    hh = MII()
    d = []
    for i, h in enumerate(hh):
        d.append((i+1, abs(a - (t - h*0.006))))
    d.sort(key=lambda x: x[1])
    print(d[0][0])

if __name__ == '__main__':
    main()


Measured memory_bytes: 3188
#include <cstdio>
#include <climits>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <list>
#include <set>
#include <bitset>
#include <iterator>
#define loop(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) for(long long i = 0; i < (long long)(n); i++)
#define debug(x)  cout << #x << " = " << (x) << endl;

using namespace std;
using LL = long long int;
using ULL = unsigned long long;

int main() {
    LL n, k; cin >> n >> k;
    LL ans = 0;
    if (k == 0) {
        cout << n * n << endl;
        return 0;
    }
    for (LL b = 1; b <= n; b++)  {
        ans += max(0LL, b - k) * (n / b) + max(0LL, n % b - k + 1);
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
n,k = map(int, input().split())
dp = [float("inf")] * 100000
h = list(map(int, input().split()))
dp[0] = 0
for i in range(n):
    for j in range(1,k+1):
        if i+j < n:
            dp[i+j] = min(dp[i+j], dp[i] + abs(h[i]-h[i+j]))
print(dp[n-1])


Measured memory_bytes: 85836
#include <bits/stdc++.h>
using namespace std;
vector< vector<long> > a, dp;
long w, n;
long rec(long i, long j)
{
    if (i >= n )
    {
        return 0;
    }
    else
    {
        if (dp[i][j] == 0)
        {
            if(j < a[i][0]){
                dp[i][j] = rec(i + 1, j);
            }
            else{
                dp[i][j] = max(rec(i + 1, j),rec(i + 1, j - a[i][0]) + a[i][1]);
            }
           
        }
        return dp[i][j];
    }
}
int main()
{
    cin >> n >> w;
    a.resize(n, vector<long>(2, 0));
    for (vector<long> &i : a)
    {
        for (long &x : i)
        {
            cin >> x;
        }
    }
    dp.resize(n, vector<long>(w + 1, 0));
    cout << rec(0, w) << endl;
    return 0;
}

Measured memory_bytes: 79488
#include<iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <map>
#include <bitset>
#include <stack>
#include <queue>
#include <fstream>

using namespace std;
using ll = long long;

#define PRI(n) cout << n << " "<<endl;
#define PRI2(n, m) cout << n << " " << m << " "<<endl;

#define REP(i, n)  for(int i = 0; i < (int)n; ++i)
#define FOR(i, t, n)  for(int i = t; i <= (int)n; ++i)

const char alphabet[26] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r',
                           's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
const ll MOD = 1e9 + 7;

struct edge;
struct UnionFind;

bool isPrime(ll x);

ll GCD(ll a, ll b);

ll LCM(ll a, ll b);

ll nCr(int n, int r);


struct UnionFind {
    vector<int> par;
    vector<int> rank;

    UnionFind(int N) {
        for (int i = 0; i < N; ++i) {
            par.push_back(i);
            rank.push_back(0);
        }
    }

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

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

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

ll N, M;
string S;
vector<edge> X[100010];
bool B[100010];
int D[100010];

int main() {
    cin >> N;
    vector<int> A(N);
    REP(i, N) {
        int a;
        cin >> a;
        D[a]++;
    }
    int cnt = 0;
    FOR(i, 1, 100000) {
        int c = D[i - 1] + D[i] + D[i + 1];
        if(c>cnt)cnt = c;
    }
    PRI(cnt)
    return 0;
}

struct edge {
    int to, cost;
    bool flag = false;
};

bool isPrime(ll x) {
    if (x == 0)return 0;
    if (x == 1)return 0;
    if (x == 2)return 1;
    if (x % 2 == 0)return 0;
    FOR(i, 3, x - 1) {
        if (x % i == 0)return 0;
    }
    return 1;
}

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

ll LCM(ll a, ll b) {
    ll gcd = GCD(a, b);
    return a / gcd * b;
}

ll nCr(int n, int r) {
    vector<ll> C(r + 1);
    C[0] = 1;
    FOR(i, 1, n) for (int j = min(i, r); j < 1; --j)C[j] = (C[j] + C[j - 1]) % MOD;
    return C[r];
}


Measured memory_bytes: 3328
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <vector>
#include <functional>
using namespace std;

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


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

#define gcu getchar_unlocked
#define pcu putchar_unlocked
#define _il inline
#define _in _il int in
#define _sc _il bool scan
_in(int c){int n=0;bool m=false;if(c=='-')m=true,c=gcu();
	do{n=10*n+(c-'0'),c=gcu();}while(c>='0');return m?-n:n;} //&&c<='9'
_in() {return in(gcu());}
_sc(int &n){int c=gcu();return c==EOF?false:(n=in(c),true);}
_sc(char &c){c=gcu();gcu();return c!=EOF;}
bool scan(complex<double> &p) {
	double x, y;
	if (scanf("%lf,%lf", &x, &y) == EOF)
		return false;
	p = {x, y};
	return true;
}
//_sc(string &s){int c;s="";
//	for(;;){c=gcu();if(c=='\n'||c==' ')return true;else if(c==EOF)return false;s+=c;}}
template <typename H,typename... T> _sc(H &h, T&&... t){return scan(h)&&scan(t...);}
#define _vo _il void out
#define _vl _il void outl
template <typename T>
_vo(T n){static char buf[20];char *p=buf;
	if(n<0)pcu('-'),n*=-1;if(!n)*p++='0';else while(n)*p++=n%10+'0',n/=10;
	while (p!=buf)pcu(*--p);}
_vo(const char *s){while(*s)pcu(*s++);}
_vo(char c){pcu(c);}
//_vo(string &s){for (char c: s) pcu(c);}
template <typename H,typename... T> _vo(H&& h, T&&... t){out(h);out(move(t)...);}
//template <typename T> _vo(vector<T> &v){for(T &x:v)out(&x == &v[0]?"":" "),out(x);out('\n');}
_vl(){out('\n');}
template <typename... T> _vl(T&&... t){out(move(t)...);outl();}


int main() {
	complex<double> p1, p2, p3;
	double s = 0;
	scan(p1, p2);
	p2 -= p1;
	while (scan(p3)) {
		p3 -= p1;
		s += abs(p2.real() * p3.imag() - p3.real() * p2.imag()) / 2;
		p2 = p3;
	}
	printf("%lf\n", s);
}


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

unsigned long long knapsack(vector<unsigned long long>&weight,vector<unsigned long long>&value,int n,int W)
{   vector<vector<unsigned long long>>dp(n+1,vector<unsigned long long>(W+1,0));
    for(int i=1;i<=n;i++)
    {
      for(unsigned long long w = 1;w<=W;w++)
      {   if(w>=weight[i-1])
        dp[i][w] = max(value[i-1]+dp[i-1][w-weight[i-1]],dp[i-1][w]);
          else dp[i][w] = dp[i-1][w];
      }
         
    }
    return dp[weight.size()][W];
}
int main()
{
     int n,W;
  cin>>n>>W;
  vector<unsigned long long>weight(n),value(n);
  for(int i =0;i<n;i++)
  {
    cin>>weight[i]>>value[i];
  }
  cout<<knapsack(weight,value,n,W)<<endl;
}

Measured memory_bytes: 80256
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <stack>
#include <cctype>
#include <complex>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cassert>

using namespace std;


bool solve(){
	double x,h;
	while(1){
		cin>> x>> h;
		if(x==0&&h==0) break;
		double ans = x*x + sqrt(x*x*x*x + 4*x*x*h*h);
		cout<< ans<< endl;
	}
	return true;
}

int main(){
	cout.setf(ios::fixed);
	cout.precision(10);
	solve();
	return 0;
}

 

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

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n,m;cin>>n>>m;
  vector<P> ans;
  int c=n/2;
  if(n%2){
    for(int l=1,r=n-1;l<r;l++,r--)ans.emplace_back(l,r);
  }
  else {
      bool flag =false;
      for(int l=1,r=n-1;l<r;l++,r--){
          if(!flag&&r-l<=c){
              --r;
              flag=true;
          }
          ans.emplace_back(l,r);
      }
  }
  rep(i,m)cout<<ans[i].first<<' '<<ans[i].second<<endl;
  return 0;
  }


Measured memory_bytes: 4124
#include "bits/stdc++.h"
using namespace std;
#define INF 1000000000
#define rep(i, n) for(int i = 0; i < n; i++)
#define ALL(x) (x).begin(), (x).end()  //昇順
#define RALL(x) (x).rbegin(), (x).rend() // 降順
const long long mod = 1e9+7;
typedef priority_queue<int> PQ;
typedef vector<long long> Vl;
typedef vector<int> VI;  // VI a(n);
typedef vector<string> VS;  
typedef vector<char> VC; 
typedef vector<VS> VSS;
typedef vector<VC> VCC;    
typedef vector<VI> VVI;   // VVI a(n,vector<int>(m)) n * m 
typedef vector<Vl> VVl;
typedef pair<int, int> PII;
typedef map<int, int> MP;   //MP a;
typedef vector<pair<int, int> > PS;
typedef long long ll;  //ll とdoubleは違う
//stack<int> st;
// cout << << endl;
// cin >> ;
template<typename T>   // operator << (cout,a);
ostream& operator << (ostream& os, vector<T>& v) {
    os << "{";
    rep(i, (int)v.size()) { os << v[i] << (i < v.size() - 1 ? ", " : ""); }
    os << "}";
    return os;
}
template<typename T>
T gcd(T a, T b){
	return b != 0 ? gcd(b, a % b) : a;
}   
 
int main(){
    ll x,y,d=0,n,m,h,k,max=-100000,min=10000000,ans=0,count=1,sum=0;
    string s;
    cin >> n;
    VI a(n);
    VI b(n);
    rep(i,n){
        cin >> a[i];
        b[i] = a[i];
	}
    sort(ALL(b));

    for(int i=0;i<n;i++){
        if(a[i] > b[n/2-1] )
            cout << b[n/2-1] << endl;
        else
            cout <<  b[n/2]<< endl;
    }
    
    return 0;
}

Measured memory_bytes: 3712
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define mii map <int, int>
#define mll map <ll, ll>
#define pii pair <int, int>
#define pll pair <ll, ll>
#define vi vector <int>
#define vd vector <double>
#define vll vector <ll>
#define fi first
#define se second
#define si set <int>
#define sll set <ll>
#define spii set <pii>
#define vs vector <string>
#define vpii vector <pair <int,int> >
#define vpll vector <pair <long long,long long> >
#define vvi vector <vector <int> >
#define vvpii vector <vector <pii > >
#define mp make_pair
#define vvll vector <vll>
#define vsi vector <si>
#define forn(i, n) for (int i = 0; i < (n); i++)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define for1(i, n) for (int i = 1; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(),(x).rend()


const ll INFLL = 1e18;
const int MAXN = 1e6+100;
const ll INF = 1e9;
const ll mod1=1e9+7;
const ll mod2=2e9+11;
vvi g;
vi used;
int cnt=0;
vector <int >d;
void dfs(int s)
{
    used[s]=1;
    cnt++;
    for (auto to:g[s])
    {
        if (used[to]==0)
            dfs(to);
    }
}
void bfs()
{
    d[0]=0;
    queue<int> q;
    q.push(0);
    while (!q.empty())
    {
        int f=q.front();
        q.pop();
        for (auto to:g[f])
        {
            if (d[to]==INF)
            {
                d[to]=d[f]+1;
                q.push(to);
            }
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#ifdef LOCAL
    freopen("a.in","r",stdin);
#endif
    int n;
    cin>>n;
    int m;
    cin>>m;
    g=vvi(n);
    while (m--)
    {
        int u,v;
        cin>>u>>v;
        u--,v--;
        g[u].pb(v);
        g[v].pb(u);
    }
    used=vi(n);
    dfs(0);
    if (cnt!=n)
    {
        cout<<"No";
        return 0;
    }
    d=vi(n,INF);
    cout<<"Yes\n";
    bfs();
    for (int i=1;i<n;i++)
    {
        int mx=-2;
        for (auto to:g[i])
        {
            if (d[to]==d[i]-1)
                mx=to;
        }
        cout<<mx+1<<'\n';
    }


}


Measured memory_bytes: 12636
#include <stdio.h>
#include <iostream>

using namespace std;

#define REP(a, i, n) for (int i = a; i < n; ++i)

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

    if (X == 3 || X == 5 || X == 7) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#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>       // int64_t, int*_t
#include <cstdio>        // printf
#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 <cmath>

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()
#define all2(a, b) (a).begin(), (a).begin() + (b)

int count(int N)
{
        int ans = 0;
        while (N)
        {
                ans++;
                N /= 10;
        }
        return ans;
}

int main()
{
        ll N;
        cin >> N;
        ll ans = count(N);
        for (ll A = 1; A * A <= N; A++)
        {
                if (N % A != 0)
                {
                        continue;
                }
                ll B = N / A;
                ll cnt = max(count(A), count(B));
                ans = min(ans, cnt);
        }
        cout << ans << endl;

        return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  int N,K;
  cin>>N>>K;
  int score[N]={0};//おかしある2,ない1
  for(int i=1;i<=N;i++)score[i]=1;
  for(int i=1;i<=K;i++){
    int d;
    cin>>d;
    for(int j=1;j<=d;j++){
      int A;
      cin>>A;
      score[A]=2;
    }
  }
  int ans=0;
  for(int i=1;i<=N;i++){
    if(score[i]==1)ans++;
  }
  cout<<ans<<endl;
}
  

Measured memory_bytes: 3676
W,H = map(int,input().split())
ans = 10**30
for i in range(1,W):
    a = H*i
    w = W - i
    b = max((w//2)*H,w*(H//2))
    c = w*H - b
    x = max(a,b,c) - min(a,b,c)
    ans = min(ans,x)
for i in range(1,H):
    a = W*i
    h = H - i
    b = max((W//2)*h,W*(h//2))
    c = h*W - b
    x = max(a,b,c) - min(a,b,c)
    ans = min(ans,x)
print(ans)


Measured memory_bytes: 3064
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007

int N;
vector<int> G[2000];
int B[2000];
int fact[2001];
vector<int> dp[2000][2];
vector<int> dp2[2][3];

vector<int> merge(vector<int> &a, vector<int> &b) {
  vector<int> o(a.size()+b.size()-1, 0);
  rep(i, a.size()) {
    rep(j, b.size()) {
      o[i+j] = (o[i+j] + 1LL*a[i]*b[j])%MOD;
    }
  }
  return o;
}
void add(vector<int> &to, vector<int> src) {
  if (to.size() < src.size()) to.resize(src.size(), 0);
  rep(i, src.size()) to[i] = (to[i]+src[i]) % MOD;
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  fact[0] = 1;
  for (int i=1; i<=2000; i++) fact[i] = (1LL*i*fact[i-1])%MOD;

  cin >> N;
  for (int i=1; i<N; i++) {
    int p;
    cin >> p;
    p--;
    G[p].pb(i);
  }
  for (int x=N-1; x>=0; x--) {
    dp2[0][0] = {1};
    dp2[0][1] = {0};
    dp2[0][2] = {0};
    for (int t : G[x]) {
      rep(k, 3) dp2[1][k].clear();
      rep(k, 3) add(dp2[1][k], merge(dp2[0][k], dp[t][0]));
      rep(k, 2) add(dp2[1][k+1], merge(dp2[0][k], dp[t][1]));
      swap(dp2[0], dp2[1]);
    }
    add(dp[x][1], dp2[0][0]);
    add(dp[x][1], dp2[0][1]);
    dp[x][1].insert(dp[x][1].begin(), 0); // s++

    add(dp[x][0], dp2[0][0]);
    for (int &x : dp2[0][1]) x = (2LL*x) % MOD;
    for (int &x : dp2[0][2]) x = (2LL*x) % MOD;
    add(dp[x][0], dp2[0][1]);
    add(dp[x][0], dp2[0][2]);
  }
  int sum = 0;
  for (int s=0; s<dp[0][0].size(); s++) {
    int e = dp[0][0][s];
    if (s%2) e = (MOD-e) % MOD;
    sum = (sum + 1LL*e*fact[N-s])%MOD;
  }
  cout << sum << "\n";
  return 0;
}


Measured memory_bytes: 32000
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;
const ll MOD = 1e9+7;
 
int main(){
  int n;
  cin >> n;

  vector<double> a(n);
  for(int i=0; i<n; i++) cin >> a[i];

  double bunbo=0;
  for(int i=0; i<n; i++) bunbo+=1/a[i];
  printf("%.7f\n", 1/bunbo);

}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <map>
#include <algorithm>


int main()
{
    std::string sW;
    while (true)
    {
        std::cin >> sW;
        if(sW == "-")
        {
            break;
        }
        size_t m;
        std::cin >> m;
        for (int64_t i = 0; i < m; i++)
        {
            int64_t h;
            std::cin >> h;

            std::string t;
            for (int j = 0; j < sW.size(); j++)
            {
                size_t sj = (j + h) % sW.size();
                t.push_back(sW[sj]);
            }
            sW = std::move(t);
        }
        std::cout << sW << "\n";
    }
    return 0;
}


Measured memory_bytes: 3124
#include<iostream>
 
using namespace std;
 
int main() {
  int n;
  cin>>n;
  int a[n-1];
  for(int i=0;i<n-1;i++) {
    cin>>a[i];
  }
  int count=a[0];
  for(int i=0;i<n-2;i++) {
    if(a[i]>=a[i+1]) {
      count += a[i+1];
    }
    else if(a[i]<a[i+1]) {
      count += a[i];
    }
  }
  
  cout<<(count+a[n-2])<<endl;
  
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cmath>
#include<complex>
#include<vector>
#include<map>
#include<queue>

using namespace std;

typedef pair< int, int > Pi;

int p, q, a, n;

int rec( int bunbo, int bunsi, int cnt, int idx){ //rec(分母, 分子, 個数, 今のidx)
  if(cnt > n) return 0;
  if(bunbo * p == bunsi * q) return 1;
  if(bunbo * p < bunsi * q) return 0;
  int ret = 0;
  for(int i = idx; i * bunbo <= a; i++){
    ret += rec( bunbo * i, bunsi * i + bunbo, cnt + 1, i);
  }
  return ret;
}

int main(){
  while(cin >> p >> q >> a >> n, p||q||a||n){
    cout << rec( 1, 0, 0, 1) << endl;
  }
}

Measured memory_bytes: 1160
import java.util.*;
import javax.lang.model.util.ElementScanner6;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 入力
        int a = sc.nextInt();
        int b = sc.nextInt();

        // 処理
        StringBuilder work = new StringBuilder();
        for (int i = 0; i < b; i++) {
            work.append(Integer.toString(a));
        }
        String aaa = work.toString();

        StringBuilder work1 = new StringBuilder();
        for (int i = 0; i < a; i++) {
            work1.append(Integer.toString(b));
        }
        String bbb = work1.toString();

        String out = aaa.compareTo(bbb) > 0 ? bbb : aaa;

        // 出力
        System.out.println(out);
    }
}

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

using namespace std;

#define S scanf
#define P printf
#define G getline
#define SZ size()
#define C clear()
#define B begin()
#define F front()
#define T top()
#define E end()
#define EM empty()
#define V vector
#define Q queue
#define DQ deque
#define PQ priority_queue
#define ST stack
#define FI first
#define SE second
#define PI acos(-1)
#define PS push
#define PP pop()
#define PSF push_front
#define PSB push_back
#define PPF pop_front()
#define PPB pop_back()
#define MP make_pair
#define LL long long int
#define ULL unsigned long long int
#define PII pair<int,int>
#define PSI pair<string,int>
#define PIS pair<int,string>
#define PLI pair<long long int,int>
#define PLL pair<long long int,long long int>
#define MII map<int,int>
#define MSI map<string,int>
#define MIS map<int,string>
#define MLI map<long long int,int>
#define FAST() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

LL big_mod(LL val,LL pow,LL mod);
LL mod_inverse(LL val,LL mod);
string sum_of_two_strings(string a,string b);







int main()
{
    FAST();

//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);

    int a,b,n;
    cin >> n >> a >> b;
    cout << min(n*a,b);
    return 0;
}








LL big_mod(LL val,LL pow,LL mod)
{
    LL res = 1;
    val = val % mod;
    while(pow > 0)
    {
        if(pow & 1)
        {
            res = (res*val) % mod;
        }
        pow = pow >> 1;
        val = (val*val) % mod;
    }
    return res;
}

LL mod_inverse(LL val,LL mod)
{
    LL mod1 = mod;
    if(mod == 1)
    {
        return 0;
    }
    LL y = 0;
    LL x = 1;
    LL quotient,temp;
    while(val > 1)
    {
        quotient = val / mod;
        temp = mod;
        mod = val % mod;
        val = temp;
        temp = y;
        y = x - quotient * y;
        x = temp;
    }
    if(x < 0)
    {
        x += mod1;
    }
    return x;
}

string sum_of_two_strings(string a,string b)
{
    reverse(a.B,a.E);
    reverse(b.B,b.E);
    char c;
    string ans="";
    int length_of_a=a.SZ,length_of_b=b.SZ;
    int i,carry=0,sum,length=max(length_of_a,length_of_b);
    for(i=0; i<length; i++)
    {
        if(i >= length_of_a)
        {
            sum=(b[i]-48)+carry;
        }
        else if(i >= length_of_b)
        {
            sum=(a[i]-48)+carry;
        }
        else
        {
            sum=(a[i]-48)+(b[i]-48)+carry;
        }
        carry=sum/10;
        sum%=10;
        c=sum+48;
        ans+=c;
    }
    if(carry > 0)
    {
        ans+=(carry+48);
    }
    reverse(ans.B,ans.E);
    return ans;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
int main(){
  int h;
  cin >> h;
  while(h!=0){
    vector <int> lines[5];
    int b[10][5];
    int i,j,k;
    for(i=0;i<h;i++){
      for(j=0;j<5;j++){
        cin >> b[i][j];
      }
    }
    for(i=h-1;i>=0;i--){
      for(j=0;j<5;j++){
        lines[j].push_back(b[i][j]);
      }
    }
     
    int o=0;
    int f=0,ba,l;
    while(f==0){
       
      k=0;
       
      for(i=0;i<5;i++) k+=lines[i].size();
       
      for(i=h-1;i>=0;i--){
        l=0;
        ba=0;
        for(j=0;j<5;j++){
                if(lines[j].size()>i){
                    if(ba==0){
                        ba=lines[j][i];
                        l=1;
                    }else if(ba==lines[j][i]){
                        l++;
                    }else{
                        if(l>=3){
                            o+=ba*l;
                            for(int a=1;a<=l;a++) lines[j-a].erase(lines[j-a].begin()+i);
                        }
                    ba=lines[j][i];
                    l=1;
                    }
                }else{
            ba=0;
            l=0;
            }
        }
     
        if(l>=3){
            o+=ba*l;
            for(int a=0;a<l;a++) lines[4-a].erase(lines[4-a].begin()+i);
        }   
     
    }
    for(i=0;i<5;i++) k-=lines[i].size();
    if(k==0) f=1;
    }
     
    cout << o << endl;
    cin >> h;
  }
  return 0;
}


Measured memory_bytes: 3036
n = int(input())
s = n // 3

def cmb2(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10**9 + 7
N = 2000  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)


total = 0
for i in range(s):
  y = n - 3*(i+1)
  x = cmb2(y+i,i,p)
  total = (total + x) % (10**9+7)
  
print(total)  
  



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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
//#pragma GCC optimize ("-O3") 
#ifdef YANG33
#include "mydebug.hpp"
#else
#define DD(x) 
#endif
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  __MAKE_TIME__  Problem: __PROBLEM__ / Link: __CONTEST_URL__  ----- */
/* ------問題------



-----問題ここまで----- */
/* -----解説等-----



----解説ここまで---- */



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

	LL ans = 0;
	LL N, K; cin >> N >> K;
	VI L(N);
	FOR(i, 0, N) {
		cin >> L[i];
	}
	SORT(L);

	FOR(i, 0, N) {
		LL sum = 0;
		FOR(j, i, i + K) {
			if (j < N)sum += L[j];
		}
		ans = max(ans, sum);
	}

	cout << ans << endl;

	return 0;
}


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

using namespace std;

const int N=1e6+3;

const double eps=1e-9;

#define pb push_back
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define f first
#define s second
typedef long long ll;

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

const int mod=1e9+7;

int n,a[N],b[N],m,k,q,u,v,x,y,tc,l,r,c,ans;

char s[N],grid[N];

void IO(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	#ifndef ONLINE_JUDGE
		freopen("test.txt","r",stdin);
	#endif
}

int main(){
	//IO();
	scanf("%d%d",&n,&m);
	if (n<=m)
		printf("un");
	printf("safe\n");
}


Measured memory_bytes: 3760
#include<iostream>
#include<vector>
#include<algorithm>

int main(){

    size_t n, c, k;
    std::cin >> n >> c >> k;

    std::vector<size_t> t(n);
    for(auto&& e : t){
        std::cin >> e;
    }

    std::sort(t.begin(), t.end());

    size_t cnt = 0, size = 0, time = t[0];
    for(size_t i = 0; i < n; i++){
        if(t[i] - time <= k && size < c){
            size++;
        }else{
            size = 1;
            time = t[i];
            cnt++;
        }
    }

    std::cout << cnt + 1 << std::endl;

    return 0;
}


Measured memory_bytes: 1024
# A - Harmony
#
# 2分探索法

a, b = gets.split.map(&:to_i)


if a<b
  tmp = a
  a = b
  b = tmp
end



def binary_search(a, b)

  head = b
  tail = a

  while head <= tail

    center = (head + tail) / 2

    if (a-center).abs == (b-center).abs
      return "#{center}"
    elsif (b-center).abs < (a-center).abs
      head = center + 1
    else
      tail = center - 1
    end

  end

  return "IMPOSSIBLE"

end

puts binary_search(a, b)


Measured memory_bytes: 1788
(* O(n) *)
let w = read_line ()
let n = String.length w
let _ =
  for i = Char.code 'a' to Char.code 'z' do
    let c = ref 0 in
    String.iter (fun x -> if x = Char.chr i then incr c) w;
    if !c mod 2 <> 0 then (print_endline "No"; exit 0)
  done;
  print_endline "Yes"

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

int main(){
    int a,b,c,x; cin>>a>>b>>c>>x;

    int count = 0;

    for(int i=0; i<=a; i++){
        for(int j=0; j<=b; j++){
            for(int k=0; k<=c; k++){
                if(500*i + 100*j + 50*k == x) count++;
            }
        }
    }

    cout<<count<<endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
const ll INF = 1LL << 60;

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];

    //mapのキーには出てきた数字が何か、値にはそれが何回出現したかを記録する
    map<int,int> m;
    //範囲for文の変数前に&をつけるとコンテナ内の要素を変更できる
    for(auto &i:a){
        m[i] ++;
    }

    int cnt=0;
    for(auto &i:m){
        if(i.first < i.second){
            cnt += i.second - i.first;
        }
        else if(i.first > i.second){
            cnt += i.second;
        }
    }
    cout << cnt << endl;


}

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

int main() {
	int N, M, al = 0;
	cin >> N >> M;
	vector<int> A(N);
	for (int i = 0;i < N;i++) {
		cin >> A[i];
		al += A[i];
	}
	if (al % (4 * M) == 0) {
		al /= (4 * M);
	}
	else {
		al = al / (4 * M) + 1;
	}
	int cnt = 0;
	for (int i = 0;i < N;i++) {
		if (A[i] >= al) {
			cnt++;
		}
	}
	if (cnt < M)cout << "No" << endl;
	else cout << "Yes" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int n;
string s;
int main(void){
    cin>>n>>s;
    if(n%2==1){
        cout<<"No"<<endl;
        return 0;
    }
    else{
        if(s.substr(0,n/2)==s.substr(n/2,n/2)){
            cout<<"Yes"<<endl;
        }
        else cout<<"No"<<endl;
    }
}


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

using namespace std;

/* alias */
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
using vpii = vector<pii>;

/* const */
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1e9 + 7;

/* repetition */
#define rep(i, n) for(int i=0;i<(n);++i)
#define repe(i, n) for(int i=0;i<=(n);++i)
#define repr(i, n) for(int i=(n-1);i>=0;--i)
#define repre(i, n) for(int i=(n);i>=0;--i)
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define FORE(i, a, b) for(int i=(a);i<=(b);++i)
#define FORR(i, a, b) for(int i=(b-1);i>=(a);--i)
#define FORRE(i, a, b) for(int i=(b);i>=(a);--i)

int main() {
    int pn;
    ll N, K, Q;
    
    cin >> N >> K >> Q;
    
    vector<ll> points(N,K);
    rep(i,Q){
        cin >> pn;
        points.at(pn-1) +=1;
    }

    rep(i,N){
        if (points.at(i) <= Q){
            cout << "No" << endl;
        }
        else{
            cout << "Yes" << endl;;
        }
    }

}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i, s) for (int i = 0; i < s; ++i)
#define ALL(v) (v).begin(), (v).end()
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define DEBUG
#define int long long
#define INF 1e18
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }
template<class T>void show(vector<T>v){for (int i = 0; i < v.size(); i++){cerr<<v[i]<<" ";}cerr<<"\n";}
typedef long long ll;


int n,m,k;
int a[100010],b[100010],c[100010],d[100010];
using Graph=vector<vector<int>>;
Graph G,G2;

struct UnionFind
{
    vector<int> par;

    UnionFind(int n) : par(n, -1) {}
    void init(int n) { par.assign(n, -1); }

    int root(int x)
    {
        if (par[x] < 0)
            return x;
        return par[x] = root(par[x]);
    }

    bool issame(int x, int y)
    {
        return root(x) == root(y);
    }
    bool merge(int x, int y)
    {
        x = root(x);
        y = root(y);
        if (x == y)
            return false;
        if (par[x] > par[y])
            swap(x, y);
        par[x] += par[y];
        par[y] = x; //大きさが正になるよ
        return true;
    }
    int size(int x)
    {
        return -par[root(x)];
    }
};

signed main()
{
    cin>>n>>m>>k;
    G.assign(n,vector<int>());
    G2.assign(n, vector<int>());
    REP(i,m) cin>>a[i]>>b[i];
    REP(i,k) cin>>c[i]>>d[i];
    REP(i,m) a[i]--,b[i]--;
    REP(i,k) c[i]--,d[i]--;
    UnionFind uni(n);
   // uni.merge(0,1);
    REP(i,m){
        G[a[i]].push_back(b[i]);
        G[b[i]].push_back(a[i]);
        uni.merge(a[i],b[i]);
    }
    int cnt=0;
    for (int i = 0; i < n; i++)
    {
        if(G[i].size()==0) cnt++;
    }
    REP(i, k)
    {
        G2[c[i]].push_back(d[i]);
        G2[d[i]].push_back(c[i]);
        
    }
    REP(i,n){
        
        //cout<<n-1-cnt-G[i].size()-G2[i].size()<<" ";
        int cnt=0;
        //cerr<<uni.size(i)<<endl;
        for (int j = 0; j < G2[i].size(); j++)
        {
            if(uni.issame(i,G2[i][j])) cnt++;
        }
        //cerr<<cnt<<endl;
        cout<<uni.size(i)-1 - G[i].size() - cnt<<" ";
        
    }
    cout<<endl;
    
     return 0;
}

Measured memory_bytes: 16884
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define dump(...)
#endif
#define endl '\n'
#define ll long long
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define REPS(i, x) for (int i = 1; i <= (int)(x); i++)
#define RREP(i, x) for (int i = ((int)(x)-1); i >= 0; i--)
#define RREPS(i, x) for (int i = ((int)(x)); i > 0; i--)
#define INF 2147483647
#define LLINF 9223372036854775807LL
#define vi vector<int>
#define vvi vector<vector<int>>
#define pi pair<int, int>
#define ALL(a) (a).begin(), (a).end()
#define BIT(n) (1LL << (n))
#define TOUPPER(s) transform(s.begin(), s.end(), s.begin(), ::toupper)
#define TOLOWER(s) transform(s.begin(), s.end(), s.begin(), ::tolower)
#define FILLZERO(s, n)                      \
    do {                                    \
        ostringstream os;                   \
        os << setw(n) << setfill('0') << s; \
        s = os.str();                       \
    } while (0);
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end()) //sortしてからつかうこと
#define INIT                               \
    std::cin.tie(nullptr);                 \
    std::ios_base::sync_with_stdio(false); \
    cout << std::fixed << std::setprecision(10);

template <typename T>
vector<T> make_vec(size_t a, T n) { return vector<T>(a, n); }
template <typename T, typename... Ts>
auto make_vec(size_t a, Ts... ts) { return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...)); }
template <class T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
    for (T &x : vec)
        is >> x;
    return is;
}

constexpr ll MOD = 1e9 + 7;
int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
ll A, B, C, D, E, F, G, H, N, M, L, K, P, Q, R, W, X, Y, Z;
string S, T;
ll ans = 0;

signed main() {
    INIT;
    cin >> T >> S >> T;
    string res = string("A") + S[0] + "C";
    cout << res << endl;
}

Measured memory_bytes: 3636
import java.util.*;

public class Main {
    public static void main(String[] args) {
        int n;
        int sum;
        int count;
        int income[] = new int[10000];
        Scanner sc = new Scanner(System.in);
        while ((n = Integer.parseInt(sc.next())) != 0) {
            sum = 0;
            for (int i = 0; i < n; i++) {
                income[i] =  Integer.parseInt(sc.next());
                sum += income[i];
            }
            int average = sum / n;
            count = 0;
            for (int i = 0; i < n; i++) {
                if (income[i] <= average) {
                    count++;
                }
            }
            System.out.println(count);
        }
        sc.close();
    }
}



Measured memory_bytes: 49928
# coding: utf-8

N = int(input())
T,A = map(int, input().split())
H = list(map(int, input().split()))

min=1000000000
for i in range(N):
    diff = abs((T-H[i]*0.006)-A)
    if (min>diff):
        min = diff
        point = i+1
print(point) 

Measured memory_bytes: 38256
#include<bits/stdc++.h>
using namespace std;
double a,b;
int h,m;
int main(){
    scanf("%lf%lf%d%d",&a,&b,&h,&m);
    printf("%.9f",sqrt(a*a+b*b-2*a*b*cos((abs(30*h-5.5*m)*(acos(-1)/180)))));
    return 0;
}

Measured memory_bytes: 4216
/*

a[n-1] < a[0] + a[1]
		STATE
a[n-1] + a[n-2] < a[0] + a[1] + a[2]  <--- then this is true too
a[n-1] + a[n-2] + a[n-3] < a[0] + a[1] + a[2] + a[3]   <--- if this is true

n=9

a[1] <= a[2] <= ... <= a[n]
a[1] + ... + a[5] > a[6] + ... + a[9]
a[1] := A[5] - A[1] >= 0
a[7] := A[7] - A[5]
5 * A[5] - a[1] - a[2] - a[3] - a[4] > 4 * A[5] + a[6] + a[7] + a[8] + a[9]
A[5] - a[1] - a[2] - a[3] - a[4] > a[6] + a[7] + a[8] + a[9]
A[5] > a[1] + a[2] + a[3] + a[4] + a[6] + a[7] + a[8] + a[9]



											a[9] + ... a[6] < a[0] + ... + a[4]

2 5 8 8 12 15 20 | ............

(20-15)+(20-12)+... = diff

dp[i][value][diff]
		diff = 20*i - sum  <= N
...
a[n-1] + ... + a[3] < a[0] + ... + a[n-3]         a[n-1] + a[n-2] < a[0] + a[1] + a[2]
a[n-1] + ... + a[2] < a[0] + a[1] + ... + a[n-2]        a[n-1] < a[0] + a[1]


1 2 3 4 5 6 7 8
X X *       * X

dp[i=1][value 1][value n-1][difference]
O(N^6) states and O(N^2) transitions per state


2^N .. 2^(2N)









width = N / 2
for(height)
	for(areaAbove)
		ways = ...

.......XXXXXX
...XXXXX.....
...X.........
...X.........
..XX.........
XXX..........
X............

 2 2 3 6 6 6 6 7 7 7 7 7
1 0 1 3 0 0 0 1 0 0 0 0   sum(value)=height
    
    sum(value * i) = areaAbove

dp[i][sum][areaAbove]




I give up with O(N^2) approach, and just try to get O(N^2 log(N)).


After seeing some part of the editorial:

x[i] = A[i] - A[i-1]
x[1] + x[2] + ... + x[n] <= N - 1

a[1] + ... + a[5] > a[6] + ... + a[9]
a[1] > -a[2] - a[3] - a[4] - a[5] + a[6] + a[7] + a[8] + a[9]
a[1] > -(a[1] + x[2] + a[1] + x[2] + x[3] + ... + a[1] + x[2] + x[3] + x[4] + x[5])
	   +(a[1] + x[2..6] + a[1] + x[2..7] + a[1] + x[2..8] + a[1] + x[2..9])

a[1] > x[3..9] + x[4..8] + x[5..7] + x[6..6]
 

x[1] + ... + x[n] <= N - 1
									BAD IDEA: x[i] := x[i]+1

x[1]>= x[1..n] * (0, 0, 1, 2, 3, 4, 3, 2, 1)
                       3  4  5  6  7  8  9
                      
                 (0, 0, 1, 1, 2, 2, 3, 3, 4, 4) <--- n = 10

			  1  2  3  4  5  6
          (1, 2, 3, 4, 5, 6, 7)
                 ^     ^      
                   
                   
                   1 2 3
                   ^   ^
               1 2 3 4 5

			dp[sum][weightedSum]
		-> dp[sum+x][weightedSum+sum+x]

x[1] + sum <= N - 1
x[1] >= weightedSum			    

dp[i][sum][weightedSum]


x[2..N] * (1, 2, ..., 2) = sum+weightedSum <= N

dp[i][sum]

*/
#include <bits/stdc++.h>
using namespace std;
int mod;
void add_self(int& a, int b) {
	a += b;
	if(a >= mod) {
		a -= mod;
	}
}
int main() { // multiplier=3      4 -> 4 +me 7 10 13 16   -me
	int n;
	cin >> n >> mod;
	vector<int> dp(n + 1);
	dp[0] = 1;
	for(int i = 2; i <= n; i++) {
		int multiplier = min(i - 2 + 1, n - i + 2);
		assert(multiplier >= 1);
		for(int sum = multiplier; sum <= n; ++sum) { // x[2..N] * (1, 2, ..., 2) <= N
			add_self(dp[sum], dp[sum-multiplier]);
			// dp[sum] = ((sum >= multiplier ? dp[i+1][sum-multiplier] : 0) + dp[i][sum]) % mod;
		}
	}
	int answer = 0;
	for(int sum = 0; sum <= n; ++sum) {
		answer = (answer + (long long) dp[sum] * (n - sum)) % mod;
	}
	cout << answer << endl;
}










Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i=a;i<b;i++)
const int MAXN = 2e5+10;
int cnt[MAXN];
typedef long long ll;
ll mex(ll arr[],ll n){
	ll h;
	fill(cnt,cnt+n+1,0);
    rep(i,0,n){
    	 cnt[arr[i]]++;
    }
    rep(i,0,n+1){
    if(!cnt[i]){
    	h=i;
    	break;
    }
   }
   return h;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);  
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ll n,a,sum=0,k,count=0;cin>>n;
    std::vector<ll> arr,arr1;
    rep(i,0,n){
    	cin>>a;
    	arr.pb(a);
    }
    if(n>1){
    sort(arr.rbegin(),arr.rend());
    arr1.pb(arr[0]);
    k=n-2;
    int i=1;
    while(k>0){
    	if(count<2){
    		arr1.pb(arr[i]);
    		count++;
    		k--;
    	}
    	else{
    		i++;
    		count=0;
    	}
    	
    }
    for(int j=0;j<arr1.size();j++){
    	sum+=arr1[j];
    }
    cout<<sum<<endl;
    }
    else{
    	cout<<0<<endl;
    }
    return 0;
}












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

using namespace std;

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

  int64_t count500 = X / 500;
  X -= 500 * count500;
  int64_t count5 = X / 5;

  int64_t answer = 1000 * count500 + 5 * count5;
  cout << answer << endl;
  return 0;
}

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

using namespace std;

typedef double D;
typedef long long int LL;

#define st first
#define nd second
#define PLL pair <LL, LL>
#define PII pair <int, int>

const int N = 1e6 + 7;
const int MX = 1e9 + 7;
const LL INF = 1LL * MX * MX;

int n, k;
set <int> C;

void no(){
	puts("-1");
	exit(0);
}

int main(){
	scanf("%d %d", &n, &k);
	if(n < k)
		no();
	
	if(k > (n + 1) / 2)
		no();
	
	k--;
	for(int i = 1; i <= n; ++i)
		C.insert(k + n + n + i);
	
	int last = n + n;
	for(int i = n; i >= 1; --i){
		if(last <= k + n)
			last = k + n + n;

		int cur = k + i + last;
		auto it = C.lower_bound(cur);

		printf("%d %d %d\n", k + i, last, *it);
		C.erase(it); last--;
	}

	return 0;
}

Measured memory_bytes: 6912
#include<cstdio>
#include<algorithm>
#include<functional>
#define NN 1000000007
using namespace std;
int main(void)
{
	int i,j,n,m;
	long long x;
	scanf("%d %d",&n,&m);
	if(n<m)	swap(n,m);
	if(n-m>1)	x=0;
	else {
		x=1;
		for(i=2;i<=n;i++)	{
			x=(x*i)%NN;
		}
		for(i=2;i<=m;i++)	{
			x=(x*i)%NN;
		}
		if(n==m)	{
			x=(x*2)%NN;
		}
	}
	printf("%lld\n",x);
	return 0;
}

Measured memory_bytes: 128
import numpy as np
import sys
import math
from collections import deque

N , M = map(int,input().split())
miti = [ [] for _ in range(N)]
for m in range(M):
    a , b = map(int , input().split())
    if b-1 != 0:
        miti[a-1].append(b-1)
    if a-1 != 0:
        miti[b-1].append(a-1)
visit = [0] * N
point = [ -1 for _ in range(N)]

def bfs():
    G = deque([0])
    visit[0] = 1
    while G:
        m = G.popleft()
        for n in miti[m]:
            if visit[n] == 0 :
                visit[n] = 1
                point[n] = m
                G.append(n)

def solve():
    bfs()
    print("Yes")
    for a in point[1::]:
        print(a+1)

if __name__ == "__main__":
    solve()



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

int main()
{
  int n,k,t;
  cin>>n>>k;
  t=n;
  vector<int> v,d(10),ans;
  while(t)
  {
    v.push_back(t%10);
    t=t/10;
  }
  reverse(v.begin(),v.end());
  for(int i=0;i<k;i++)
  {
    cin>>t;
    d[t]++;
  }
  int min1;
  for(min1=0;min1<10;min1++)
    if(d[min1]==0) break;
  for(int i=0;i<v.size();i++)
  {
    int j=v[i];
    while(d[j]!=0) j=(j+1)%10;
    //cout<<j<<"\t";
    ans.push_back(j);
    if(j!=v[i])
    {

      ans.resize(v.size(),min1);
      break;
    }
  }
  int cans=0;
  for(int i=0;i<v.size();i++) cans += (ans[i]*pow(10,v.size()-1-i));
  if(cans>=n) cout<<cans;
  else
  {
    if(min1!=0)
     {
       cout<<min1;
       int l=v.size();
       for(int i=0;i<l;i++) cout<<min1;
     }
    else
      {
        while(d[++min1]!=0);
        cout<<min1;
        for(int i=0;i<v.size();i++) cout<<0;
      }
  }
  cout<<"\n";
  return 0;
}


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

using namespace std;

const double PI = 3.1415926535897932384626433;

void Main() {
    int A, B, H, M;
    cin >> A >> B >> H >> M;
    double a = (double)A;
    double b = (double)B;
    double h = (double)H;
    double m = (double)M;

    double angle = ((60.0 * h + m) / 360.0 - m / 30.0);
    angle = abs(angle);
    while (angle > 1.0) {
        angle -= 2;
    }
    angle = abs(angle);
    double X2 = a * a + b * b - 2.0 * a * b * cos(angle * PI);
    double ans = sqrt(X2);
    cout << ans << endl;
}

int main() {
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 4232
#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;

#ifndef bhartiya
    #pragma GCC optimize("Ofast")
    #pragma GCC optimize("unroll-loops")
    // #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#endif

#define int long long
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef gp_hash_table<int, int> umap;
typedef tree<int, null_type, less<int>, rb_tree_tag,
		tree_order_statistics_node_update> oset;
// not that imp
typedef pair<pii, int> piii;
typedef vector<int> vi;
typedef vector<pii> vii;

#define inf 200000000000000
#define mod 1000000007
#define eps 1e-7
#define PI 3.1415926535897932385
// #define PI acos(-1)

#define pb push_back
#define bitc  __builtin_popcountll
#define mp make_pair
#define ff first
#define ss second
#define all(ar) ar.begin(), ar.end()
#define sz(x) (int)(x).size()

#define fr(i,a,b) for (int i = (a), _b = (b); i <= _b; i++)
#define rep(i,n) for (int i = 0, _n = (n); i < _n; i++)
#define repr(i,n) for (int i = n - 1; i >= 0; i--)
#define frr(i,a,b) for (int i = (a), _b = (b); i >= _b; i--)
#define foreach(it,ar) for (auto it = ar.begin(); it != ar.end(); it++)
#define fil(ar,val) memset(ar, val, sizeof(ar))

#ifdef bhartiya
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
int begtime = clock();
#define end_routine() cout << "\n\nTime elapsed: " << (clock() - begtime)*1000/CLOCKS_PER_SEC << " ms\n\n";
#else
#define endl '\n'
#define trace(...)
#define end_routine()
#endif

mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count());
inline bool equals(double a, double b) {return fabs(a - b) < 1e-9;}
int gcd(int a, int b){ return b==0 ? a : gcd(b, a%b); }
ll modpow(ll b, ll e) {
	ll ans=1; for(;e;b=b*b%mod,e/=2) if(e&1) ans=ans*b%mod; return ans;}

const int maxn = 1000005;

void solve(){
	int x; cin>>x;
	cout<<3*x*x;
}

signed main() 
{ 
	ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0), cout.precision(10); //cout<<fixed;
    cin.exceptions(cin.failbit);
    #ifdef bhartiya
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    solve();
    end_routine();
}

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

int main(int argc, char const *argv[])
{
    long long n, k;
    cin >> n >> k;
    if (k == 1 || n == k)
    {
        cout << 0;
        return 0;
    }
    set<long long> vals;
    if (n > k)
    {
        n %= k;
        vals.insert(n);
    }
    while (true)
    {
        n = abs(n - k);
        //cout << "n is :" << n << endl;
        if (vals.find(n) == vals.end())
            vals.insert(n);
        else
        {
            cout << *vals.begin();
            break;
        }
    }
    return 0;
}


Measured memory_bytes: 256