akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class AtCoderB
{
    static void Main()
    {
        var sc = new Scanner();

        int n = sc.NextInt();
        int m = sc.NextInt();
        int[] a = sc.IntArray();

        a = a.OrderByDescending(i => i).ToArray();
        int sum = a.Sum();
        for (int i = 0; i < m; i++)
        {
            if (a[i] * 4 * m < sum)
            {
                Console.WriteLine("No");
                return;
            }
        }

        Console.WriteLine("Yes");
    }

    class Scanner
    {
        private string[] _line;
        private int _index;
        private const char Separator = ' ';

        public Scanner()
        {
            _line = new string[0];
            _index = 0;
        }

        public string Next()
        {
            while (_index >= _line.Length)
            {
                _line = Console.ReadLine().Split(Separator);
                _index = 0;
            }

            return _line[_index++];
        }

        public int NextInt() => int.Parse(Next());
        public long NextLong() => long.Parse(Next());
        public double NextDouble() => double.Parse(Next());
        public decimal NextDecimal() => decimal.Parse(Next());
        public char NextChar() => Next()[0];
        public char[] NextCharArray() => Next().ToCharArray();

        public string[] Array()
        {
            _line = Console.ReadLine().Split(Separator);
            _index = _line.Length;
            return _line;
        }

        public int[] IntArray() => Array().Select(int.Parse).ToArray();
        public long[] LongArray() => Array().Select(long.Parse).ToArray();
        public double[] DoubleArray() => Array().Select(double.Parse).ToArray();
        public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray();
    }
}

Measured memory_bytes: 13396
#include<iostream>
using namespace std;
int p[300001],p2[300001];
int main(){
	int ssssssss,minv=0x7FFFFFF;
	cin>>ssssssss;
	string s;
	cin>>s;
	for(int i=1;i<s.size();i++)
		p[i]=p[i-1]+(s[i-1]=='W');
	minv=p[s.size()-1];
	for(int j=s.size()-2;j>=0;j--)
		p2[j]=p2[j+1]+(s[j+1]=='E'),minv=min(minv,p[j]+p2[j]);
	cout<<minv;
	return 0;
}

Measured memory_bytes: 2948
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define dbg(x) cerr << #x << " = " << x << endl
#define _ << ' ' <<
using namespace std;
using ll = long long;
using vi = vector<int>;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a[3];
    for (int i = 0; i < 3; ++i)
        cin >> a[i];
    sort(a, a + 3);
    if (a[0] == 5 && a[1] == 5 && a[2] == 7)
        cout << "YES";
    else
        cout << "NO";
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	string s;
  	cin>>s;
  	int sum=0;
  	for(int i=0;i<s.size();i++){
     	sum+=int(s[i]-'0')%9;
      	sum=sum%9;
    }
  	if(!sum%9)cout<<"Yes"<<endl;
  	else cout<<"No";
  
}

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

int main() {
  ll N, X, M;
  cin >> N >> X >> M;
  if (X == 0) {
    cout << X << endl;
    return 0;
  }

  vector<ll> S(M + 1, 0);
  vector<ll> T(M + 1, 0);
  S.at(X) = 1;
  T.at(1) = X;

  ll i = 2;

  bool loop = false;
  ll l, r;
  while (i <= N) {
    X = (X * X) % M;
    T.at(i) = T.at(i - 1) + X;
    if (S.at(X) > 0) {
      l = S.at(X) - 1;
      r = i - 1;
      loop = true;
      break;
    } else {
      S.at(X) = i;
    }
    i++;
  }
  ll ans = T.at(i - 1);

  if (loop) {
    ll dx = r - l;
    ll dy = T.at(r) - T.at(l);
    ans += dy * ((N - r) / dx);
    ans += T.at(l + (N - r) % dx) - T.at(l);
  }

  cout << ans << endl;
}


Measured memory_bytes: 4828
#include <iostream>
#include <iomanip>
#include <string>
#include <string.h>
#include <math.h>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <deque>
#include <queue>

#define rep(i, n) for(int i = 0; i < n; ++i)
#define REP(i, m, n) for(int i = m; i < n; ++i)
#define rrep(i,n) for(int i = n; i >= 0; --i)
#define RREP(i, m, n) for(int i = n; i >= m; --i)

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

using namespace std;

const long long MOD = 1000000007;

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

	int n;
	string s;
	cin >> n >> s;
	int** sum;
	sum = new int*[n];
	
	sum[0] = new int[26];
	memset(sum[0], 0, sizeof(int) * 26);
	++sum[0][s[0] - 'a'];
	REP(i, 1, n) {
		sum[i] = new int[26];

		rep(j, 26) sum[i][j] = sum[i - 1][j];
		++sum[i][s[i] - 'a'];
	}

	int q;
	cin >> q;
	vector<pair<int, char>> query1;
	vector<pair<int, pii>> query2;
	rep(i, q) {
		int type;
		cin >> type;
		if (type == 1) {
			int i;
			char c;
			cin >> i >> c;
			query1.push_back(pair<int, char>(i-1, c));
		}
		else {
			int l, r;
			cin >> l >> r;
			query2.push_back(pair<int, pii>(query1.size(), pii(l-1, r-1)));
		}
	}

	map<int, char> que;
	int t = 0;
	int num[26] = { 0 };
	rep(i, query2.size()) {
		int l = query2[i].second.first, r = query2[i].second.second;
		rep(j, 26) {
			if (l != 0) {
				num[j] = sum[r][j] - sum[l - 1][j];
			}
			else {
				num[j] = sum[r][j];
			}
		}

		REP(j, t, query2[i].first) {
			que[query1[j].first] = query1[j].second;
		}
		t = query2[i].first;

		auto endq = que.upper_bound(r);
		for (auto p = que.lower_bound(l); p != endq; ++p) {
			--num[s[(*p).first] - 'a'];
			++num[(*p).second - 'a'];
		}

		int ans = 0;
		rep(j, 26) {
			if (num[j] != 0) ++ans;
		}

		cout << ans << "\n";
	}

	return 0;
}


Measured memory_bytes: 60828
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define REP(i,j) for(int i=0;i<j;i++)
#define FORN(i,j,k) for(int i=j;i<k;i++)
#define vi vector<int>
#define vvi vector<vi >
#define pii pair<int,int>
#define vpii vector<pii >
using namespace std;
int main(void){
	string s;
	cin>>s;
	int n=s.size();
	REP(i,n){
		if(s[i]=='?')s[i]='D';
	}
	cout<<s;
	return 0;
}

Measured memory_bytes: 3720
N = int(input())

result = [0]*4

for _ in range(N):
    S = input()
    if S == 'AC':
        result[0] += 1
    elif S == 'WA':
        result[1] += 1
    elif S == 'TLE':
        result[2] += 1
    else:
        result[3] += 1

print('AC x',result[0])
print('WA x',result[1])
print('TLE x',result[2])
print('RE x',result[3])


Measured memory_bytes: 9204
#include <stdio.h>

int main(void){

  int n;
  int i;
  int count = 0;

  scanf("%d", &n);

  int p[n];

  for(i = 0; i < n; i++){
    scanf("%d", &p[i]);
  }

  for(i = 1; i < n - 1; i++){
    if(p[i] >= p[i - 1] && p[i] < p[i + 1]){
      count += 1;
    }
    if(p[i] < p[i - 1] && p[i] >= p[i + 1]){
      count += 1;
    }
  }

  printf("%d\n", count);

  return 0;
}


Measured memory_bytes: 128
/*...........................
.........tank.jpg............
...........................*/

//PointBlank's code (⌐■_■)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
 
ll power(ll x, ll y); 
#define repp(I, A, B) for(int I = A; I <= B; I++)
#define rep(I, A, B) for(int I = A; I < B; I++)
#define rrep(I, B, A) for(int I = B; I >= A; I--)
#define pb emplace_back
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define LB lower_bound
#define UB upper_bound
#define MP make_pair
#define quickio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define debug(this) cerr<<"> "<<#this<<" : "<<this<<"\n"
#define bitcount(n) __builtin_popcountll(n)
#define in_edges(M) repp(I, 1, M){int A, B; cin >> A >> B; v[A].pb(B), v[B].pb(A);}
#define in_dedges(M) repp(I, 1, M){int A, B; cin >> A >> B; v[A].pb(B);}
#define in_wedges(M) repp(I, 1, M){int A, B, C; cin >> A >> B >> C; v[A].pb(B, C), v[B].pb(A, C);}
#define in_dwedges(M) repp(I, 1, M){int A, B, C; cin >> A >> B >> C; v[A].pb(B, C);}
#define endl "\n"

const ll MOD = 1e9 + 7;
const ll INF = 1e18 + 18;
const int inf = 2e9;

const int N = 2e6 + 6;
vector<int> v[N];
bool vis[N];

void dfs(int s){
    vis[s] = 1;
    for(auto i : v[s]) if(!vis[i]) dfs(i);
}
int main() //PointBlank's code ¯\_(ツ)_/¯
{
    quickio
    int n, m;
    cin >> n >> m;
    in_edges(m);

    int res = -1;
    repp(i, 1, n){
        if(!vis[i]){
            dfs(i);
            res++;
        }
    }
    cout << res;
}

ll power(ll x, ll y){ 
    ll res = 1; x %= MOD;
    while(y > 0){if(y & 1) res = (res*x) % MOD; y = y>>1, x = (x*x) % MOD;} 
    return res; 
}

Measured memory_bytes: 54212
#include<stdio.h>

int main(void) {
    int n;
    int tmp;
    int i;
    int min;
    int max;
    scanf("%d %d", &n, &tmp);
    min = tmp;
    max = tmp;
    for ( i = 1; i < n; i++ ) {
        scanf("%d", &tmp);
        if ( max < tmp ) {
            max  = tmp;
        } else if ( min > tmp ) {
            min = tmp;
        }
    }
    printf("%d\n", max - min);
    return 0; 
}

Measured memory_bytes: 128
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
	int n,m;
	string s[110],t[110];
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>s[i];
	}
	cin>>m;
	for(int i=0;i<m;i++){
		cin>>t[i];
	}
	int ans=0;
	for(int i=0;i<n;i++){
		int res=0;
		for(int j=0;j<n;j++){
			if(s[i]==s[j])res++;
		}
		for(int j=0;j<m;j++){
			if(s[i]==t[j])res--;
		}
		if(res>ans)ans=res;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 888
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
const ll INF = 1e18;
const int MOD = 1000000007;
#define rep(i,n) for(int i=0;i<n;i++)
 
int main() {
  ll h,w;
  cin >> h >> w;
  ll ans = INF;
  ll res,s1,s2,s3;
  for(ll i=1;i<h;i++){
     s1 = w*i;
    if(w%2 == 0){
      s2 = (h-i)*(w/2);
      res = abs(s1-s2);
    }else if((h-i)%2 == 0){
      s2 = w*((h-i)/2);
      res = abs(s1-s2);
    }else{
      if(w < h-i){
        s2 = w*((h-i)/2);
        s3 = w*(((h-i)/2)+1);
        res = max(s1,s3)-min(s1,s2);
      }else{
        s2 = (h-i)*(w/2);
        s3 = (h-i)*((w/2)+1);
        res = max(s1,s3)-min(s1,s2);
      }
    }
    ans = min(ans,res);
  }
  for(ll i=1;i<w;i++){
    ll s1 = h*i;
    if(h%2 == 0){
      ll s2 = (w-i)*(h/2);
      res = abs(s1-s2);
    }else if((w-i)%2 == 0){
      ll s2 = h*((w-i)/2);
      res = abs(s1-s2);
    }else{
      if(h < w-i){
        ll s2 = h*((w-i)/2);
        ll s3 = h*(((w-i)/2)+1);
        res = max(s1,s3)-min(s1,s2);
      }else{
        ll s2 = (w-i)*(h/2);
        ll s3 = (w-i)*((h/2)+1);
        res = max(s1,s3)-min(s1,s2);
      }
    }
    ans = min(ans,res);
  }
  cout << ans << endl;    
    
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <queue>
#include <set>
#include <map>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <bitset>
using namespace std;
  
const double EPS = 1e-9;

int check(int &a, int &m){
	int x = 1;
	int cnt = 0;
	do{
		cnt++;
		x = (a*x)%m;
	}while(x != 1);
	return cnt;
}

int getGCD(int m, int n){
	if(n == 0){
		return m;
	}
	return getGCD(n, m%n);
}
  
int main(){
	int x, y, z;
	int a1, m1, a2, m2, a3, m3;
	while(cin >> a1 >> m1 >> a2 >> m2 >> a3 >> m3, a1){
		long long cntx = 0, cnty = 0, cntz = 0;
		cntx = check(a1, m1);
		cnty = check(a2, m2);
		cntz = check(a3, m3);

		if(cntx < cnty){
			swap(cntx, cnty);
		}
		long long LCMxy, LCM;
		LCMxy = cntx*cnty/getGCD(cntx, cnty);
		if(LCMxy < cntz){
			swap(LCMxy, cntz);
		}
		LCM = LCMxy*cntz/getGCD(LCMxy, cntz);
		cout << LCM << endl;
	}
  
    return 0;
}

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

int main(void) 
{
   int h, w, k;
   cin >> h >> w >> k;

   vector<string> c(h);
   rep(i,h) cin >> c[i];

   int ans = 0;
   rep(hi, 1 << h)
   {
        vector<string> target = c;
        rep(hj, h){
            if(hi >> hj & 1)
            {
                //選択
                target[hj] ="------";
            }
        }
        rep(wi, 1 << w)
        {
            vector<string>target2 = target;
            int sum = 0;
            rep(wj, w)
            {
                if(wi >> wj & 1)
                {
                    rep(x,h) target2[x][wj] = '-';
                }
            }
             rep(ii, h) rep(jj, w) 
            {
            if(target2[ii][jj] == '#') sum++;
            }
            if(sum == k) ans ++;
        }
    }
    cout << ans << endl;
}

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

//#include<vector>
//#include<iterator>
//#include<utility>
//#include<algorithm>
//#include<cmath>
using namespace std;


#define ll long long
#define fr(m) for(int i=0; i<m; i++)
#define frj(m) for(int j=0; j<m; j++)
#define frr(n) for(int i=n; i>=0; i--)
#define pb push_back
#define orr ||
#define nl \n
#define sci(n) scanf("%lld ", &n)
#define pri(n) printf("%d", n)
#define prl(n) printf("%lld", n)
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl

bool compare(ll a, ll b){
    return(a>b);
}

int main()
{

    ll n;
    cin>>n;
    ll arr[n];
    fr(n) cin>>arr[i];
    ll maxi=*max_element(arr,arr+n),mini=*min_element(arr,arr+n),current,sum=0,ans=INT_MAX;
//    cout<<maxi<<" "<<mini<<endl;
    ll a=-100;
    fr(201){
        sum=0;
        current=a++;

        frj(n){
            sum+=(abs(arr[j]-current)*abs(arr[j]-current));
        }
//        cout<<sum<<" "<<current;
         ans=min(ans,sum);
    }
    cout<<ans<<endl;
    return 0;
}


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

#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rep2(i,s,n) for(int i = (s); i < (n); ++i)
#define ll long long
#define ld long double
#define P pair<ll,ll>
#define all(v) v.begin(),v.end()

const ll mod = 1e9+7;
const ll INF = 1e18;
const double pi = acos(-1.0);

int main(void)
{
    ll n,c,k; cin>>n>>c>>k;
    vector<ll> t(n);
    rep(i,n) cin>>t[i];

    ll ans=0;

    sort(all(t));

    for(int i=0;i<n;){
        ll start = i;
        while(i<n && t[i] - t[start] <= k && i - start < c) ++i;
        ++ans;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3984
#define _CRT_SECURE_NO_WARNINGS
#define ANS_NUM (3)

#ifdef _____MY_DEBUG_____
#define VS_ENDPAUSE()	(system("pause"))
#else
#define VS_ENDPAUSE()
#endif

#include <stdio.h>
#include <iostream>
#include <math.h>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;
typedef signed char int8;
typedef signed short int16;
typedef signed int int32;
typedef signed long long int64;
typedef unsigned char uint8;
typedef unsigned short uint16;
typedef unsigned int uint32;
typedef unsigned long long uint64;


#if ANS_NUM == 3
struct Obj{
	uint32 val;
	uint32 length;
	bool operator<(const Obj& o) const{
		return val < o.val;
	}
};

void func(void)
{
	uint32 n;
	uint64 k;
	uint32 a, b;

	Obj top = {0};

	(void)scanf("%d %llu", &n, &k);
	vector<Obj> objs(n);
	for(uint32 i=0; i<n; i++){
		(void)scanf("%d %d", &a, &b);
		// add value
		objs[i].val = a;
		objs[i].length = b;
	}

	sort(objs.begin(), objs.end());
	uint64 l = 0;
	uint32 objK;
	for(objK=0; objK<n; objK++){
		if(k <= l + objs[objK].length){
			break;
		}
		l += objs[objK].length;
	}
	printf("%d\n", objs[objK].val);
}
#endif


int main(void)
{
	func();

	VS_ENDPAUSE();
	return 0;
}








#if ANS_NUM == 1
void func(void)
{
	int32 a, b, c;
	scanf("%d %d %d", &a, &b, &c);
	if((c>=a) && (c<=b)){
		printf("Yes\n");
	} else {
		printf("No\n");
	}
}
#endif

#if ANS_NUM == 2
void func(void)
{
	uint32 n, m;
	uint32 a, b;
	(void)scanf("%d %d", &n, &m);
	uint8 *ans = (uint8 *)calloc(n, sizeof(uint8));
	for(uint8 i=0; i<m; i++){
		(void)scanf("%d %d", &a, &b);
		ans[a-1]++;
		ans[b-1]++;
	}

	for(uint8 i=0; i<n; i++){
		printf("%d\n", ans[i]);
	}

	free(ans);
}
#endif



#if ANS_NUM == 4
void func(void)
{

}
#endif

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

#define int long long
#define rep(i,l,r) for(int i=(int)(l);i<(int)(r);i++)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)x.size())
template<class T>bool chmax(T &a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,T b){if(a>b){a=b;return 1;}return 0;}

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;

const int inf = 1LL<<60;
const int mod = 1e9 + 7;
const double eps = 1e-9;

/*{
  }*/

signed main(){
  int n, k;
  cin >> n >> k;

  vi p(n);
  rep(i, 0, n) cin >> p[i];

  vi q(n-1), s(n);
  rep(i, 0, n-1){
    q[i] = p[i] > p[i+1];
    s[i+1] = s[i] + q[i];
  }

  int ans = 1, flag = s[k-1] > 0;
  set<int> st;
  rep(i, 0, k) st.insert(p[i]);
  rep(i, 0, n-k){
    st.insert(p[i+k]);
    int x = *st.begin();
    int y = *st.rbegin();
    if((flag or s[i+k]-s[i+1] > 0) and (p[i] != x or p[i+k] != y)){
      if(s[i+k]-s[i+1] == 0) flag = 0;
      ans++;
    }
    st.erase(p[i]);
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 14336
n,x = map(int,input().split())
l_li = list(map(int,input().split()))

ans = 0
point = 0

for i in range(len(l_li)+1):
    if i == 0:
        ans += 1
    else:
        point = point + l_li[i-1]
        if point <= x:
            ans += 1
print(ans)

Measured memory_bytes: 3064
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st=new StringTokenizer(br.readLine());
        int H=Integer.parseInt(st.nextToken());
        int W=Integer.parseInt(st.nextToken());

        while(H!=0 || W!=0) {

            int i=0;
            int j=0;

            while(j<H) {
                if(j%2==1){
                	while(i<W) {
                        if(i%2==1){
                        	System.out.print("#");
                        }else{
                        	System.out.print(".");
                        }
                        i++;
                    }
                }else{
                	while(i<W) {
                        if(i%2==1){
                        	System.out.print(".");
                        }else{
                        	System.out.print("#");
                        }
                        i++;
                    }
                }
                System.out.println("");
                i=0;
                j++;
            }
            System.out.println("");
            StringTokenizer sa=new StringTokenizer(br.readLine());
            H=Integer.parseInt(sa.nextToken());
            W=Integer.parseInt(sa.nextToken());
        }
	}

}



Measured memory_bytes: 31072
import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int n;
		int sum;
		
		while (sc.hasNext()) {
			n = sc.nextInt();
			sum = 0;
			for (int i = 0; i < 600 / n; i++) {
				sum += n * n * n * i * i;
			}
			System.out.println(sum);
		}
	}
}

Measured memory_bytes: 12000
/*
  Vivek Rathi
  CSE 2nd Year
  MNNIT
*/
#include<bits/stdc++.h>
using namespace std;
#define M 1000000007
#define ll long long int
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define debug1(x) cout<<#x<<" "<<x<<endl;
#define debug2(x,y) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<endl;
#define debug3(x,y,z) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<" "<<#z<<" "<<z<<endl;
#define present(c,x) ((c).find(x) != (c).end())
#define null NULL
#define mp make_pair
#define fi first
#define se second
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);
#define inf 1e18
#define flush fflush(stdout);
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<ll, null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
ll modpower(ll a,ll b,ll c)
{
	ll res=1;
	while(b)
	{
		if(b&1LL)
			res=(res*a)%c;
		a=(a*a)%c;
		b>>=1;
	}
	return res;
}
//-------------------------------Template--Above------------------------------------------------


int main()
{
	boost
	ll n,m;
	cin>>n>>m;
	ll dif[n+1]={0};
	for(ll i=0;i<m;i++)
	{
		ll l,r;
		cin>>l>>r;
		if(l-1>=0)dif[l-1]+=1;
		dif[r]-=1;
	}
	ll a[n]={0},co=0;
	for(ll i=1;i<=n;i++)
	{
		a[i]=dif[i-1]+a[i-1];
		if(a[i]==m)
			co++;
	}
	cout<<co<<endl;
	return 0;
}


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

using namespace std;

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

typedef long long ll;

int c[10010];
vector<int> edge[10010];
int deg[10010];
//bool done[10010];
int ans[10010];
queue <int> q;

int main()
{
	int n;
	cin >> n;
	int a, b;
	rep(i, n-1)
	{
		cin >> a >> b;
		a--;
		b--;
		edge[a].push_back(b);
		edge[b].push_back(a);
	}
	rep(i, n) cin >> c[i];
	sort(c, c+n);
	int answer=0;
	rep(i, n-1) answer+=c[i];
	cout << answer << endl;
	rep(i, n) deg[i]=edge[i].size();
	rep(i, n)
	{
		if(deg[i]==1)
		{
			q.push(i);
			//done[i]=true;
		}
	}
	int tmp=0;
	while(!q.empty())
	{
		int v=q.front();
		q.pop();
		ans[v]=c[tmp];
		tmp++;
		rep(i, edge[v].size())
		{
			int u=edge[v][i];
			deg[u]--;
			if(deg[u]==1) q.push(u);
		}
	}
	rep(i, n)
	{
		cout << ans[i];
		if(i==n-1) cout << endl;
		else cout << ' ';
	}
	return 0;
}

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

int n, tot = 0, a[100];

inline void ck_min( int &a, int b ) { if( a > b ) a = b; }
inline void ck_max( int &a, int b ) { if( a < b ) a = b; }
 
struct tAns {
	int x, y;
} ans[200];
 
int main() 
{
	scanf( "%d", &n );
	
	for( int i = 1; i <= n; i ++ ) 
		scanf( "%d", &a[i] ); 
	
	int _min = 0, min_id;
	int _max = 0, max_id;
	for( int i = 1; i <= n; i ++ ) {
		if( a[i] < _min ) 
			_min = a[i], min_id = i;
		if( a[i] > _max ) 
			_max = a[i], max_id = i;
	}
	
	if( _min == 0 && _max == 0 ) ;
	else if( abs( _min ) < abs( _max ) )
	{
		for( int i = 1; i <= n; i ++ ) 
			if( a[i] < 0 ) a[i] += _max, ans[++tot] = ( tAns ) { max_id, i };	 
		for( int i = 2; i <= n; i ++ ) 
			a[i] += a[i-1], ans[++tot] = ( tAns ) { i-1, i };
	}
	else
	{
		for( int i = 1; i <= n; i ++ ) 
			if( a[i] > 0 ) a[i] += _min, ans[++tot] = ( tAns ) { min_id, i };  
		for( int i = n-1; i >= 1; i -- ) 
			a[i] += a[i+1], ans[++tot] = ( tAns ) { i+1, i };
	}	
	
//	for( int i = 1; i <= n; i ++ )
//		printf( "%d ", a[i] ); printf( "\n\n" );
	
	printf( "%d\n", tot );	
	for( int i = 1; i <= tot; i ++ )
		printf( "%d %d\n", ans[i].x, ans[i].y );

	return 0;
}

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

int main(){

    int X,A,B;
    cin >> X >> A >> B;

    if (B - A <= 0 ) cout << "delicious" << endl;
    else if(B - A <= X) cout << "safe" << endl;
    else cout << "dangerous" <<endl;

    return 0;
}

Measured memory_bytes: 256
// https://atcoder.jp/contests/abc092/tasks/abc092_a

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
  /* Magic word */
  cin.tie(0);
  ios::sync_with_stdio(false);
  /* ---------- */

  int a, b, c, d;

  cin >> a >> b >> c >> d;

  cout << min(a, b) + min(c, d) << '\n';
  
  return 0;
}


Measured memory_bytes: 256
s = input()
l1 = ['D','R','U']
l2 = ["D",'L','U']
count = 0

for i in s[::2]:
    if i in l1 :
        count += 1
for i in s[1::2]:
    if i in l2:
        count += 1
    
if count == len(s):
    print('Yes')
else:
    print('No')

Measured memory_bytes: 8988
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

const int MXK=100000,MXN=100;
int a[MXN+1];
int dp[2][MXK+1];
int n,k;
int solve(int i,int k){
	if( dp[i][k]!=-1 )return dp[i][k];
	dp[i][k]=0;
	for(int j=1;j<=n;j++){
		if( a[j] <= k )
		dp[i][k]|=solve(i^1,k-a[j])^1;
	}
	return dp[i][k];
}
int32_t main()
{
   IOS
   memset(dp,-1,sizeof(dp));
   cin >> n >> k ;
   for(int i=1;i<=n;i++)
   cin>>a[i];
   cout << ( solve(0,k) ? "First" : "Second"  ) << endl;
}


Measured memory_bytes: 6528
n = int(input())
dicte = {}
count = 0
for i in range(n):
    s = list(input())
    z = ''.join(sorted(s))
    if z in dicte:
        dicte[z] += 1
    else:
        dicte[z] = 1
for i in dicte.keys():
    count += ((dicte[i] * (dicte[i]-1))//2)
print(count)

Measured memory_bytes: 17804
# coding: utf-8

from collections import Counter

n, m = map(int, raw_input().split())
f = [int(flatten) for _ in range(m) for flatten in raw_input().split()]
c = Counter(f)

for i in range(1, n+1):
    if i in c:
        print c[i]
    else:
        print 0


Measured memory_bytes: 2812
fun main(args: Array<String>){
    val (N, K) = readLine()!!.split(' ').map(String::toInt)
    val A: Array<Int> = readLine()!!.split(' ').map(String::toInt).toTypedArray()
    var size = A.size
    var counter = 0

    while (size > 0){
        size -= K - 1
        if (counter == 0){
            size -= 1
        }
        counter ++
        if (size <= 0) println(counter)
    }
}

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

int main() {
    int N;  cin >> N;
    map<int, int> mp;
    for (int i = 0; i < N; ++i) {
        int a;  cin >> a;
        ++mp[a];  ++mp[a - 1];  ++mp[a + 1];
    }
    int ans = 0;
    for (auto e : mp) {
        ans = max(ans, e.second);
    }
    cout << ans << endl;
}


Measured memory_bytes: 4736
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using u32 = uint32_t;
using vi = vector<int>;    using vvi = vector<vi>;
using vb = vector<bool>;   using vvb = vector<vb>;
using vl = vector<ll>;     using vvl = vector<vl>;
using vd = vector<double>; using vvd = vector<vd>;

#define MAXC(c, x) (c = max(c, x))
#define MINC(c, x) (c = min(c, x))

#define REP(i,n) for(auto i = 0 * (n), i##_len = (n); i < i##_len; ++i)
#define ALL(c) (c).begin(), (c).end()
#define FOR(i,s,n) for(ll i=s, i##_len=(ll)(n); i<i##_len; ++i)
#define TEN(x) ((ll)1e##x)
const ll mod = TEN(9) + 7;

const ll INF = 1e9;
using ull = unsigned long long;

// 制約fを満たす最大値（最小値）の二分探索
// ok < ng なら最大値，ok > ng なら最小値探索になる
template<typename F> ll bsearch(ll ok, ll ng, F f) {
	while (abs(ok - ng) > 1) {
		ll middle = (ok + ng) / 2;
		(f(middle) ? ok : ng) = middle;
	}
	return ok;
}


int main() {
	#ifdef INPUT_FROM_FILE
	ifstream cin("sample.in");
	ofstream cout("sample.out");
	#endif
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(50);
	ll n, k; cin >> n >> k;
	vl a(n); REP(i, n) cin >> a[i];
	struct P {
		ll num = 0;
		vl l, r;
	};
	function<P(ll, ll)> recur = [&](ll l, ll r) {
		if (l == r) {
			P p; 
			p.num = a[l] >= k;
			p.l = { a[l] - k };
			p.r = { a[l] - k };
			return p;
		}
		ll c = (r + l) / 2;
		auto lhs = recur(l, c);
		auto rhs = recur(c + 1, r);
		P p;
		p.num = lhs.num + rhs.num;
		p.l = std::move(lhs.l);
		ll pl = p.l.size();
		REP(i, rhs.l.size()) p.l.push_back(p.l[pl-1] + rhs.l[i]);
		p.r = std::move(rhs.r);
		ll pr = p.r.size();
		REP(i, lhs.r.size()) p.r.push_back(p.r[pr-1] + lhs.r[i]);

		sort(ALL(rhs.l));
		REP(i, lhs.r.size()) p.num += rhs.l.end() - lower_bound(ALL(rhs.l), -lhs.r[i]);

		return p;
	};
	auto ans = recur(0, n - 1);
	cout << ans.num << endl;
	
	return 0;
}


Measured memory_bytes: 8476
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

s = ns()
n = len(s)

lastw = 0
ans = 0
for i in range(n - 1, -1, -1):
    if s[i] == 'W':
        lastw = max(lastw, i)
    else:
        ans += max(0, lastw - i)
        lastw = max(0, lastw - 1)

print(ans)

Measured memory_bytes: 3628
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def ll():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def onem():
	return int(input())
def s(x):
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x):
	return " ".join(map(str,x))

h,w = m()

l = []

for i in range(h):
	a = ll()
	l.append(a)

dp = [[0 for i in range(w+1)] for j in range(h+1)]

for i in range(h):
	for j in range(w):
		if l[i][j] == 0:
			dp[i+1][j+1] = min(dp[i+1][j],dp[i][j+1],dp[i][j]) + 1
print(max(map(max,dp))**2)






Measured memory_bytes: 56228
using System;
using System.Linq;
using System.Collections.Generic;

class Program
{
    public static void Main()
    {
        string s = Console.ReadLine();
        bool flag = false;

        if (s[0] != 'h')
        {
            flag = true;
        }
        for (int i = 1; i < s.Length; i++)
        {
            if (s[i] == 'i')
            {
                if (s[i - 1] != 'h')
                {
                    flag = true;
                }
            } else if (s[i] == 'h')
            {
                if (s[i - 1] != 'i')
                {
                    flag = true;
                }
            } else
            {
                flag = true;
            }
        }
        if (s.Length % 2 == 1)
        {
            flag = true;
        }

        if (flag)
        {
            Console.WriteLine("No");
        } else
        {
            Console.WriteLine("Yes");
        }
    }
}

Measured memory_bytes: 13140
sstr=list(input())
sf=[sstr[0],sstr[1]]
sb=[sstr[2],sstr[3]]
if sf[0]=="0":
  sf.pop(0)
if sb[0]=="0":
  sb.pop(0)
fws="".join(sf)
bks="".join(sb)
fwb=[int(n) for n in fws]
bkb=[int(n) for n in bks]
if len(fwb)==2:
    fw=(fwb[0]*10)+(fwb[1])
else:
    fw=fwb[0]
if len(bkb)==2:
    bk=(bkb[0]*10)+(bkb[1])
else:
    bk=bkb[0]
if 1<=fw<=12:
  if 1<=bk<=12:
    print("AMBIGUOUS")
  else:
    print("MMYY")
else:
  if 1<=bk<=12:
    print("YYMM")
  else:
    print("NA")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int k,n,a[200005],cnt[200005]; 
int main() {
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) {
		scanf("%d",a+i);
		cnt[a[i]]++;
	}
	sort(cnt+1,cnt+1+n);
	int i;
	for(i=1;i<=n;i++) if (cnt[i]!=0) break;
//	cerr<<i<<endl;
	int ans=0;
	for(;i<=n-k;i++) ans+=cnt[i];
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 1792
# H * W の行列をする
H, W = map(int, input().split())
field = [list(input()) for i in range(H)] 
count = 0

for i in range(H):
    for j in range(W):
        # 注目している点が#でその上下左右が#でないときにcountが加算される
        # このcountが1以上になると、#が孤立していることになり、Noが出力される
        if (i == 0 and j == 0) or (i == H-1 and j == 0) or (i == 0 and j == W-1) or (i == H-1 and j == W-1):
            pass
        elif i == 0:
            if field[i][j] == '#' and field[i][j-1] != '#' and field[i][j+1] != '#' and field[i+1][j] != '#':
                count += 1
        elif i == H-1:
            if field[i][j] == '#' and field[i][j-1] != '#' and field[i][j+1] != '#' and field[i-1][j] != '#':
                count += 1
        elif j == 0:
            if field[i][j] == '#' and field[i][j-1] != '#' and field[i][j+1] != '#' and field[i+1][j] != '#':
                count += 1
        elif j == W-1:
            if field[i][j] == '#' and field[i][j-1] != '#' and field[i+1][j] != '#' and field[i-1][j] != '#':
                count += 1
        elif field[i][j] == '#' and field[i][j-1] != '#' and field[i][j+1] != '#' and field[i+1][j] != '#' and field[i-1][j] != '#':
            count += 1
print('No' if count>=1 else 'Yes')

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

using namespace std;

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

  int p = 0;
  int q = 0;
  for (int i = 0; i < n; ++i) {
    int tmp;
    cin >> tmp;
    p = p * 10 + tmp;
  }
  for (int i = 0; i < n; ++i) {
    int tmp;
    cin >> tmp;
    q = q * 10 + tmp;
  }

  vector<int> vec1;
  vector<int> vec2(n);
  for (int i = 0; i < n; ++i)
    vec2[i] = i + 1;

  do {
    int tmp = 0;
    for (auto &v : vec2)
      tmp = tmp * 10 + v;
    vec1.push_back(tmp);
  } while (next_permutation(vec2.begin(), vec2.end()));

  sort(vec1.begin(), vec1.end());

  int idxp = 0;
  int idxq = 0;
  for (int i = 0; i < static_cast<int>(vec1.size()); ++i) {
    if (vec1[i] == p)
      idxp = i;
    if (vec1[i] == q)
      idxq = i;
  }

  cout << abs(idxp - idxq) << endl;
}

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

int main() {
  int H, W;
  cin >> H >> W;
  vector<string> vec(H);
  
  for(int i = 0; i < W+2 ; i++){
    cout << "#";
  }
  cout << endl;
  
  
  for (int i = 0; i < H ; i++){
       cin >> vec.at(i);
        
  }
  for(int j = 0; j < H; j++){
        cout << '#' << vec.at(j) << '#' << endl;
  }
  
  for(int i = 0; i < W+2 ; i++){
    cout << "#";
  }
    
    
}




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

ll mod = 998244353;
ll modpow(ll a, ll n){
    ll res = 1;
    while(n > 0){
        if(n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
ll com(ll a, ll b){
	ll res = 1;
	b = min(b, a-b);
	ll n = b;
	for(int i=0; i<n; i++){
    	res *= a;
    	if(res >= mod) res %= mod;
    	res *= modpow(b, mod-2);
    	if(res >= mod) res %= mod;
    	a--;
    	b--;
    }
	return res;
}

int main(){
	int n, m, k;
	cin >> n >> m >> k;
	ll ans = 0;
	vector<ll> ss(k+1);
	ss.at(0) = com(n-1, 0);
	for(int i=1; i<=k; i++){
		ss.at(i) = ss.at(i-1);
		if(ss.at(i) >= 998244353) ss.at(i) %= 998244353;
		ss.at(i) *= n-i;
		if(ss.at(i) >= 998244353) ss.at(i) %= 998244353;
		ss.at(i) *= modpow(i, mod-2);
		if(ss.at(i) >= 998244353) ss.at(i) %= 998244353;
	}
	rep(i, k+1){
		ll l;
		l = m*modpow(m-1, n-1-i);
		if(l >= 998244353) l %= 998244353;
//		cout << l << endl;
		l *= ss.at(i);
//		cout << l << endl;
		if(l >= 998244353) l %= 998244353;
		ans += l;
		if(ans >= 998244353) ans %= 998244353;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 4752
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int mmax=1e6+10;
ll book[100];
int main()
{
	ll n;
	while(cin>>n)
	{
		ll num=0;
		for(int i=1;i<=n;i++)
		{
			ll a,b;
			cin>>a>>b;
			num+=(b-a+1);
		}
		cout<<num<<endl;
	}
	return 0;
 } 

Measured memory_bytes: 256
from collections import Counter
n = int(input())
el = [int(i) for i in input().split()]
odd_l = Counter(el[::2])
even_l = Counter(el[1::2])
a1, b1 = odd_l.most_common(1)[0]
a2, b2 = even_l.most_common(1)[0]
if a1 != a2:
    ans = n - b1 - b2
else:
    if len(odd_l) > 1:
        b3 = odd_l.most_common(2)[1][1]
    else:
        b3 = 0
    if len(even_l) > 1:
        b4 = even_l.most_common(2)[1][1]
    else:
        b4 = 0
    ans = min(n - b1 - b4, n - b3 - b2)
print(ans)



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

int main(){
  int N;
  cin >> N;
  vector<int64_t> A(N),B(N);
  int64_t sumA=0;
  int64_t sumB=0;
  for(int i=0;i<N;i++){
    cin >> A.at(i);
    sumA+=A.at(i);
  }
  for(int i=0;i<N;i++){
    cin >> B.at(i);
    sumB+=B.at(i);
  }
  if(sumA<sumB){
    cout << -1 << endl;
    return 0;
  }
  vector<int64_t> diff(N);
  for(int i=0;i<N;i++){
    diff.at(i)=A.at(i)-B.at(i);
  }
  sort(diff.begin(),diff.end());
  if(diff.front()>=0){
    cout << 0 << endl;
    return 0;
  }
  int left=0;
  int right=N-1;
  vector<bool> flag(N,false);
  int64_t ans=0;
  while(diff.at(left)<0){
    if(diff.at(right)+diff.at(left)>0){
      diff.at(right)+=diff.at(left);
      diff.at(left)=0;
      if(!flag.at(left)){
        flag.at(left)=true;
        ans++;
      }
      if(!flag.at(right)){
        flag.at(right)=true;
        ans++;
      }
      left++;
    }else if(diff.at(right)+diff.at(left)<0){
      diff.at(left)+=diff.at(right);
      diff.at(right)=0;
      if(!flag.at(left)){
        flag.at(left)=true;
        ans++;
      }
      if(!flag.at(right)){
        flag.at(right)=true;
        ans++;
      }
      right--;
    }else{
      diff.at(left)=0;
      diff.at(right)=0;
      if(!flag.at(left)){
        flag.at(left)=true;
        ans++;
      }
      if(!flag.at(right)){
        flag.at(right)=true;
        ans++;
      }
      left++;
      right--;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 2560
using System;
using System.Linq;

namespace ABC139_C
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine());
            var H = Console.ReadLine().Split().Select(int.Parse).ToArray();

            var ans = 0;
            var c = 0;
            var temp = 0;
            for (int i = 0; i < H.Length; i++)
            {
                if (c >= H[i])
                {
                    temp++;
                }
                else
                {
                    ans = Math.Max(temp, ans);
                    temp = 0;
                }
                c = H[i];
            }

            ans = Math.Max(temp, ans);
            Console.WriteLine(ans);
        }
    }
}


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

// #define DEBUG

using namespace std;

const int N = 2e5+7;
const int MOD = 1e9+7;
const double eps = 1e-11;
typedef pair<int, int> pii;

struct Node
{
    int x, h;
    friend bool operator < (const Node &n1, const Node &n2) {
        return n1.x < n2.x;
    }
    friend istream& operator >> (istream &is, Node &nd) {
        return is >> nd.x >> nd.h;
    }
} b[N];

int n, d, a;
int del[N], hhh[N];

inline int getpos(const long long &x)
{
    int l = 1, r = n;
    while (l < r) {
        int mid = (l+r)>>1;
        if (b[mid].x <= x) l = mid+1;
        else r = mid;
    }
    return b[l].x > x ? l : n+1;
}

inline void solve()
{
    cin >> n >> d >> a;
    for (int i = 1; i <= n; ++i)
        cin >> b[i];

    sort(b+1, b+n+1);
    long long res = 0;
    for (int i = 1, j = 1, now = 0, t, k; i <= n; ++i) {
        while (j <= i) now -= del[j++]*a;
        if (now >= b[i].h) continue;
        t = (b[i].h-now)/a+((b[i].h-now)%a != 0);
        res += t;
        now += t*a;
        del[getpos(1ll*b[i].x+d+d)] += t;
    }
    cout << res << endl;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int T = 1;
    while (T--) {
        solve();
    }
    return 0;
}

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

#define rep(i, n) for (int i = 0; i < n; ++i)
#define ALL(a) (a).begin(), (a).end()
#define rALL(a) (a).rbegin(), (a).rend()
#define SZ(x) ((int)(x).size())
using ll = long long;
using P = pair<int, int>;
using llP = pair<ll, ll>;
using DoP = pair<double, double>;
const int di[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dj[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int INF = 1 << 29;
const ll INF64 = 1ll << 55;
const int mod = 1000000007;
//const int mod = 998244353;

template <class T>inline bool chmin(T &a, const T b)
{
  if (a > b)
  {
    a = b;
    return true;
  }
  return false;
}
template <class T>inline bool chmax(T &a, const T b)
{
  if (a < b)
  {
    a = b;
    return true;
  }
  return false;
}
template <class T>inline void line_out(const vector<T> vec) {
  int n = SZ(vec);
  rep(i, n) {
    cout << vec[i];
    if(i < n-1) cout << " ";
  }
  cout << endl;
  return;
}

struct mint
{
  ll x; // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint &operator+=(const mint a)
  {
    if ((x += a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator-=(const mint a)
  {
    if ((x += mod - a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator*=(const mint a)
  {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const
  {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint a) const
  {
    mint res(*this);
    return res -= a;
  }
  mint &operator++()
  {
    if ((x += 1) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator--()
  {
    if ((x += mod - 1) >= mod)
      x -= mod;
    return *this;
  }
  mint operator*(const mint a) const
  {
    mint res(*this);
    return res *= a;
  }
  mint pow(ll t) const
  {
    if (!t)
      return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1)
      a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const
  {
    return pow(mod - 2);
  }
  mint &operator/=(const mint a)
  {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const
  {
    mint res(*this);
    return res /= a;
  }
};


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

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

  vector<bool> dp(k+1, false);


  for(int i = 1; i <= k; ++i) {
    for(int j = 0; j < n; ++j) {
      if(i >= a[j]) dp[i] = dp[i] | !dp[i-a[j]];
    }
  }
  cout << (dp[k] ? "First" : "Second") << endl;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
	long long N, D, X, Y, sum = 0;
	cin >> N >> D;
	for (int i = 0; i < N; i++)
	{
		cin >> X >> Y;
		if (X * X + Y * Y <= D * D)
			sum++;
	}
	cout << sum;
	return 0;
}

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

int main()
{
	long long a, b, k;
	cin >> a >> b >> k;
	if (a + b <= k)
	{
		cout << "0 0" << endl;
	}
	else
	{
		if (k <= a) cout << a - k << " " << b << endl;
		else cout << "0 " << b + a - k;
	}
	return 0;
}

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

int main() {

  int m1, d1, m2, d2;
  cin >> m1 >> d1 >> m2 >> d2;

  if (d1 == 28) {
    if (m1 == 2) {
      cout << 1 << endl;
    } else {
      cout << 0 << endl;
    }
  } else if (d1 == 30) {
    if (m1 == 2 || m1 == 4 || m1 == 6 || m1 == 9 || m1 == 11) {
      cout << 1 << endl;
    } else {
      cout << 0 << endl;
    }
  } else if (d1 == 31) {
    if (m1 == 1 || m1 == 3 || m1 == 5 || m1 == 7 || m1 == 8 || m1 == 10 || m1 == 12) {
      cout << 1 << endl;
    } else {
      cout << 0 << endl;
    }
  } else {
    cout << 0 << endl;
  }

}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
int main(){
  int N, K;
  cin >> N >> K;
  vector<int> V(N);
  for(int i=0; i<N; i++) cin >> V[i];
  int r = 0;
  for(int i=0; i<=min(N, K); i++){
    for(int j=0; j<=min(N-i, K-i); j++){
      vector<int> a(i+j);
      for(int k=0; k<i; k++) a[k]=V[k];
      for(int k=0; k<j; k++) a[i+k]=V[N-j+k];
      int sa=0;
      vector<int> b;
      for(int ak: a){
        sa += ak;
        if(ak<0) b.push_back(ak);
      }
      sort(b.begin(), b.end());
      int sb=0;
      for(int k=0; k<b.size()&&k<K-i-j; k++) sb+=b[k];
      r = max(r, sa-sb);
    }
  }
  cout << r << endl;
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main() {
    int n, a[100000], i, btn;
    scanf("%d", &n);
    for (i=0; i<n; i++) {
        scanf("%d", &a[i]);
    }
    i = 0;
    btn = 1;
    while (1) {
        int tmp;
        if (a[btn-1] == -1) {
            puts("-1");
            return 0;
        } else if (btn == 2) {
            printf("%d\n", i);
            return 0;
        }
        i++;
        tmp = a[btn-1];
        a[btn-1] = -1;
        btn = tmp;
    }
}


Measured memory_bytes: 512
import math


def main():
    N, K = map(int, input().split())
    ans = 0
    for i in range(1, N+1):
        x = math.ceil(math.log(-(-K//i), 2))
        ans += 1/(2**x)
    print(ans/N)


if __name__ == "__main__":
    main()


Measured memory_bytes: 39920
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,K,A,B,L;
string alpha = "abcdefghijklmnopqrstuvwxyz";
string ALPHA = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const ll MOD = (1e+9) + 7;

int main() {
    cin>>M>>K;
    if(M == 0){
        cout<<(K == 0 ? "0 0" : "-1")<<endl;
        return 0;
    }
    if(M == 1){
        cout<<(K == 0 ? "0 1 1 0" : "-1")<<endl;
        return 0;
    }
    if((K>>M) > 0){
        cout<<-1<<endl;
        return 0;
    }
    rep(i,1<<M){
        if(i == K)continue;
        cout<<i<<' ';
    }
    cout<<K<<' ';
    rep(i,1<<M){
        if((1<<M) - i - 1 == K) continue;
        cout<<(1<<M) - i - 1<<' ';
    }
    cout<<K<<endl;
}


Measured memory_bytes: 1792
#include<stdio.h>
int main(void)
{
	int n,m,t[100],a,s[100],h=0,i,j;
	scanf("%d %d", &n, &m);
	for(i=0; i<m; i++)
	scanf("%d", &t[i]);
	for(i=0; i<m; i++)
	{
		for(j=1; j<=n; j++)
		{
			if(i==0)
			s[j]=0;
			scanf("%d", &a);
			if(a==t[i])
			s[j]++;
			else
			h++;
		}
		s[t[i]]+=h;
		h=0;
	}
	for(i=1; i<=n; i++)
	printf("%d\n", s[i]);
	
	return 0;
}


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

int main(){
  int n; cin>>n;
  vector<int> a(n);
  for(int i=0; i<n; ++i) cin>>a[i];
  sort(a.begin(),a.end());
  cout<<a[n-1]-a[0]<<endl;
}

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

#define ll long long

#define rep(i, n) for (int i = 0; i < (int)(n); i++)  //(i, 10) i=0～i=9まで
#define repr(i, n) for (int i = n; i >= 0; i--)   // (i, 10) i=10～i=0まで
#define FOR(i, m, n) for (int i = m; i < n; i++)  // (i, 3, 10) i=3～i=9まで

int main() {
    int n;
    cin >> n;
    vector<int> a(n);

    int maxv  = -1000000;
    int minv  = 1000000;
    ll  total = 0;

    rep(i, n) {
        cin >> a[i];
        if (maxv < a[i]) maxv = a[i];
        if (minv > a[i]) minv = a[i];
        total += a[i];
    }
    cout << minv << " " << maxv << " " << total << endl;

    return 0;
}



Measured memory_bytes: 3144
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef tree<ii,null_type,less<ii>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

bool ok(ll N, ll K) {
	while(N>=K) {
		if(N%K==0) N/=K;
		else N%=K;
	}
	return N==1;
}

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	ll N; cin>>N;
	ll M=N-1;
	set<ll> div;
	for (ll d=1; d*d<=M; d++) {
		if(M%d==0)
			div.insert(d), div.insert(M/d);
	}
	div.erase(1);
	set<ll> div2;
	for (ll K=1; K*K<=N; K++) {
		if(N%K==0)
			div2.insert(K), div2.insert(N/K);
	}
	div2.erase(1);

	ll ret=div.size();
	for (ll K : div2) {
		if(ok(N,K))
			ret++;
	}
	cout<<ret<<"\n";
	return 0;
}

Measured memory_bytes: 512
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD

N, W = imn()
wv = [iln() for _ in range(N)]

dp = [0 for _ in range(W+1)]

for i in range(N):
    for w in range(W, -1,  -1):
        if w - wv[i][0] >= 0: dp[w] = max(dp[w], dp[w-wv[i][0]]+wv[i][1])
print(dp[W])

Measured memory_bytes: 70764