akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for (int i = 1; i < (int)(n); i++)
template<class T> bool chmin(T &a, T b) {if(a>b) {a=b;return 1;}return 0;}
using namespace std;
using vint = vector<int>;
using vvint = vector<vector<int>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<int,int>;
const ll inf = 1e18;
const int mod = 1e5;
const int MAX = 1e6;

int main() {
    string s; cin >> s;
    if (s[0] != 'A') {cout << "WA" << endl; return 0;}
    int ct = 0;
    for (int i = 2; i < s.size()-1; i++) if (s[i] == 'C') ct++;
    if (ct != 1) {cout << "WA" << endl; return 0;}
    rep(i,s.size()) {
        if (s[i] != 'A' && s[i] != 'C') {
            if (s[i] - 'A' <= 25) {cout << "WA" << endl; return 0;}
        }
    }
    cout << "AC" << endl;
}

Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define debug(x) cerr << #x << ": " << x << endl;
#define debug2(x, y) debug(x) debug(y);
#define repn(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) for(int i = 0; i < (int)(a); i++)
#define all(v) v.begin(), v.end() 
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define sq(x) ((x) * (x))

template<class T> T gcd(T a, T b){ return ((b == 0) ? a : gcd(b, a % b)); }

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	int n;
	cin >> n;
	vi h(n), cur(n, 0);
	rep(i, n) cin >> h[i];
	int ans = 0;
	while(true){
		int nm = 0;
		rep(i, n){
			if(cur[i] < h[i]){
				cur[i]++;
				nm++;
			}
			else{
				if(nm) ans++;
				nm = 0;
			}
		}
		if(nm) ans++;
		int f1 = 1;
		rep(i, n) if(cur[i] != h[i]){
			f1 = 0;
			break;
		}
		if(f1) break;
	}
	cout << ans << endl;
	return 0;
}
/*
Things to look out for:
	- Integer overflows
	- Array bounds
	- Special cases
Be careful!
*/


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

using namespace std;
typedef long long ll;

int main()
{
    int n;
    cin >> n;
    vector<ll> a(n);
    ll sum = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        sum += a[i];
    }
    vector<ll> ans(n);
    int index = 1;
    int cnt = 0;
    ll temp = sum;
    while (cnt < n / 2)
    {
        temp -= 2 * a[index];
        cnt++;
        index += 2;
        index %= n;
    }
    ans[0] = temp;
    for (int i = 1; i < n; i++)
    {
        ans[i] = 2 * a[i - 1] - ans[i - 1];
    }
    for (int i = 0; i < n; i++)
    {
        cout << ans[i] << endl;
    }
    return 0;
}

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

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

/*-------------------------------------------*/

int n,x,y;
vector<int> e[100009];
bool visited[100009];

int dfs(int m){
    visited[m]=true;
    int re=0,cnt=0;
    rep(i,e[m].size()){
        if(!visited[e[m][i]]){
            cnt++;
            re^=dfs(e[m][i])+1;
        }
    }
    return re;
}

int main(){
    cin>>n;
    rep(i,n-1){
        cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    cout<<(dfs(1)?"Alice\n":"Bob\n");
}

Measured memory_bytes: 10496
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define MOD 1000000007
#define INF (1<<30)
#define LINF (1LL<<60)
#define endl "\n"
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define Flag(x) (1<<(x))
#define Flagcount(x) __builtin_popcount(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
typedef unsigned long long int ull;
typedef long long lint;
 
int main(void){
  lint N,ans=0,check=0;
  cin >> N;
  lint A[N];
  rep(i,N) cin >> A[i];
  if(A[0]!=0) cout << "-1" << endl;
  else{
    for(int i=1;i<N;i++){
      if(A[i]==1 || A[i]-A[i-1]==1) ans++;
      else ans+=A[i];
      if(A[i]-A[i-1]>=2){
        check=1;
        break;
      }
    }
    if(check==0) cout << ans << endl;
    else cout << "-1" << endl;
  }
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define SIZE 100005
#define MAX 20

int N;
ll dp[1 << MAX];
ll POW[SIZE];


int main(){

	POW[0] = 1;
	for(int i = 1; i < SIZE; i++){

		POW[i] = POW[i-1]*2;
		POW[i] %= MOD;
	}

	scanf("%d",&N);

	for(int i = 0; i < POW[MAX]; i++){

		dp[i] = 0;
	}

	int tmp;
	for(int loop = 0; loop < N; loop++){

		scanf("%d",&tmp);
		dp[tmp] += 1;
	}

	for(int loop = 0; loop < MAX; loop++){
		for(int state = POW[MAX]-1; state >= 0; state--){
			if((state & (1 << loop)) == 0){
				//自分を含む集合の個数を求める
				dp[state] += dp[state+POW[loop]];
			}
		}
	}

	ll ans = POW[N]-1;
	ll minus = 0;

	//全体から、少なくとも1つ以上の桁が1である集合を除く
	for(int i = 1; i < POW[MAX]; i++){
		int count = 0;
		for(int loop = 0; loop < MAX; loop++){
			if(i & (1 << loop))count++;
		}

		if(count%2 == 1){

			minus += (POW[dp[i]]-1);
			minus %= MOD;
		}else{

			minus -= (POW[dp[i]]-1);
			if(minus < 0){
				minus += MOD;
			}
		}
	}

	ans -= minus;
	if(ans < 0){

		ans += MOD;
	}

	printf("%lld\n",ans);

	return 0;
}



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

using namespace std;

int main(){
 int n,h,w; 
  cin >> n >> h >> w;
 
  int res=0;
  int a,b;
  for(int i=0;i<n;i++){
   cin >> a>> b;
   if(a>=h&&b>=w) res++;
  }
  cout << res << endl;
}

Measured memory_bytes: 256
// http://ir5.hatenablog.com/entry/20131221/1387557630
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <utility>
#include <cmath>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define DEBUG(x) cerr << #x << " = " << x << endl
typedef pair<double, double> P;
typedef pair<int, int> IP;
double norm(P a, P b) {
  double x = a.first - b.first;
  double y = a.second - b.second;
  return sqrt(x*x + y*y);
}
int main() {
  int N; cin >> N;
  vector<P> p(N);
  REP(i,N) {
    double x, y; cin >> x >> y;
    p[i] = make_pair(x, y);
  }
  double xmin = p[0].first, ymin = p[0].second;
  REP(i,N) {
    xmin = min(xmin, p[i].first);
    ymin = min(ymin, p[i].second);
  }
  REP(i,N) {
    p[i].first -= xmin;
    p[i].second -= ymin;
  }
  // std::rand is often used.
  random_shuffle(p.begin(), p.end());
  double delta = norm(p[0], p[1]);
  multimap<IP, int> S;
  S.insert(make_pair(IP(p[0].first / delta, p[0].second / delta), 0));
  S.insert(make_pair(IP(p[1].first / delta, p[1].second / delta), 1));
  for(int i = 2; i < N; ++i) {
    IP ip(p[i].first / delta, p[i].second / delta);
    bool update = false;
    for(int dx = -1; dx <= 1; ++dx) for(int dy = -1; dy <= 1; ++dy) {
      int count = S.count(IP(ip.first + dx, ip.second + dy));
      auto it = S.find(IP(ip.first + dx, ip.second + dy));
      for(int j = 0; j < count; ++j) {
        double d2 = norm(p[i], p[it->second]);
        if(delta > d2) {
          delta = d2;
          update = true;
        }
        ++it;
      }
    }
    if(update) {
      S.clear();
      for(int j = 0; j <= i; ++j) {
        S.insert(make_pair(IP(p[j].first / delta, p[j].second / delta), j));
      }
    }
    else {
      S.insert(make_pair(ip, i));
    }
  }
  cout.setf(ios::fixed);
  cout.precision(6);
  cout << delta << endl;
}

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

using namespace std;

int n, cnt[1005], in[1005], out[1005], par[1005], ta, tb, tc, td;
bool o[1005];

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

int main() {
	scanf("%d%d", &n, &ta);
	for (int i = 0; i < 1005; i++)
		par[i] = i;
	while (n--) {
		scanf("%d%d%d%d", &ta, &tb, &tc, &td);
		if (tc == 0)
			ta = 500 + ta;
		else
			ta = 500 - tc;
		if (td == 0)
			tb = 500 - tb;
		else
			tb = 500 + td;
		if (find(ta) != find(tb))
			par[par[ta]] = par[tb];
		out[ta]++;
		in[tb]++;
	}
	for (int i = 0; i < 1005; i++)
		if (in[i] * out[i] == 0 || in[i] != out[i])
			o[i] = o[find(i)] = 1;
	for (int i = 0; i < 1005; i++)
		if ((i > 500 && out[i] < in[i]) || (i < 500 && out[i] > in[i]) || !o[find(i)]) {
			printf("NO\n");
			return 0;
		}
	printf("YES\n");
	return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#include <unordered_map>
#define inputarr(a,n) for(ll i=0;i<n;i++) cin>>a[i];
#define prllarr(a,n) for(ll i=0;i<n;i++) cout<<a[i]<<" ";
#define pb push_back
#define ll long long
#define mod 1000000007
#define foi ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0);
#define in(n) scanf("%lld",&n);
#define in2(x,y) scanf("%lld %lld",&(x),&(y));
#define in3(x,y,z) scanf("%lld %lld %lld",&(x),&(y),&(z));
#define out(n) printf("%lld\n",n);
#define out2(x,y) printf("%lld %lld\n",x,y);
#define test(t)  ll t; in(t);while(t--)
#define set(arr,n,s) for(ll i=0;i<n;i++){arr[i]=s;}

ll power(ll x,ll y,ll p){ll res=1;x=x%p;while(y>0){if(y&1){res=(res*x)%p;} y=y>>1;x=(x*x)%p;}return res;}
ll modInverse(ll a,ll p){return power(a,p-2,p);}//used with feemat little

ll gcd(ll x,ll y){if(x==0 || y==0){return max(y,x);}return gcd(y%x,x);}
ll gcdExtended(ll a,ll b,ll &x,ll &y){if(a==0){x=0;y=1;return b;}ll x1,y1;ll gcd = gcdExtended(b%a,a,x1,y1);x=y1-(b/a)*x1;y=x1;return gcd;}//o(log(b))
;
ll arr[403];
ll dp[405][405];
int main()
{
	ll n;
	in(n)
	for(ll i=1;i<=n;i++){
		in(arr[i])
	}
	arr[0]=0;
	for(ll i=1;i<=n;i++){
		arr[i]+=arr[i-1];
	}

	for(ll i=0;i<=400;i++){
		for(ll j=0;j<=400;j++){
			dp[i][j]=1e18;
		}
	}
	for(ll i=1;i<=n;i++){
		dp[i][i]=0;
	}
	for(ll len=2;len<=n;len++){
		for(ll i=1;i<=n;i++){
			ll end=i+len-1;
			if(end>n)break;
			for(ll k=i;k<end;k++){
				dp[i][end]=min(dp[i][k]+dp[k+1][end]+arr[end]-arr[i-1],dp[i][end]);
			}
		}
	}
	// for(ll i=0;i<=n;i++){
	// 	for(ll j=0;j<=n;j++){
	// 		cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
	// 	}
	// }
	cout<<dp[1][n]<<endl;

}
/*error-----
convert every int to long long eg-1LL
create array with proper analysis of problem constrain
check mod also
*/






Measured memory_bytes: 1536
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node
{
    int b,kk,t[201];
}s[12001];
int n,k,xb,tot,ans,mod=1e9+7,a[201],c[201],d[201];
pair<int,int>dp[12001];
bool operator < (const node &a,const node &b)
{
    for (register int i=1;i<n;i++)
      if (a.t[i]<b.t[i])
	    return 1;else
	  if (a.t[i]>b.t[i]) 
	    return 0;
    return 0; 
}
inline long long read()
{
   long long sum=0,x=1;
   char ch=getchar();
   while (ch<'0'||ch>'9')
   {
       if (ch=='-')
	     x=-1;
	   ch=getchar();
   }
   while (ch>='0'&&ch<='9')
   {
   	   sum=sum*10+ch-'0';
	   ch=getchar();
   }
   return sum*x;
}
inline void write(long long x)
{
    if (x<0)
	{
        putchar('-');
        x=-x;
    }
    if (x>9)
      write(x/10);
    putchar(x%10+'0');
    return;
}
inline bool check(node x,node y)
{
    for (int i=1;i<n;i++)
      if (x.t[i]!=y.t[i])
	    return 0;
    return 1;   
}
inline int maxpop(int x,int y)
{
    if (x==-1)
	  return 0;
    int s=0;
    for (int i=60;i>=0;i--)
      if (((x>>i)&1)==((y>>i)&1))
	    s+=((x>>i)&1);else
	  {
	      ++s;
		  break;
	  }
    return s;  
}
inline int dpp()
{
    sort(dp+1,dp+1+tot);
    int s=0,l=0,r=-1;
    for (register int i=1;i<=tot;++i)
    {
        if (dp[i].first>r)
		{
		    s+=(r-l+1);
			l=dp[i].first;
		}
        r=dp[i].second;
    }
    s+=(r-l+1);
    return s;  
}
signed main()
{
    n=read();k=read();
    for (register int i=1;i<=n;++i)
      a[i]=read();
    sort(a+1,a+1+n);    
    for (register int i=0;i<=60;++i)
    {
        for (register int j=1;j<=n;++j)
          c[j]=(a[j]&((1ll<<i)-1));   
        sort(c+1,c+1+n);
        c[0]=-1;
        int sz=unique(c+1,c+n+1)-c-1;
        for (register int j=1;j<=sz;j++)
          if (a[1]>=c[j])
          {
            int P=maxpop(c[j-1],c[j]);
            for (register int l=1;l<=n;++l)
              d[l]=((a[l]-c[j])>>i);  
            s[++xb].b=d[1];s[xb].kk=i+P;
            for (register int l=1;l<n;++l)
              s[xb].t[l]=d[l+1]-d[l];        
          }
    }
    sort(s+1,s+1+xb);
    for (register int i=1;i<=xb;++i)
    {
        if (i!=1&&!check(s[i],s[i-1]))
        {
        	ans=(ans+dpp())%mod;
		    tot=0;
		}  
        if (s[i].kk<=k)
		  dp[++tot]=make_pair(max(s[i].b-k+s[i].kk,0ll),s[i].b);
    }
    ans=(ans+dpp())%mod;
    write(ans);
    return 0;
}

Measured memory_bytes: 18712
#include<set>
#include<map>
#include<deque>
#include<queue>
#include<stack>
#include<cmath>
#include<ctime>
#include<bitset>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<complex>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;

const int maxn = 1100;

ll n,a,b,c,d,u;

int main()
{
	scanf("%lld%lld%lld%lld%lld",&n,&a,&b,&c,&d);
	u=b-a;
	ll l=0,r=0,L=c*(n-1ll),R=d*(n-1ll);
	for(int i=n;i>=0;i--)
	{
		if(L+l<=u&&u<=R+r) { puts("YES");return 0; }
		L-=c,R-=d;
		l-=d,r-=c;
	}
	puts("NO");
	
	return 0;
}


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

int n, a, num[100001] = {}, large = 0, two = 0, ans = 0;

int main(){
	cin >> n;

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

		if (num[a] == 3){
			num[a] = 1;
		}

		if (a > large){
			large = a;
		}
	}

	for (int i = 1; i <= large; i++){
		if (num[i] > 0){
			ans++;
		}

		if (num[i] == 2){
			two++;
		}
	}

	ans -= two % 2;

	cout << ans;

	return 0;
}

Measured memory_bytes: 640
/**
 * Created by hiramekun at 20:55 on 2019-09-07.
 */
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using vb = vector<bool>;
using P = pair<ll, ll>;
template<typename T> using pq = priority_queue<T>;
template<typename T> using minpq = priority_queue<T, vector<T>, greater<T>>;
template<typename T, typename K> using ump = unordered_map<T, K>;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll e5 = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = ll(n - 1); i >= 0; i--)
#define each(i, mp) for(auto& i:mp)
#define eb emplace_back
#define F first
#define S second
#define all(obj) (obj).begin(), (obj).end()

template<class T>
ostream &operator<<(ostream &out, const vector<T> &list) {
    ll n = list.size();
    rep(i, n) out << list[i] << ' ';
    return out;
}

template<class T>
istream &operator>>(istream &in, vector<T> &list) {
    ll n = list.size();
    rep(i, n) in >> list[i];
    return in;
}

template<class T>
ostream &operator<<(ostream &out, const vector<vector<T>> &list) {
    ll n = list.size();
    rep(i, n) out << list[i] << '\n';
    return out;
}

/* ------------- ANSWER ------------- */
/* ---------------------------------- */

void solve() {
    ll n;
    cin >> n;
    vl b(n - 1);
    cin >> b;
    ll ans = b[0];
    rep(i, n - 2) {
        ans += min(b[i], b[i + 1]);
    }
    ans += b.back();
    cout << ans << '\n';
}

int main() {
#ifdef MY_DEBUG
    while (true) {
#endif
        solve();
#ifdef MY_DEBUG
    }
#endif
    return 0;
}

Measured memory_bytes: 256
a, b, c = sorted(map(int,input().split()))
cnt = 0
while a!=b or b!=c:
  if a != c and b != c:
    a += 1
    b += 1
  elif a == c+1:
    c += 1
    b += 1
  elif b == c and a != c:
    a += 2
  cnt += 1
print(cnt)

Measured memory_bytes: 3064
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
using namespace std;
#define INF 100000000
#define MAXH 10
#define MAXW 10

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

int h, w, c;
int p[MAXH][MAXW], buf[MAXH][MAXW];
int ret = 0;
int hairetu[4] = {1, 1, 1, 1};

void dfs(int cur) {
    if (cur == 4) {
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                buf[i][j] = p[i][j];
            }
        }
        for (int i = 0; i < 5; i++) {
            bool done[MAXH][MAXW] = {false};
            int color; 
            if (i < 4) color = hairetu[i];
            else color = c;
            int origin = buf[0][0];
            queue<int> X;
            queue<int> Y;
            X.push(0); Y.push(0);
            while (!X.empty()) {
                int x = X.front(); X.pop();
                int y = Y.front(); Y.pop();
                done[y][x] = true;
                buf[y][x] = color;
                for (int j = 0; j < 4; j++) {
                    int nx = x + dx[j];
                    int ny = y + dy[j];
                    if (0 <= nx && nx < w && 0 <= ny && ny < h && buf[ny][nx] == origin && !done[ny][nx]) {
                        X.push(nx); Y.push(ny);
                    }
                }
            }
        }
        // 連続している島で一番大きい物を探す
        bool done[MAXH][MAXW] = {false};
        for (int j = 0; j < h; j++) {
            for (int k = 0; k < w; k++) {
                if (buf[j][k] == c && !done[j][k]) {
                    int ans = 0;
                    queue<int> X; queue<int> Y;
                    X.push(k); Y.push(j);
                    while (!X.empty()) {
                        int x = X.front(); X.pop();
                        int y = Y.front(); Y.pop();
                        ans++;
                        done[y][x] = true;
                        for (int l = 0; l < 4; l++) {
                            int nx = x + dx[l];
                            int ny = y + dy[l];
                            if (0 <= nx && nx < w && 0 <= ny && ny < h && !done[ny][nx] && buf[ny][nx] == c) {
                                X.push(nx); Y.push(ny);
                                done[ny][nx] = true;
                            }
                        }
                    }
                    ret = max(ret, ans);
                }
            }
        }
        return;
    }
    for (int i = 1; i <= 6; i++) {
        hairetu[cur] = i;
        dfs(cur+1);
    }
}


int main(void) {
    while (1) {
        cin >> h >> w >> c;
        if (h == 0 && w == 0 && c == 0) break;
        ret = 0;
        for (int i = 0; i < 4; i++) hairetu[i] = 1;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cin >> p[i][j];
            }
        }
        dfs(0);
        cout << ret << endl;
    }
    return 0;
}

Measured memory_bytes: 1260
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <fstream>
#include <sstream>

using namespace std;

int main(){
    int N,W;
    cin >> N >> W;
    
    vector<vector<int> > wv(N,vector<int>(2,0));
    for(int i=0; i<N; i++){
        cin >> wv[i][0] >> wv[i][1];
    }

    vector<long long> dp(W+1,0);
    vector<vector<int > > item(W+1,vector<int>(N,0));
    long long ans=0;
    for(int i=0; i<W; i++){
        for(int j=0; j<item[i].size(); j++){
            if(item[i][j]==1)continue;
            int w = wv[j][0];
            int v = wv[j][1];
            if(i+w<=W && dp[i]+v>dp[i+w]){
                dp[i+w]=dp[i]+v;
                item[i+w]=item[i];
                item[i+w][j]=1;
                if(ans<dp[i+w])ans=dp[i+w];
            }
        }
    }
    cout << ans << endl;
}

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

template <class T> T* serchL(T* begin, T* end, T num) {
	T *p = begin;
	for (; p < end;p++) {
		if (&p >= num) {
			return p;
		}
	}

	return NULL;
}

int main() {
	ios::sync_with_stdio(false);
	string S;
	int N, K;
	cin >> N >> S >> K;
	
	char c = S.at(K-1);
	for (auto&i:S) {
		if (i != c) {
			i = '*';
		}
	}

	cout << S<<"\n";

	return 0;
}


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

typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> PLL;
typedef pair<P,P> PP;
typedef vector<ll> llVEC;
typedef vector<P> PVEC;
typedef priority_queue<P,PVEC,greater<P> > PPQ;
typedef priority_queue<ll, llVEC, greater<ll> > llPQ;

#define rep(i,a,n) for(ll i = a;i < n;i++)
#define rrep(i,a,n) for(ll i = n-1; i >= a;i--)
#define index_check(i,n) if(i > n-1 || i < 0) continue;
#define LINF (ll)1e18
#define INF (int)1e9
#define fs first
#define sc second

template<typename T>
ll sz(vector<T> &vec){ return (ll)vec.size(); }
ll sz(string &s){ return (ll)s.size(); }

ll gcd(ll a,ll b){ return ((!b) ?a :gcd(b, a%b)); }

int main(){
    ll N,W;
    cin >> N >> W;
    ll v[N],w[N];
    vector<ll> vec[4];

    rep(i,0,N){
        cin >> w[i] >> v[i];
        vec[w[i] - w[0]].push_back(v[i]);
    }

    rep(i,0,4) sort(vec[i].begin(),vec[i].end(),greater<ll>());
    rep(i,0,4) rep(j,1,sz(vec[i])) vec[i][j] += vec[i][j-1];

    ll ans = 0,temp = 0;
    rep(i,0,sz(vec[0])+1){
        rep(j,0,sz(vec[1])+1){
            rep(k,0,sz(vec[2])+1){ 
                rep(l,0,sz(vec[3])+1){
                    if((i+j+k+l)*w[0]+(j+2*k+3*l) > W) break;
                    temp = 0;
                    if(i > 0) temp += vec[0][i-1];
                    if(j > 0) temp += vec[1][j-1];
                    if(k > 0) temp += vec[2][k-1];
                    if(l > 0) temp += vec[3][l-1];
                    ans = max(ans,temp); 
                }
            }
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3580
#include <bits/stdc++.h>
using namespace std;
int main(){
	long long int a, b, c;
	cin >> a >> b >> c;
	if(((c - a - b) >= 0) && (((c - a - b) * (c - a - b) - 4 * a * b) > 0)){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}
}

Measured memory_bytes: 256
#include<stdio.h>
#define N 100
#define M 2000000
  
int main()
{
  
  int n,p[N],m[N][N];
  int i,j,k,l,q;
  
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d%d",&p[i],&j);
  }

  p[n] = j;;
  for(i=1;i<=n;i++)
    m[i][i] = 0;
  
  for(l=2;l<=n;l++) {
	for(i=1;i<=n-l+1;i++){
	  
      j = i + l - 1;
      m[i][j] = M;
	  
      for(k=i;k<=j-1;k++) {
		q = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j];
        
		if(m[i][j] > q)
		  m[i][j] = q;
	  }
    }
  }
  printf("%d\n",m[1][n]);
  
  return 0;
}

Measured memory_bytes: 636
#include <bits/stdc++.h>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

const ll MOD=1e9+7;
const ll INF=1e18;

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

int main(){
    string a, b; cin>>a>>b;
    string c=a+b;
    int n=stoi(c);
    for(int i=1; i<=1000; i++){
        if(n==i*i){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define all(v) ((v).begin()),((v).end())
#define fast_IO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define PI 3.14159265358979323
typedef long long ll;
const int INF = 1e9+5;
ll MOD(ll ans, ll m)
{
    return (ans % m + m) % m;
}
/*ll dp(int i)
{
    if(i >= n-1)
    {
        return 0;
    }
    if(mem[i] != -1)
        return mem[i];
    ll p1 = 0, p2 = 0;
    //if(i+1 <= n-1)
    p1 = abs( a[i] - a[i+1] ) + dp(i+1);
    //if(i+2 <= n-1)
    p2 = abs( a[i] - a[i+2] ) + dp(i+2);
    return mem[i] = min(p1,p2);
}*/
int main()
{
    fast_IO;
    int n;
    cin>>n;
    vector<int> h(n);
    for(int i=0; i<n; i++)
    {
        cin>>h[i];
    }
    vector<int> dp(n,INF);
    dp[0] = 0;
    for(int i=0;i<n;i++)
    {
        for(int j = i+1 ; j <= i+2 ; j++)
        {
            if(j < n)
            {
                dp[j] = min(dp[j] , dp[i] + abs(h[i]-h[j]));
            }
        }
    }
    cout<<dp[n-1]<<endl;
}


Measured memory_bytes: 1024
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) {
        MyScanner sc = new MyScanner();
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        int n = sc.nextInt();
        long [] a = new long[3 * n];
        for (int i = 0; i < 3 * n; i++) a[i] = sc.nextLong();
        long [] p = new long[3 * n];
        long [] m = new long[3 * n];
        PriorityQueue<Long> pq = new PriorityQueue<>();
        long cur = 0;
        for (int i = 0; i < 3 * n; i++) {
            cur += a[i];
            pq.add(a[i]);
            if (pq.size() > n) {
                cur -= pq.poll();
            }
            if (pq.size() >= n) p[i] = cur;
        }
        pq = new PriorityQueue<>(Comparator.reverseOrder());
        cur = 0;
        for (int i = 3 * n - 1; i >= 0; i--) {
            cur += a[i];
            pq.add(a[i]);
            if (pq.size() > n) {
                cur -= pq.poll();
            }
            if (pq.size() >= n) m[i] = cur;
        }
        long res = Long.MIN_VALUE;
        for (int i = n - 1; i < 2 * n; i++) res = Math.max(res, p[i] - m[i + 1]);
        out.println(res);
        out.close();
    }


    //-----------MyScanner class for faster input----------
    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        public MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }


    }

}

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

int main()
{
  int n;
  cin >> n;
  string d[n];
  for(int i = 0; i < n; i++)
    cin >> d[i];
  bool seq[1001];
  fill(seq,seq+1001,true);
  for(int i = 0; i < n; i++){
    for(int j = i; j < i+3 && j < n; j++){
      string str = "";
      for(int k = i; k <= j; k++){
        str += d[k];
        seq[atoi(str.c_str())] = false;
      }
    }
  }
  for(int i = 0;;i++){
    if(seq[i]){
      cout << i << endl;
      break;
    }
  }
}

Measured memory_bytes: 1272
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
int main(){
    ll n,k;
    cin >> n >> k;
    int a[n];
    vector<int> t(n,0);
    vector<int> s(n,0);
    for(int i = 0;i < n;i++)cin >> a[i];
    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            if(j > i && a[i] > a[j])t[i]++;
            if(a[i] > a[j])s[i]++;
        }
    }
    ll tsum,ssum;
    tsum = ssum = 0;
    for(int i = 0;i < n;i++){
        tsum += t[i];
        ssum += s[i];
        tsum %= MOD;
        ssum %= MOD;
    }
    //cout << tsum << ssum << endl;
    tsum *= k;
    tsum %= MOD;
    ll K = (k*(k-1)/2) % MOD;
    ssum *= K;
    ssum %= MOD;
    ll ans = tsum + ssum;
    ans %= MOD;
    cout << ans << endl;
    //cin >> n;
}

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

int get(int n,int number)
{
	int las = number / pow(10,n-1);
	return las % 10;
}
bool check(int number)
{
	for (int i = 0; i < 2; i++)
	{
		if (get(i + 1, number) != get(5 - i, number))
		{
			return false;
		}
	}
	return true;
}
int A, B,num=0;
int main()
{
	cin >> A >> B;
	for (int i = A; i <= B; i++)
	{
		if (check(i))
		{
			num++;
		}
	}
	cout << num;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
    int n;
    int i;
    int num;
    int max=0,min=0;

    while(~scanf("%d",&n)){
        int no = 0;
        max = min = 0;
        for(i = 0; i < n; i++){
            scanf("%d",&num);
            if(num > max){
                max = min = num;
            }else if(num < min){
                min = num;
            }

            if(max - min > 1) no = 1;
        }

        printf("%s\n",no?"No":"Yes");
    }
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
#define sz(s) (int)(s).size() 
 
using namespace std;
const int hell = 1e9+7;

void solve(){
	int n , a ;
	cin >> n >> a;
	cout << max(n-2*a,0ll) << endl;	
}
 
int32_t main(){                                    
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    	cout.precision(10);
    	cout << fixed;
#ifdef LOCAL
    freopen("input.txt", "rt", stdin);
    freopen("output.txt","w",stdout);
#endif
        int q=1;
        //cin>>q;
        while(q--){
            solve();
        }
               
#ifdef LOCAL
    cout << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
 
	return 0;
}	
 

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

using namespace std;

using int64 = long long;
const int mod = 1e9 + 7;
//const int mod = 998244353;

const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;


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

template< typename T1, typename T2 >
istream &operator>>(istream &is, pair< T1, T2 > &p) {
  is >> p.first >> p.second;
  return is;
}

template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) {
  for(int i = 0; i < (int) v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
  for(T &in : v) is >> in;
  return is;
}

template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

template< typename T = int64 >
vector< T > make_v(size_t a) {
  return vector< T >(a);
}

template< typename T, typename... Ts >
auto make_v(size_t a, Ts... ts) {
  return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));
}

template< typename T, typename V >
typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {
  t = v;
}

template< typename T, typename V >
typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {
  for(auto &e : t) fill_v(e, v);
}

template< typename F >
struct FixPoint : F {
  FixPoint(F &&f) : F(forward< F >(f)) {}

  template< typename... Args >
  decltype(auto) operator()(Args &&... args) const {
    return F::operator()(*this, forward< Args >(args)...);
  }
};

template< typename F >
inline decltype(auto) MFP(F &&f) {
  return FixPoint< F >{forward< F >(f)};
}


int main() {
  int D, T, S;
  cin >> D >> T >> S;
  if(S * T >= D) cout << "Yes\n";
  else cout << "No\n";
}


Measured memory_bytes: 3648
<?php
  list($n) = explode(" ", trim(fgets(STDIN)));

  $a = array_map('intval', explode(" ", trim(fgets(STDIN))));

  $x = [];
  $y = [];
  for($i=0;$i<$n;$i++){
    if($i%2==0){
      if(!isset($x[$a[$i]])) $x[$a[$i]]=0;
      $x[$a[$i]]++;
    }else{
      if(!isset($y[$a[$i]])) $y[$a[$i]]=0;
      $y[$a[$i]]++;
    }
  }

  arsort($x);
  arsort($y);

  $x1=[];
  $y1=[];

  foreach($x as $k => $c){
    if(count($x1)>=2){
      break;
    }
    $x1[]=[$k,$c];
  }
  foreach($y as $k => $c){
    if(count($y1)>=2){
      break;
    }
    $y1[]=[$k,$c];
  }

  if($x1[0][0]==$y1[0][0]){
    echo $n-max($x1[0][1]+$y1[1][1], $x1[1][1]+$y1[0][1]);
  }else{
    echo $n-($x1[0][1]+$y1[0][1]);
  }

Measured memory_bytes: 28740
/* ****mittal**** */
#include<bits/stdc++.h>
#define ll          long long int 
#define pb          push_back
#define endl        '\n'
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define jell        998244353
#define rep(i,a,b)    for(ll int i=a;i<b;i++)
#define repr(i,a,b)   for(ll int i=a;i>=b;i--)
#define lbnd    lower_bound
#define ubnd        upper_bound
#define mp          make_pair
#define DEC(N)  cout << std::fixed; cout << setprecision(N);
using namespace std;
ll add(ll x,ll y)
{
return (x%hell+y%hell)%hell;
}
ll mul(ll x,ll y)
{
return ((x%hell)*(y%hell))%hell;
}
ll sub(ll x,ll y)
{
return (x-y+hell)%hell;
}
#define N  100005
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int TESTS=1;
//    cin>>TESTS;
    while(TESTS--)
    {
        ll n,m;
        cin>>n>>m;
        ll a[n+2];
        ll sum=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            sum+=a[i];
        }
        ll x=0;
        for(int i=1;i<=n;i++)
        {
           if(a[i]*4*m>=(sum))
              x++;
        }
        if(x>=m)
            cout<<"Yes";
        else
            cout<<"No";
    }
    return 0;
}

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

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

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF 1e16
#define mod 1000000007

vector<int> construct_sa(const string& S){
  vector<int> SA, ranks, tmp;
  int N = S.length();

  SA.resize(N + 1);
  ranks.resize(N + 1);
  tmp.resize(N + 1);

  for(int i = 0; i <= N; i++){
    SA[i] = i;
    ranks[i] = (i < N ? S[i] : -1);
  }

  for(int k = 1; k <= N; k *= 2){
    auto f = [&](const int& a,const int& b){
      if(ranks[a] != ranks[b]) return ranks[a] < ranks[b];
      else{
        int ra = (a + k <= N ? ranks[a + k] : -1);
        int rb = (b + k <= N ? ranks[b + k] : -1);
        return ra < rb;
      }
    };

    sort(SA.begin(), SA.end(), f);

    tmp[SA[0]] = 0;
    for(int i = 1; i <= N; i++){
      tmp[SA[i]] = tmp[SA[i-1]] + (f(SA[i-1], SA[i]) ? 1 : 0);
    }
    for(int i = 0; i <= N; i++){
      ranks[i] = tmp[i];
    }
  }
  return SA;
}

string calcmns(const string& S,bool f,char mnc){
  int N=S.size();
  if(!f){
    vector<int> SA=construct_sa(S);
    rep(i,SA.size()){
      if(SA[i]<=N/2){
        return S.substr(SA[i],N/2);
      }
    }
  }else{
    ll k=N/2 - 1;
    while(k>=0&&S[k]==mnc)k--;
    return S.substr(k+1,N/2);
  }
  return "~";
}

string calcU(const string& S){
  string T=S;
  reverse(all(T));
  return S+T;
}

int N,K;
string S;
char mnc='~';

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

  cin>>N>>K>>S;
  rep(i,N)minch(mnc,S[i]);
  K=min(K,14);

  if(K==1){
    cout<<calcmns(calcU(S),false,mnc)<<endl;
    return 0;
  }

  string res="~";
  repl(i,N-1,2*N){
    if(S[2*N-1-i]==mnc){
      string crtS=S;
      rep(j,K-1){
        string crtU=calcU(crtS);
        int k;
        if(j>0){
          k=N;
          while(k<2*N&&crtU[k]==mnc)k++;
        }else{
          k=i+1;
        }
        crtS=crtU.substr(k-N,N);
      }
      minch(res,calcmns(calcU(crtS),true,mnc));
    }
  }
  cout<<res<<endl;

  return 0;
}


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

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

    // 3個, 2個, 1個の皿の個数に対してそこからの期待値を保存
    double dp[N+1][N+1][N+1] = {};
    // 意味のある皿を選んだ時, 推移確率から期待値を計算
    // 意味のある皿を選べるまでの回数の期待値を足す
    for (int i = 0; i <= N; ++i) {
        for (int j = 0; i + j <= N; ++j) {
            for (int k = 0; i + j + k <= N; ++k) {
                int dish = i + j + k;
                double &x = dp[i][j][k];
                if(dish == 0) continue;
                if(k) x += dp[i][j][k-1] * k; // (k / dish) の確率
                if(j) x += dp[i][j-1][k+1] * j; // (j / dish) の確率
                if(i) x += dp[i-1][j+1][k] * i; // (i / dish) の確率
                x += N; // 意味のある皿を選べるまでの回数の期待値 (N / dish)
                x /= dish;
            }
        }
    }

    vector<int>c(4, 0);
    for (int i = 0; i < N; ++i) {
        c[a[i]]++;
    }
    cout << setprecision(20) << dp[c[3]][c[2]][c[1]];
    return 0;
}

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

using namespace std;

using ll = long long;

int main() {
  int a, b;
  cin >> a >> b;
  if (a * b == 15)
    cout << "*" << endl;
  else if (a + b == 15)
    cout << "+" << endl;
  else
    cout << "x" << endl;
}

Measured memory_bytes: 256
N, M = list(map(int, input().split(' ')))
r = [ None for i in range(N) ]

illegal = False
for i in range(M):
  s, c = list(map(int, input().split(' ')))
  if r[s-1] is not None and r[s-1] != c:
    illegal = True
    break
  r[s-1] = c

v = -1
if not illegal:
  for i in range(N):
    if r[i] is None:
      if i == 0 and N != 1:
        r[i] = 1
      else:
        r[i] = 0
  v = sum(r[i] * 10**(N-1-i) for i in range(N))
  if v < 10**(N-1) and not (N == 1 and v == 0):
    v = -1

print(v)

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

using namespace std;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 1LL<<60;

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

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; }

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

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

  int N;
  cin >> N;
  ll ans = 0;

  for(ll i = 1; i <= N; i++){
    if(i%3!=0 && i%5!=0){
      ans += i;
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3648
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long; 
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
//constexpr long long MOD = 998244353LL;
template<class T, class U> inline bool chmax(T &a, U b) { if (a < b) { a = b; return true;} return false; }
template<class T, class U> inline bool chmin(T &a, U b) { if (a > b) { a = b; return true;} return false; }
const ll INF = (ll)1e18 + 1;
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int k; cin >> k;
    
    if(k%2==0) cout << k/2 * k/2 << ln;
    else cout << k/2 * (k/2+1) << ln;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
#define repr(i,a,b) for (int i=a; i<b; i++)
#define rep(i,n) for (int i=0; i<  n; i++)
 
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; }
 
const long long INF = 1LL << 60;
#define PI 3.14159265359 
 
template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
    vector.erase(vector.begin() + index);
}
 
int gcd(int a, int b){
    if(b == 0) return a;
    else return gcd(b, a%b);
}
 
long long lcm (int a, int b){
    return  (long long) a*b /gcd(a,b);
}


int main(){
    int N;
    map<string, long long> S;

    cin >> N;

    rep(i,N){
        string s;
        cin >> s;

        sort(s.begin(),s.end());
        S[s]++;
    }

    long long ans =0;
    for(auto a :S){
        ans += (a.second *(a.second-1))/2;
    }
    cout << ans << endl;

}

Measured memory_bytes: 11272
import heapq
N,M=map(int,input().split())
if M==N-1:
    print(0)
    exit()
if N<2*(N-M-1):
    print("Impossible")
    exit()
a=[int(i) for i in input().split()]
x=[0 for i in range(M)]
y=[0 for i in range(M)]
for i in range(M):
    x[i],y[i]=map(int,input().split())
par=[0 for i in range(N)]
rnk=[0 for i in range(N)]
def init(n):
    for i in range(N):
        par[i]=i
        rnk[i]=0
def find(x):
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
def unite(x,y):
    x=find(x)
    y=find(y)
    if x==y:
        return
    if (rnk[x]<rnk[y]):
        par[x]=y
    else:
        par[y]=x
        if(rnk[x]==rnk[y]):
            rnk[x]+=1
def same(x,y):
    return find(x)==find(y)
init(N)
for i in range(M):
    unite(x[i],y[i])
A=[find(i) for i in range(N)]
K=0
D=dict()
for i in range(N):
    if A[i] in D:
        D[A[i]].append((a[i],i))
    else:
        D[A[i]]=[(a[i],i)]
        K+=1
ans=0
used=[0 for i in range(N)]
for i in D:
    seq=min(D[i])
    ans+=seq[0]
    used[seq[1]]=1
q=[]
for i in range(N):
    if used[i]==0:
        heapq.heappush(q,(a[i],i))
for _ in range(2*(N-M-1)-K):
    s,t=heapq.heappop(q)
    ans+=s
print(ans)


Measured memory_bytes: 40228
using System;
using System.Collections.Generic;
class Program{
	static void Main(){
		int n=int.Parse(Console.ReadLine());
		int[] a=Array.ConvertAll(Console.ReadLine().Split(),int.Parse);
		int[] b=Array.ConvertAll(Console.ReadLine().Split(),int.Parse);
		int[] m=new int[n+1];
		Dictionary<int,int>[] hs=new Dictionary<int,int>[29];
		long ans=0;
		for(int i=0;i<29;i++){
			hs[i]=new Dictionary<int,int>();
			for(int j=0;j<n;j++){m[j]=b[j]%(1<<(i+1));}
			m[n]=int.MaxValue;
			Array.Sort(m);
			long t=(long)Math.Pow(2,i),o=0;
			for(int j=0;j<n;j++){
				int q=a[j]%(1<<(i+1));
				if(hs[i].ContainsKey(q)){o+=hs[i][q];}
				else{
					int[] h=new int[4];
					for(int k=1;k<=4;k++){
						int lb=-1,ub=n,mid=0;
						while(ub-lb>1){
							mid=(ub+lb)/2;
							if(m[mid]+q>t*k-(1)){ub=mid;}
							else{lb=mid;}
						}
						h[k-1]=ub;
					}
					hs[i].Add(q,h[1]-h[0]+h[3]-h[2]);
					o+=h[1]-h[0]+h[3]-h[2];
				}
			}
			ans|=(o%2)<<i;
		}
		Console.WriteLine("{0}",ans);
	}
}

Measured memory_bytes: 112092
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rep2(i,s,f) for(int i=s;i<f;i++)
#define INF 1000000000000000000
#define MOD 1000000007
typedef pair<int, int> P;

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; }

bool prime(int n) {
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0)return false;
    }
    return n != 1;
}
int gcd(int x, int y) {
    if (y == 0)return x;
    return gcd(y, x % y);
}
int lcm(int x, int y) {
    return x / gcd(x, y) * y;
}
int mod_pow(int n, int p, int m) {
    if (p == 0) return 1;
    if (p % 2 == 0) {
        int t = mod_pow(n, p / 2, m);
        return (t * t) % m;
    }
    return n * mod_pow(n, p - 1, m) % m;
}
int extGCD(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = extGCD(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
int modinv(int a, int m) {
    int b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
int digit(int x) {
    int cnt = 0;
    while (x > 0) {
        cnt += x % 10;
        x /= 10;
    }
    return cnt;
}
int read() {
    int tmp;
    cin >> tmp;
    return tmp;
}
int xor128() {
    static int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    int t = (x xor (x << 11));
    x = y; y = z; z = w;
    return (w = (w xor (w >> 19)) xor (t xor (t >> 8)));
}
map<int, int> factaring(int x) {
    map<int, int>ans;
    int now = 2;
    while (now * now <= x) {
        if (x % now == 0) {
            x /= now;
            ans[now]++;
        }
        else now++;
    }
    if (x != 1) ans[x]++;
    return ans;
}
int comb(int n, int k) {
    k = min(k, n - k);
    int x = 1, y = 1;
    rep(i, k) {
        y *= i + 1;
        y %= MOD;
    }
    for (int i = n - k + 1; i <= n; i++) {
        x *= i;
        x %= MOD;
    }
    return x * modinv(y, MOD) % MOD;
}

int n, m;
int a[100005];
int sum[100005];
int ans = 0;
int shakecnt = 0;

bool binary_search(int x) {
    int cnt = 0;
    rep(i, n) {
        int nokori = x - a[i];
        cnt += (a + n) - lower_bound(a, a + n, nokori);
    }
    return cnt >= m;
}

signed main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> n >> m;
    rep(i, n) cin >> a[i];
    sort(a, a + n);

    int ok = 0, ng = 200001;
    while ((ng - ok) > 1) {
        int mid = (ok + ng) / 2;
        if (binary_search(mid)) {
            ok = mid;
        }
        else ng = mid;
    }
    //cerr << ok << endl;

    sum[0] = 0;
    rep(i, n) sum[i + 1] = sum[i] + a[i];
    rep(i, n) {
        shakecnt += (a + n) - lower_bound(a, a + n, ok - a[i]);
        ans += (sum[n] - sum[lower_bound(a, a + n, ok - a[i]) - a]) + a[i] * ((a + n) - lower_bound(a, a + n, ok - a[i]));
    }
    ans -= (shakecnt - m) * ok;
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
long long int arr[1000000],brr[1000000];
long long int p[1000000],q[1000000];

int main(){
    long long int i,j,n,m,l,r,mid,d,x=0,mi=-1,k;
    cin>>n>>m>>k;
  for(i=1;i<=n;i++){
    cin>>arr[i];
  }
  for(i=1;i<=m;i++){
    cin>>brr[i];
  }
  p[1]=arr[1];
  for(i=2;i<=n;i++){
    p[i]=p[i-1]+arr[i];
  }
  q[1]=brr[1];
   for(i=2;i<=m;i++){
    q[i]=q[i-1]+brr[i];
  }
  for(i=0;i<=n;i++){
    d=k-p[i];
    //cout<<d<<endl;
    if(d<0)
      break;
    l=1,r=m;
    long long int ans=0;
    while(l<=r){
      mid=(l+r)/2;
      if(q[mid]<=d){
        ans=mid;
        l=mid+1;
      }
      else
        r=mid-1;
    }
   //cout<<i<<" "<<r<<endl;
    //cout<<i<<" "<<l<<endl;
    x=i+ans;
   // cout<<i<<"*"<<endl;
    //cout<<x<<" "<<l<<endl;
    if(x>mi)
      mi=x;
  }
    cout<<mi<<endl;
  mi=-1;
}


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

using namespace std;

#define REP(a, b, c) for (register int a = b, _n = c; a <= _n; ++a)
#define DREP(a, b, c) for (register int a = b, _n = c; a >= _n; --a)
#define FOR(a, b, c) for (register int a = b, _n = c; a < _n; ++a)
#define DFOR(a, b, c) for (register int a = b, _n = c; a > _n; --a)
#define EREP(a, b) for (register int a = first[b]; ~a; a = edge[a].nxt)
#define GREP(a, b) for (register int& a = cur[b]; ~a; a = edge[a].nxt)

int n;
int h[100005];

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

    REP (i, 1, n) {
        scanf ("%d", h + i);
        if (h[i] > h[i - 1]) --h[i];
        if (h[i] < h[i - 1]) {
            puts("No");
            return 0;
        }
    }
    puts("Yes");
    return 0;
}


Measured memory_bytes: 640