akhauriyash/Code-Regression huggingface dataset:
d=gets.to_i
c=gets.split.map(&:to_i)
s=[]
d.times do
  s << gets.split.map(&:to_i)
end
l=[0]*26
(d-2).times do |i|
  m=0
  mi=0
  26.times do |j|
    l[j]+=1
  end
  26.times do |j|
    cs1=c[j]*(3*l[j]-2)+s[i][j]
    26.times do |k|
      cs2=c[k]*(2*l[k]-1)+s[i+1][k]
      26.times do |kk|
        cs3=c[kk]*l[kk]+s[i+2][kk]
        if cs1+cs2+cs3>m
          m=cs1+cs2+cs3
          mi=j
        end
      end
    end
  end
  puts mi+1
  l[mi]=0
end
m=0
mi=0
26.times do |j|
  l[j]+=1
end
26.times do |j|
  cs1=c[j]*(2*l[j]-1)+s[d-2][j]
  26.times do |k|
    cs2=c[k]*l[k]+s[d-1][k]
    if cs1+cs2>m
      m=cs1+cs2
      mi=j
    end
  end
end
puts mi+1
l[mi]=0
m=0
mi=0
26.times do |j|
  l[j]+=1
end
26.times do |j|
  cs=c[j]*l[j]+s[d-1][j]
  if cs>m
    m=cs
    mi=j
  end
end
puts mi+1


Measured memory_bytes: 14396
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
int a[1005];
using namespace std;
int main(){
	int n,m;
	int sum=0;
	cin>>n>>m;
	for(int i=0;i<n;i++){
		scanf("%d",a+i);
		sum+=a[i];
	}
	sort(a,a+n,greater<int>()); 
	
	
	int time=0;
	for(int i=0;i<n;i++){
		if(a[i]>=sum/float(4*m)){
			time++;
		}
	}
	if(time>=m)cout<<"Yes";
	else cout<<"No";
	
	
	
	
	
}

Measured memory_bytes: 256
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
#define fi first
#define se second
map<int,int> mp;
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
ll lcm(ll c,ll d){return c*d/gcd(c,d);}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
int n,cnt=0;
cin>>n;
vector<int> a(n);
for(int i=0;i<n;i++){
    cin>>a.at(i);
    if(a.at(i)%2==1)cnt++;
}
if(cnt%2==0)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}


Measured memory_bytes: 640
#include <algorithm>
#include <bitset>
#include <cmath>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using ll = long long;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repk(i, k, n) for (int i = k; i < n; i++)
#define MOD 1000000007
#define INF INT32_MAX / 2
#define PIE 3.14159265358979323

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;
}
template <class T>
T GCD(T a, T b) {
    if (b == 0)
        return a;
    else
        return GCD(b, a % b);
}
template <class T>
inline T LCM(T a, T b) {
    return (a * b) / GCD(a, b);
}

using namespace std;
//#inculude <bits/stdc++.h>
//#define int long long

signed main() {
    int n;
    cin >> n;
    map<char, int> m;
    map<char, int> ans;
    rep(i, 26) ans['a' + i] = 100;
    string s;
    rep(i, n) {
        cin >> s;
        rep(j, int(s.size())) m[s[j]]++;
        rep(j, 26) chmin(ans['a' + j], m['a' + j]);
        m.clear();
    }
    string res = "";
    rep(i, 26) {
        if (ans['a' + i] == 100)
            continue;
        else {
            while (ans['a' + i]--)
                res.push_back('a' + i);
        }
    }
    sort(res.begin(), res.end());
    cout << res << endl;
    return 0;
}

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

#ifdef LOCAL
#include "/home/shahraaz/bin/debug.h"
#else
#define db(...)
#define pc(...)
#endif

using ll = long long;
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(), v.end()

const int NAX = 2e5 + 5, MOD = 1000000007;

class Solution
{
private:
    vector<int> getSmallerLeft(vector<int> H)
    {
        stack<int> s;
        vector<int> ret(H.size());
        for (int i = 0; i < H.size(); i++)
        {
            while (s.size() && H[s.top()] >= H[i])
                s.pop();
            if (s.size())
                ret[i] = s.top();
            else
                ret[i] = i;
            s.push(i);
        }
        return ret;
    }

    vector<int> getSmallerRight(vector<int> H)
    {
        reverse(H.begin(), H.end());
        auto ret = getSmallerLeft(H);
        for (size_t i = 0; i < H.size(); ++i)
            ret[i] = H.size() - 1 - ret[i];
        reverse(ret.begin(), ret.end());
        return ret;
    }

public:
    Solution() {}
    ~Solution() {}
    void solveCase()
    {
        int n;
        cin >> n;
        vector<int> v(n + 2);
        for (size_t i = 1; i <= n; i++)
        {
            cin >> v[i];
            // v[i - 1] = i;
        }
        v[0] = v[n + 1] = -1;
        auto left = getSmallerLeft(v);
        auto right = getSmallerRight(v);
        pc(v);
        pc(left, right);
        ll res = 0;
        for (ll i = 1; i <= n; i++)
        {
            db(i - left[i], right[i] - i);
            res += v[i] * max(1LL, i - left[i]) * max(1LL, right[i] - i);
        }
        cout << res << '\n';
    }
};

int32_t main()
{
#ifndef LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif
    int t = 1;
    // cin >> t;
    Solution mySolver;
    for (int i = 1; i <= t; ++i)
    {
        mySolver.solveCase();
#ifdef LOCAL
        cerr << "Case #" << i << ": Time " << chrono::duration<double>(chrono::steady_clock::now() - TimeStart).count() << " s.\n";
        TimeStart = chrono::steady_clock::now();
#endif
    }
    return 0;
}

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

#define FASTIO  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ll long long int
#define ld long double
#define vll vector<ll>
#define pll pair<ll,ll>
#define vl(p) vector<p>
#define w while
#define For(i,s,x) for(i=s;i<x;i++)
#define Fore(i,s,x) for(i=s;i<=x;i++)
#define FOR(i,x) for(i=0;i<x;i++)
#define Rof(i,s,x) for(i=s;i>=x;i--)
#define all(v) v.begin(),v.end()
#define it(r,v) for(auto r=v.begin();r!=v.end();r++)
#define pb push_back
#define in insert
#define sz size()
#define F first
#define S second
#define nl cout<<"\n"
#define pr(a) cout<<a<<" "
#define pr2(a,b) cout<<a<<" "<<b<<"\n"
#define pr3(a,b,c) cout<<a<<" "<<b<<" "<<c<<"\n"
#define mod 1000000007

int main()
{
	FASTIO;
	ll a,b,sum=0,i,dif;
	cin>>a>>b;
	ll arr[b];
	for(i=0;i<b;i++)
        cin>>arr[i];
   for(i=0;i<b;i++)
        sum=sum+arr[i];
   dif=a-sum;
   if(dif<0)
        cout<<-1<<endl;
   else
    cout<<dif<<endl;

}



Measured memory_bytes: 3676
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<cstring>
#include<utility>
#include<set>
#include<stack>
#include<complex>
#include<bitset>
#define vi vector<int>
#define vvi vector<vector<int> >
#define ll long long int
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
#define ld long double
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define CC puts("-------ok--------");
#define all(in) in.begin(), in.end()
#define bv vector<bool>
using namespace std;
typedef pair<int, int>PA;
using namespace std;
#define MAX  999999
int main(){
	int h,m,s;
	while(cin>>h>>m>>s,!(h+m+s==-3)){
		int r=3600*2-(h*3600+m*60+s);int hoge=3*r;
		int th=r/3600; r%=3600;
		int tm=r/60; r%=60;
		int ts=r;
		printf("%02d:%02d:%02d\n",th,tm,ts);	
		 th=hoge/3600; hoge%=3600;
		tm=hoge/60; hoge%=60;
		ts=hoge;	
		printf("%02d:%02d:%02d\n",th,tm,ts);	

		
	}
}

Measured memory_bytes: 3228
import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static Scanner sc;
	static PrintWriter out;
	static ArrayList<Edge> adj[];
	static int V,E;
	static int[] dist;
	static int[] parent;
	static final int oo = (int) 1e9;
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		sc = new Scanner(System.in);
		out = new PrintWriter(System.out);
		int n = sc.nextInt();
		out.println(n==1?0:1);
		out.close();
	}
	static void dijkstra(int src) {
		dist = new int[V];
		Arrays.fill(dist, oo);
		parent = new int[V];
		Arrays.fill(parent, -1);
		dist[src] = 0;
		PriorityQueue<Edge> pq = new PriorityQueue<>();
		pq.add(new Edge(src,0));
		while(!pq.isEmpty()) {
			Edge e = pq.poll();
			if(dist[e.x] < e.y)
				continue;
//			if(e.x == dest)
//				return e.y;
			for(Edge e2:adj[e.x]) {
				if(dist[e2.x] > e2.y+e.y) {
					pq.add(new Edge(e2.x,dist[e2.x] = e2.y+e.y));
					parent[e2.x] = e.x;
				}
			}
		}
//		return -1;
	}
	static class Edge extends java.awt.Point implements Comparable<Edge>{		
		public Edge(int u, int val) {
			// TODO Auto-generated constructor stub
			super(u, val);
		}

		@Override
		public int compareTo(Edge e) {
			// TODO Auto-generated method stub
			return y - e.y;
		}		
	}
	static class Scanner{
		BufferedReader br;
		StringTokenizer st;
		public Scanner(InputStream in) {
			br = new BufferedReader(new InputStreamReader(in));
		}
		private String next() throws Exception{
			while(st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public int nextInt() throws Exception{
			return Integer.parseInt(next());
		}
		public long nextLong() throws Exception{
			return Long.parseLong(next());
		}
		public double nextDouble() throws Exception{
			return Double.parseDouble(next());
		}
		public String nextLine() throws Exception {
			return br.readLine();
		}

	}
}


Measured memory_bytes: 32668
#include<iostream>
#include<iomanip>
#include<math.h>
#include<algorithm>
#include<functional>
#include<utility>
#include<queue>
#include<string.h>
#include<string>
#include<set>
#include<map>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int N_MAX=100000;
class UnionFind {
  vector<ll> par, rank; // par > 0: number, par < 0: -par
public:
  void init(ll n) {
    par.resize(n, 1); rank.resize(n, 0);
  }
  ll getSize(ll x) {
    return par[find(x)];
  }
  ll find(ll x) {
    if (par[x] > 0) return x;
    return -(par[x] = -find(-par[x]));
  }
  void merge(ll x, ll y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (rank[x] < rank[y]) {
      par[y] += par[x];
      par[x] = -y;
    } else {
      par[x] += par[y];
      par[y] = -x;
      if (rank[x] == rank[y]) rank[x]++;
    }
  }
  bool isSame(ll x, ll y) {
    return find(x) == find(y);
  }
};
ll N;
ll x[100010];
ll y[100010];
int main(){
    cin>>N;
    UnionFind uf;
    uf.init(2*N_MAX);
    ll cnt=0;
    map<ll,ll> edgeCnt;
    map<ll, pair< set<ll>,set<ll> > > vCnt;
    for(int i=0;i<N;i++){
        cin>>x[i]>>y[i];
        uf.merge(x[i],N_MAX+y[i]);
    }
    for(int i=0;i<N;i++){
        ll par=uf.find(x[i]);
        edgeCnt[par]++;
        vCnt[par].first.insert(x[i]);
        vCnt[par].second.insert(y[i]);
    }
    ll ans=0;
    set<ll> checkedSet;
    for(int i=0;i<N;i++){
        ll par=uf.find(x[i]);
        if(checkedSet.find(par)==checkedSet.end()){
            checkedSet.insert(par);
            ll x=vCnt[par].first.size();
            ll y=vCnt[par].second.size();
            if( x>=2 && y>=2){
                ans+=x*y-edgeCnt[par];
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

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

int main() {
    string S;
    cin >> S;
    int N = (int)S.size();
    vector<int> A(N + 1, 0);

    for (int i = 0; i < N; i++) {
        if (S[i] == '<') {
            A[i + 1] = max(A[i + 1], A[i] + 1);
        }
    }

    for (int i = N - 1; i >= 0; i--) {
        if (S[i] == '>') {
            A[i] = max(A[i], A[i + 1] + 1);
        }
    }

    long long res = 0;
    for (int i = 0; i < N + 1; i++) {
        res += A[i];
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 2820
/**
        Bismilla- hir rahma-nir rahi-m
    @uthor Md Hasibur Rahman (Evan)
                JKKNIU
*/


#include<bits/stdc++.h>
#define         ll              long long
#define         FI              freopen("input.txt","r",stdin)
#define         FO              freopen("output.txt","w",stdout)
#define         PrintCase(i)    printf("Case %d: ",i)
#define         sc(a)           scanf("%d",&a)
#define         scl(a)          scanf("%lld",&a)
#define         rep(i,n)        for(int i=0;i<n;i++)
#define         pb              push_back
#define         MAX             1000000
#define         fast            ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define			endl			"\n"


using namespace std;

bool isPrime(ll a)
{
    for(ll i=2;i*i<=a;i++)
        if(a%i==0)
            return false;
    return true;
}






bool isPowerOfTwo(ll a)
{
    if(a==1)
        return true;
    if(a&1)
        return false;
    while(a)
    {
        a/=2;
        if(a!=1 && a&1)
            return false;
        if(a==1)
            return true;
    }
    return true;
}




ll gcd(ll a, ll b)
{
    if(a<0 || b<0)
    {
        a = abs(a);
        b = abs(b);
    }
    if(a<b)
        swap(a,b);
    if(a%b==0 || b==0)
        return b;
    else
        return gcd(b,a%b);
}



ll lcm(ll a, ll b)
{
    return (a*b)/gcd(a,b);
}



ll power(ll base, ll exponent)
{
    ll ans = 1;
    for(ll i=1;i<=exponent;i++)
        ans*=base;
    return ans;
}




bool isPowerOfX(ll x, ll value)
{
    if(value==1)
        return true;
    while(value)
    {
        value/=x;
        if(value%x && value!=1)
            return false;
    }
    return true;
}


ll X_or(ll for1, ll for2, ll value)
{
	ll arr[7];
	arr[3] = for1^for2;
	//cout<<(for1^for2)<<endl;
	arr[4] = arr[3]^for2;
	arr[5] = arr[4]^arr[3];
	cout<<arr[3]<<" "<<arr[4]<<" "<<arr[5]<<" ..... \n";
	if(value%3==0)
	{
		//cout<<arr[]
		return arr[3];
	}
	else
	{
		ll ret = ((value%3)==1)?arr[4] : arr[5];
		return ret;
	}
}


ll X_nor(ll for1, ll for2, ll value)
{
	ll arr[7];
	arr[3] = ~(for1^for2);
	//cout<<~(for1^for2)<<endl;
	if(arr[3]<0)
		arr[3]*=(-1);
	arr[4] = ~(arr[3]^for2);
	if(arr[4]<0)
		arr[4]*=(-1);
	arr[5] = ~(arr[3]^arr[4]);
	if(arr[5]<0)
		arr[5]*=(-1);
	cout<<arr[3]<<" "<<arr[4]<<" "<<arr[5]<<" ..... \n";
	if(value%3==0)
	{
		return arr[3];
	}
	else
	{
		ll ret = (value%3==1)? arr[4] : arr[5];
		return ret;
	}
}


int main()
{
	int n,x;
	cin>>x>>n;
	vector<int>arr(n);
	rep(i,n)cin>>arr[i];
	int value = INT_MAX , mn = INT_MAX;
	for(int i=-200;i<=110;i++)
	{
		if(abs(x-i)<mn && find(arr.begin(),arr.end(),i)==arr.end())
		{
			value = i;
			mn = min(mn,abs(x-i));
		}
	}
	cout<<value<<endl;
	return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
#define ll long long int 
const int mod = 1e9 + 7;
int main() {
    int n;cin >> n;
    int tmp = 1e9 + 7;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        int x;cin >> x;
        if (tmp > x) {
            tmp = x;
            ++ans;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a),i##formax=(b);i<i##formax;i++)
#define FORR(i,a,b) for(int i=(a),i##formax=(b);i>=i##formax;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pcnt __builtin_popcount
#define sz(x) (int)(x).size()
#define maxs(x,y) x=max(x,y)
#define mins(x,y) x=min(x,y)
#define show(x) cout<<#x<<" = "<<x<<endl;
#define all(a) (a.begin()),(a.end())
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define perm(c) sort(all(c));for(bool c##p=1;c##p;c##p=next_permutation(all(c)))
#define bitComb(a,n,k) for(int a##x,a##y,a=(1<<k)-1;a<(1<<n);a##x=a&-a,a##y=a+a##x,a=(((a&~a##y)/a##x)>>1)|a##y)
#define uniq(v) sort(all(v));v.erase(unique(all(v)), v.end())
#define bit(n) (1LL<<(n))
#define randInt(l,r) (uniform_int_distribution<ll>(l,r)(rnd))
#define randDouble(l,r) (uniform_real_distribution<double>(l,r)(rnd))
#define dout(d) printf("%.12f\n",d)

typedef long long ll;
typedef __int128_t lll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<class T>using V=vector<T>;
template<class T>using VV=V<V<T>>;
template<class T,class Y>ostream& operator<<(ostream& o,const pair<T,Y>& p){return o<<"("<<p.fi<<", "<<p.se<<")";}
template<typename A,size_t N,typename T>void Fill(A (&array)[N],const T&v){fill((T*)array,(T*)(array+N),v);}
lll gcd(lll a,lll b,lll &x,lll &y){if(!b){x=1;y=0;return a;}lll d=gcd(b,a%b,y,x);y-=a/b*x;return d;}
ll gcd(ll a,ll b){lll x=0,y=0;return gcd(a,b,x,y);}
ll modInv(ll a,ll m){lll x,y;gcd(a,m,x,y);return (x%m+m)%m;}
ll modPow(lll a,lll n,ll m){if(!a)return a;lll p=1;for(;n>0;n>>=1,a=a*a%m)if(n&1)p=p*a%m;return(ll)p;}
bool isPrime(ll n){if(n<2||n%2==0)return n==2;lll t=n-1,d=t/(t&-t);for(lll a:{2,325,9375,28178,450775,9780504,1795265022})if(a%n){for(t=d,a=modPow(a,t,n);t!=n-1&&a!=1&&a!=n-1;a=a*a%n,t=t*2%n);if(a!=n-1&&t%2==0)return 0;}return 1;}
const int IINF = 1e9+6;
const ll LINF = 1e18;
const int MOD = 1e9+7;
const double PI = acos(-1);
const double EPS = 1e-10;
static random_device rd;
static mt19937 rnd(rd());

const int N = 1000;
int n, k;
ll _s[N+1], *s=_s+1, v[500500];
main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n >> k;
  FOR(i, 0, n){
    cin >> s[i];
    s[i] += s[i-1];
  }
  int idx = 0;
  FOR(i, 0, n)FOR(j, i, n){
    v[idx] = s[j]-s[i-1];
    idx++;
  }
  ll ans = 0;
  FORR(i, 40, 0){
    ans ^= bit(i);
    int c = k;
    FOR(j, 0, idx){
      if((ans&v[j])==ans) c--;
      if(!c) break;
    }
    if(c) ans ^= bit(i);
  }
  cout << ans << endl;
}

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

inline int read() {
	int x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
	return x * f;
}

int main() {
	int n = read(), m = read();
	int x = read(), y = read();
	printf("%.10f ", 1.0 * n * m / 2.0);
	if (n % 2 == 0 && m % 2 == 0 && x == n / 2 && y == m / 2) puts("1");
	else puts("0");
	return 0; 
}

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

int main(){
  int N,A,B,P1,P2;
  cin >> N >> A >> B;
  P1 = A * N, P2 = B;
  if(P1 <= P2){
    cout << P1 << endl;
  }
  else{
    cout << P2 << endl;
  }
}
  
  

Measured memory_bytes: 256
h=int(input())
def feb(s):
    i=0
    A=[0]*2000
    A[0]=s
    while(1):
        if A[i]%2==0:
            
            A[i+1]=(A[i]//2)
        elif A[i]%2==1:
            A[i+1]= 3*A[i]+1
        for j in range(i):
            if A[j]==A[i]:
               return i+1
        i+=1
print(feb(h))

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <cstdio>
#include <string.h>
using namespace std;

bool played[5010][5010] = {0}; // 試合したかどうか
bool visited[5001], is_outed[5001];
vector<int> games[5001]; // games[i][j] チームjがチームiに勝利
vector<int> r; // 順位

void dfs(int n){
	visited[n] = true;
	for(int i = 0; i < games[n].size(); ++i){
		if(!visited[games[n][i]]){
			dfs(games[n][i]);
		}
	}
	if(!is_outed[n]){
		cout << n << endl;
		r.push_back(n);
	}
	is_outed[n] = true;
	return;
}

int main() {
	int n, m, a, b;
	while(cin >> n >> m){
		for(int i = 0; i <= 5000; ++i)
			games[i].clear();
		r.clear();
		memset(played, 0 ,sizeof(played));
		memset(visited, 0, sizeof(visited));
		memset(is_outed, 0, sizeof(is_outed));
		for(int i = 0; i < m; ++i){
			scanf("%d %d", &a, &b);
			games[b].push_back(a);
			played[a][b] = true;
		}
		for(int i = 1; i <= n; ++i)
			dfs(i);
		int one = 1;
		for(int i = 0; i < n - 1; ++i){
			if(!played[r[i]][r[i + 1]] && !played[r[i + 1]][r[i]]){
				one = 0;
				break;
			}
		}
		cout << (one ^ 1) << endl;

	}
	return 0;
}

Measured memory_bytes: 26592
#include <stdio.h>
#define FREE 0
#define NOT_FREE 1
#define N 8
int putQueen(int);
int col[8],row[8],dpos[15],dneg[15],p[8][8];
int main(void){
    int n,i,j,k;
    for(i=0;i<8;i++){
        col[i]=FREE;
        row[i]=FREE;
        for(j=0;j<8;j++){
            p[i][j]=FREE;
        }
    }
    for(i=0;i<15;i++){
        dpos[i]=FREE;
        dneg[i]=FREE;
    }
    scanf("%d",&n);
    for(k=0;k<n;k++){
        scanf("%d%d",&i,&j);
        p[i][j] = NOT_FREE;
        row[i] = NOT_FREE;
        col[j] = NOT_FREE;
        dpos[i+j] = dneg[i-j+N-1] = NOT_FREE;
    }
    k = putQueen(0);
    
    
    return 0;
}

int putQueen(int i){
    int j=0,a,b;
    if(i==N){
        for(a=0;a<N;a++){
        for(b=0;b<N;b++){
            if(p[a][b]==FREE){
                printf(".");
            }
            else{
                printf("Q");
            }
        }
        printf("\n");
    }
        return 0;
    }
    if(row[i] == NOT_FREE)putQueen(i+1);
    else{
    for(j = 0; j<N;j++){
        if(col[j] == NOT_FREE || dpos[i+j] == NOT_FREE || dneg[i-j+N-1] == NOT_FREE){
            continue;
        }
        //row[i] = j;
        col[j] = dpos[i+j] = dneg[i-j+N-1] = p[i][j]= NOT_FREE;
        putQueen(i+1);
        col[j] = dpos[i+j] = dneg[i-j+N-1] = p[i][j] = FREE;
        }
    }
}

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


/**
 * AIZU ONLINE JUDGE
 * 0654
 *  2020/5/5
 */
public class Main {


    boolean main() throws IOException {

        Scanner sc = new Scanner(systemin);

        int N = sc.nextInt();
        sc.nextLine();
        String S = sc.nextLine();
        int cnt = 0;
        for(int i = 0;i < N - 1;) {
            if (S.charAt(i) != S.charAt(i + 1)) {
                cnt++;
                i+=2;
            }
            else {
                i++;
            }
        }
        result.printf("%d\n",  cnt);
        
        sc.close();
        return false;
    }



    PrintStream log;
    PrintStream result = System.out;
    BufferedReader systemin;

    static Main instance = new Main();

    Main() {
        systemin = new BufferedReader(new InputStreamReader(System.in));
        log = new PrintStream(new OutputStream() { public void write(int b) {} } );
    }

    public static void main(String[] args) throws IOException {

        instance.main();
        instance.systemin.close();
    }


}




Measured memory_bytes: 31872
def s():
 import sys
 r=sys.stdin.readline
 I=float('inf')
 for e in iter(r,'0 0\n'):
  n,k=map(int,e.split())
  F=[[I]*-~n for _ in[0]*-~n]
  for i in range(1,n+1):F[i][i]=0
  for _ in[0]*k:
   f=r();g=map(int,f[2:].split())
   if'0'==f[0]:a,b=g;A=F[a][b];print([A,-1][A==I])
   else:
    c,d,e=g
    if e<F[c][d]:
     for i in range(2,n+1):
      for j in range(1,i):
       F[i][j]=F[j][i]=min(F[i][j],F[i][c]+e+F[d][j],F[i][d]+e+F[c][j])
s()


Measured memory_bytes: 6240
#!/usr/bin/env python3
import sys
from fractions import gcd

def solve(N: int, M: int, a: "List[int]"):
    koubaisu = a[0]
    for i in range(1, N):

        koubaisu = koubaisu * a[i] // gcd(koubaisu, a[i])

    for i in a:
        if koubaisu // i % 2 == 0:
            print(0)
            exit()

    print(M // koubaisu - M // (2*koubaisu))


    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int(next(tokens)) // 2 for _ in range(N)]  # type: "List[int]"
    solve(N, M, a)

if __name__ == '__main__':
    main()


Measured memory_bytes: 17500
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<int(n);++i)
#define all(a) a.begin(),a.end()
typedef long long ll;
 
using P = pair<ll,ll>;
#define v first
#define w second
 
// v高い順（vが同じならw軽い方優先）
bool comp(P a, P b){
    return a.v == b.v ? a.w < b.w : a.v > b.v;
}
 
int main(void){
    ll N,W;
    cin>>N>>W;
    vector<P> a(N);
    rep(i,N){
        ll v,w;
        cin>>w>>v;
        a[i] = {v,w};
    }
    vector<P> dp = {{0,0}};
 
    rep(i,N){
        vector<P> tmp;
        for(auto& s : dp){
            tmp.push_back(s);
            tmp.push_back({s.v + a[i].v, s.w + a[i].w});
        }
 
        sort(all(tmp),comp);
        dp.clear();
        ll w_border = W+1;
        for(auto& s : tmp){
            if( w_border > s.w){
                w_border = s.w;
                dp.push_back(s);
            }
        }
    }
    cout<<dp[0].v<<endl;
    return 0;
}

Measured memory_bytes: 512
s = input()
ans = []
for i in s:
    cnt = 0
    t = s
    while t.count(i) < len(t):
        cnt += 1
        tmp = ''
        for j in range(len(t)-1):
            if t[j] != i and t[j+1] != i:
                tmp = tmp+t[j]
            else:
                tmp = tmp+i
        t = tmp
    ans.append(cnt)
print(min(ans))


Measured memory_bytes: 3060
def fastio():
    import sys
    from io import StringIO 
    from atexit import register
    global input
    sys.stdin = StringIO(sys.stdin.read())
    input = lambda : sys.stdin.readline().rstrip('\r\n')
    sys.stdout = StringIO()
    register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()

MOD = 10**9 + 7
I = lambda:list(map(int,input().split()))

n, = I()
a = I()
ans = 0
for bit in range(64):
    c = [0, 0]
    for i in a:
        c[(i >> bit)&1] += 1
    ans += c[0] * c[1] * 2**bit
    ans %= MOD
    # print(ans, c[0], c[1], 2**i)
print(ans)

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

int main() {
  int a,b, c;
  cin >> a >> b;
  c=a*b%2;
  
  if(c>0){
    cout << "Odd" << endl;
  }
  else{
    cout << "Even" << endl;
    
  }
  
  
}

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

using namespace std;

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

int mem[100000];

int main(int argc, char const *argv[]) {
  int n;
  cin >> n;
  // memset(&mem, 0, sizeof(mem));
  REP(i, n) {
    int a_in;
    cin >> a_in;
    mem[a_in]++;
  }
  int ans = mem[0] + mem[1];
  FOR(i, 1, 99999) {
    int num = mem[i - 1] + mem[i] + mem[i + 1];
    ans = max(ans, num);
  }
  ans = max(ans, mem[99998] + mem[99999]);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1e9 + 7;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<class T>
istream& operator >> (istream& is, vector<T>& v)
{
	for (auto &i : v) is >> i;
	return is;
}
template<class T>
ostream& operator<<(ostream& os, vector<T>& v)
{
	const string delimiter = "\n";
	REP(i, v.size())
	{
		os << v[i];
		if (i != v.size() - 1) os << delimiter;
	}
	return os;
}
/*--------------------template--------------------*/
int n;
string s;

bool check(string t)
{
	char c = t[0]; t.push_back(c);

	if (t[0] == 'S')
	{
		if (s[0] == 'o' && t[n - 1] != t[1]) return false;
		if (s[0] == 'x' && t[n - 1] == t[1]) return false;
	}
	if (t[0] == 'W')
	{
		if (s[0] == 'o' && t[n - 1] == t[1]) return false;
		if (s[0] == 'x' && t[n - 1] != t[1]) return false;
	}
	FOR(i, 1, t.size() - 1)
	{
		if (t[i] == '.') return false;
		if (t[i] == 'S')
		{
			if (s[i] == 'o' && t[i - 1] != t[i + 1]) return false;
			if (s[i] == 'x' && t[i - 1] == t[i + 1]) return false;
		}
		if (t[i] == 'W')
		{
			if (s[i] == 'o' && t[i - 1] == t[i + 1]) return false;
			if (s[i] == 'x' && t[i - 1] != t[i + 1]) return false;
		}
	} 
	return true;
}

int main()
{
	cin.sync_with_stdio(false); cout << fixed << setprecision(10);
	cin >> n;
	cin >> s;
	vs ans(4, string(n, '.'));
	ans[0][0] = 'S', ans[0][n - 1] = 'S';
	ans[1][0] = 'S', ans[1][n - 1] = 'W';
	ans[2][0] = 'W', ans[2][n - 1] = 'S';
	ans[3][0] = 'W', ans[3][n - 1] = 'W';
	for (auto t : ans)
	{
		if (s[0] == 'o')
		{
			if(t[0] == 'S') t[1] = t[n - 1];
			if(t[0] == 'W') t[1] = (t[n - 1] == 'S' ? 'W' : 'S');
		}
		else
		{
			if (t[0] == 'W') t[1] = t[n - 1];
			if (t[0] == 'S') t[1] = (t[n - 1] == 'S' ? 'W' : 'S');
		}
		FOR(i, 1, n - 2)
		{
			if (s[i] == 'o')
			{
				if (t[i] == 'S') t[i+1] = t[i - 1];
				if (t[i] == 'W') t[i+1] = (t[i - 1] == 'S' ? 'W' : 'S');
			}
			else
			{
				if (t[i] == 'W') t[i+1] = t[i - 1];
				if (t[i] == 'S') t[i+1] = (t[i - 1] == 'S' ? 'W' : 'S');
			}
		}
		if (check(t))
		{
			cout << t << endl;
			return 0;
		}
	}
	cout << -1 << endl;
	return 0;
}

Measured memory_bytes: 1116
import math
s=input()
def kaibun(s):
    ls=len(s)

    if ls==1:
        print("YES")
        return
      
    ca,cb,cc=0,0,0
    l=[]
    for i in range(ls):
        if s[i]=="a":
            ca+=1
        if s[i]=="b":
            cb+=1
        if s[i]=="c":
            cc+=1
    l.append(ca)
    l.append(cb)
    l.append(cc)
    cnt_zero=0
    for j in l:
        if j==0:
            cnt_zero+=1
    if cnt_zero==2:
        print("NO")
        return

    elif cnt_zero==1:
        if ls==2:
            print("YES")
            return
        else:
            print("NO")
            return
          
    #cnt_zero=0のとき，つまりすべての文字が文字列に含まれるとき
    else:
        if ls==3 or ls==4:
            print("YES")
            return
        nmin=math.floor(ls/3.0)
        nmax=math.ceil(ls/3.0)
        nmax=int(nmax)
        nmin=int(nmin)
        #out=0
        for j in l:
            if j<nmin or nmax<j:
                print("NO")
                return

        print("YES")
        return
        
kaibun(s)

Measured memory_bytes: 9264
import math
from queue import PriorityQueue
from sys import stdin,stdout
from collections import defaultdict

def solve():
    n=int(input())
    ans=[0 for _ in range(200050)]
    for i in range(1,101):
        for j in range(1,101):
            for k in range(1,101):
                v=i*i+j*j+k*k+i*j+k*j+k*i
                ans[v]+=1
    for i in range(n):
        print(ans[i+1])
    

    
    
    
def main():
    solve()
main()


Measured memory_bytes: 11260
ls = [1, 9, 30, 76, 141, 267, 400, 624, 885, 1249, 1590, 2208, 2689, 3411, 4248, 5248, 6081, 7485, 8530, 10248, 11889, 13687, 15228, 17988, 20053, 22569, 25242, 28588, 31053, 35463, 38284, 42540, 46581, 50893, 55362, 61824, 65857, 71247, 76884, 84388, 89349, 97881, 103342, 111528, 120141, 128047, 134580, 146316, 154177, 164817, 174438, 185836, 194157, 207927, 218812, 233268, 245277, 257857, 268182, 288216, 299257, 313635, 330204, 347836, 362973, 383709, 397042, 416448, 434025, 456967, 471948, 499740, 515581, 536073, 559758, 583960, 604833, 633651, 652216, 683712, 709065, 734233, 754734, 793188, 818917, 846603, 874512, 909496, 933081, 977145, 1006126, 1041504, 1073385, 1106467, 1138536, 1187112, 1215145, 1255101, 1295142, 1342852, 1373253, 1422195, 1453816, 1502376, 1553361, 1595437, 1629570, 1691292, 1726717, 1782111, 1827492, 1887772, 1925853, 1986837, 2033674, 2089776, 2145333, 2197483, 2246640, 2332104, 2379085, 2434833, 2490534, 2554600, 2609625, 2693919, 2742052, 2813988, 2875245, 2952085, 3003306, 3096024, 3157249, 3224511, 3306240, 3388576, 3444609, 3533637, 3591322, 3693924, 3767085, 3842623, 3912324, 4027884, 4102093, 4181949, 4270422, 4361548, 4427853, 4548003, 4616104, 4718640, 4812789, 4918561, 5003286, 5131848, 5205481, 5299011, 5392008, 5521384, 5610705, 5739009, 5818390, 5930196, 6052893, 6156139, 6239472, 6402720, 6493681, 6623853, 6741078, 6864016, 6953457, 7094451, 7215016, 7359936, 7475145, 7593865, 7689630, 7886244, 7984165, 8130747, 8253888, 8403448, 8523897, 8684853, 8802826, 8949612, 9105537, 9267595, 9376656, 9574704, 9686065, 9827097, 9997134, 10174780, 10290813, 10493367, 10611772, 10813692]
k = int(input())
print(ls[k-1])

Measured memory_bytes: 9376
fun main(args: Array<String>) {
    val (n, k) = readLine()!!.split(' ').map(String::toLong)
    var num = 0.5
    var num2 = 0L
    if (k / 2 > n) {
        println(0)
    } else if (k % 2L == 0L) {
        while (true) {
            num += 1.0
            if (n < num * k) {
                num -= 1.0
                break
            }
        }
        while (true) {
            num2 += 1L
            if (n < num2 * k) {
                num2 -= 1L
                break
            }
        }
        val ceil = Math.ceil(num).toLong()
        println((ceil * ceil * ceil) + (num2 * num2 * num2))
    } else {
        println((n / k) * (n / k) * (n / k))
    }
}

Measured memory_bytes: 37948
from sys import exit, stdin
N = int(stdin.readline().rstrip())
S = [int(stdin.readline().rstrip()) for _ in range(N)]
S.sort()
ans = sum(S)
if ans % 10 != 0:
    print(ans)
    exit()
for i in range(N):
    if (ans-S[i]) % 10 != 0:
        print(ans-S[i])
        exit()
print(0)

Measured memory_bytes: 3060
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys

tenant = [[[0 for r in range(10)] for f in range(3)] for b in range(4)]

n = int(sys.stdin.readline())
for i in range(n):
    b, f, r, v = map(int, sys.stdin.readline().split())
    tenant[b-1][f-1][r-1] += v

ROOM_STR = '{:2}' * 10  # width:2 10 rooms
separator = '#' * 20
for b in range(4):
    for f in range(3):
        print(ROOM_STR.format(*tenant[b][f]))  # unpack list of 10 elements
    if b != 3:
        print(separator)



Measured memory_bytes: 5628
#include <iostream>
#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <cstring>
#include <utility>
#include <vector>
#include <complex>
#include <valarray>
#include <fstream>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <numeric>

#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = Y-1;(X) >= 0;--(X))
#define repa(X,A,Y) for (int (X) = A;(X) <= (Y);++(X))
#define all(X) (X).begin(),(X).end()
#define mod(n, m) (((n)%(m)+(m))%m)
#define fi first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
const int INFINT = 1 << 30;                          // 1.07x10^ 9
const ll INFLL = 1LL << 60;                          // 1.15x10^18
const double EPS = 1e-10;
const int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

const int MAX_N = 100;
int N;
int a[MAX_N];


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

  cin >> N;
  rep(i, N) cin >> a[i];

  int sum = 0;
  rep(i, N) sum += a[i];

  int ans = 0, mi = INFINT;
  rep(i, N) {
    if (abs(N*a[i] - sum) < mi) {
      ans = i; mi = abs(N*a[i] - sum);
    }
  }

  cout << ans << endl;
  return 0;
}


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

#define ll long long
 
using namespace std;
 
int main(){

    ll n;
    vector<ll> v;
    
    ll minv = 1000000000000000;
    int index;


    cin >> n;

    for(int i = 0; i < 5; i++){
        ll tmp;
        cin >> tmp;
        if(minv > tmp){
            minv = tmp;
            index = i;
        }
        v.push_back(tmp);
    }

    ll t;

    if(n % minv == 0){
        t = n / minv;
    }else t = n / minv + 1;

    cout << t + 4 << endl;

 
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
  
int  main(void){
         int h,w,i,j;
          while(1){
          scanf("%d %d",&h,&w);
           if( h==0 && w==0)
              break;
           for(i=1; i<=h; i++){
            for(j=1; j<=w; j++){
              if(i==1 || i==h || j==1 || j==w)
              printf("#");
             else
              printf(".");
             }printf("\n");
            }printf("\n");
           }
            return 0;
}


Measured memory_bytes: 2056
n = STDIN.gets.to_i
matrix = Array.new(n) { Array.new(n, 0) }

n.times do
	node_no, degree, *adj_list = STDIN.gets.split.map(&:to_i)
	degree.times do |i|
		matrix[node_no - 1][adj_list[i] - 1] = 1
	end
end

matrix.each do |adj|
	puts "#{adj.join(" ")}"
end

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

using namespace std;

int main(){
	int i,o,p;
	while ( cin >> i >> o >> p ){
		if (i == o && o == p){
			printf("%d %d %d\n",i,o,p);
		}
		else if (i <= o && o <= p){
			printf("%d %d %d\n",i,o,p);
		}
		else if (i <= p && p <= o){
			printf("%d %d %d\n",i,p,o);
		}
		else if (o <= i && i <= p){
			printf("%d %d %d\n",o,i,p);
		}
		else if (o <= p && p <= i){
			printf("%d %d %d\n",o,p,i);
		}
		else if (p <= o && o <= i){
			printf("%d %d %d\n",p,o,i);
		}
		else if (p <= i && i <= o){
			printf("%d %d %d\n",p,i,o);
		}
	}
	return 0;
}


Measured memory_bytes: 3236
#include <iostream>
#include <algorithm>
using namespace std;
int main(void){
    int a[13];
    for(int i = 0; i < 12; i++){
        cin >> a[i];
    }
    sort(a, a + 12);
    if(a[0] == a[3] && a[4] == a[7] && a[8] == a[11]){
        cout << "yes" << endl;
    }
    else
        cout << "no" << endl;
    
    return 0;
}



Measured memory_bytes: 3156
fn getline() -> String{
	let mut __ret=String::new();
	std::io::stdin().read_line(&mut __ret).ok();
	return __ret;
}


fn main(){
    let s=getline();
    let v:Vec<_>=s.trim().split(' ').collect();
    let n:i32=v[0].parse().unwrap();
    let y:i32=v[1].parse().unwrap();
    let mut a = -1;
    let mut b = -1;
    let mut c = -1;

    for i in 0..n+1{
        for j in 0..n+1-i{
            let k = n-i-j;
            if i*10000  + j*5000 + k*1000 == y{
                a=i;
                b=j;
                c=k;
            }
        }
    }
    println!("{} {} {}",a,b,c);
}

Measured memory_bytes: 4352
#include <iostream>
#include <map>
#include <array>

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

using lli = long long int;
using pii = std::pair<int, int>;

constexpr int theSIZE = 10;
std::array<lli, theSIZE> res;
std::map<pii, int> Counter;

int main(void){
    int H, W, n; scanf("%d%d%d", &H, &W, &n);
    res[0] = H - 2; res[0] *= W - 2;
    REP(i, n){
        int a, b; scanf("%d%d", &a, &b); a--; b--;
        for(int x = -2; x <= 0; ++x) if(a + x >= 0){
            for(int y = -2; y <= 0; ++y) if(b + y >= 0){
                Counter[{a+x, b+y}]++;
            }
        }
    }
    for(auto& itr : Counter) {
        if(itr.first.first < H - 2 and itr.first.second < W - 2){
            res[itr.second]++; res[0]--;
        }
    }
    for(auto ans : res) printf("%lld\n", ans);

    return 0;
}

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

int main() {
 	int n, m, sum = 0;
  	cin >> n >> m;
  	int a[n + 1];
  	for(int i = 1; i <= n; i++) {
     	cin >> a[i];
      	sum += a[i];
    }
  	sort(a + 1, a + 1 + n);
  	int x = sum / (4 * m);
  	int f = 0;
  	if(x * m * 4 == sum)
      	f = 1;
  	bool f1 = true;
  	//cout << "lol" << endl;
  	for(int i = n; i > (n - m); i--) {
      	if(a[i] > x)
          	continue;
      	if(a[i] == x && f == 1)
          	continue;
      	f1 = false;
    }
  	cout << ((f1 == false) ? ("No") : ("Yes")) << endl;
  	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll MOD=1e9+7;
/*
【解法】
A = [1, 2, ..., n] と固定する（求める場合の数は、固定した場合の数の mPn 倍）。B を長さ n の数列とする

ある集合 S \subset {1, ..., n} の上で値が一致する（そのほかにも一致する値のある可能性がある）ような B の場合の数は g(S) = (m-|S|)P(n-|S|) 通り
（まだ決まっていない n-|S| 箇所の値を、使っていない m-|S| 個の値から重複しないように決める）

ある集合 S \subset {1, ..., n} の上でちょうど値が一致する（ S に属さない点 i ではA[i] != B[i] となる）ような
B の場合の数を f(S) 通りとすると、g(S) = \sum_{S\subset T} f(T) となる。

F(S) = f({1, ..., n} \setminus S), G(S) = g({1, ..., n} \setminus S) とおくと、
G(S) = \sum_{T\subset S} F(S) なので、包除原理から F(S) = \sum_{T\subset S} (-1)^|S\setminus T| G(T) が成り立つ。

求めるのは f(\emptyset)
= F({1, ..., n})
= \sum_{T\subset {1, ..., n}} (-1)^|{1, ..., n}\setminus T| G(T)
= \sum_{T\subset {1, ..., n}} (-1)^|{1, ..., n}\setminus T| g({1, ..., n} \setminus T)
= \sum_{T\subset {1, ..., n}} (-1)^|T| g(T)
（ T -> T\setminus {1, ..., n} で置換）
ここで g は size の関数なので g(T) = g(|T|) とおくと、 k 元集合の選び方が nCk 通りなので 
= \sum_{k=0}^n (-1)^k nCk g(k)
= \sum_{k=0}^n (-1)^k n! / (n-k)! / k! * (m-k)! / (m-n)!
となる。

これを高速に計算する。 k == 0 のとき m! / (m-n)! で、

    n! (m-k)!             n! (m-(k-1))!          n-k+1
---------------- == ------------------------ * ---------
(n-k)! k! (m-n)!    (n-(k-1))! (k-1)! (m-n)!   (m-k+1) k

なので、 k がふえるたびに (n-k+1) / (m-k+1) / k 倍すればよい
*/
ll inv_table[500001] = {};
void make_inv_table(int n){
    inv_table[1] = 1;
    for (int i=2; i<=n; ++i){
        // (MOD / i) * i + MOD % i = 0 なので
        // (MOD / i) * i = - (MOD % i)
        // - (MOD / i) * (MOD % i)^(-1) = i^(-1)
        inv_table[i] = inv_table[MOD%i] * (MOD - MOD / i) % MOD;
    }
}

ll npr(ll n, ll r){
    ll ans = 1;
    for(ll i=n-r+1; i<=n; ++i)ans = (ans * i) % MOD;
    return ans;
}

int main()
{
    ll n, m;
    scanf("%lld%lld", &n, &m);

    const ll mpn = npr(m, n);
    ll tmp = mpn;
    ll sum = tmp;
    const ll sign[2] = {1, MOD-1};
    make_inv_table(500000);
    for(int k=1; k<=n; ++k){
        tmp = ((tmp * inv_table[m-k+1]) % MOD * (inv_table[k] * (n-k+1) % MOD)) % MOD;
        sum = (sum + sign[k%2] * tmp) % MOD;
    }
    printf("%lld\n", (sum * mpn) % MOD);
    return 0;
}


Measured memory_bytes: 7684
import javax.swing.plaf.IconUIResource;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.nio.charset.IllegalCharsetNameException;
import java.util.*;
public class Main {
    static long dp[]= new long[2006];
    static long mod=(long) (1e9+7);
    static long mod(long x){
        return ((x%mod+mod)%mod);
    }
    static long add(long a,long b){
        return mod(mod(a)+mod(b));
    }

    static long find(int s){
        if (s==0){
            return 1;
        }
        if (s==1||s==2){
            return 0;
        }

        if (dp[s]!=-1)return dp[s];
        long total=0;
        for (int i=3;i<=s;i++){
            if (s-i>=0){
                total=add(total,find(s-i));
//                total=(total+find(s-i))%mod;
            }
        }
        return dp[s]=total;
    }

     public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
         FastScanner sc = new FastScanner();
         PrintWriter out = new PrintWriter(System.out);
         int n=sc.nextInt();
         Arrays.fill(dp,-1);
         System.out.println(find(n));

     }






    static void sort(int[] a) {
        ArrayList<Integer> l=new ArrayList<>();
        for (int i:a) l.add(i);
        Collections.sort(l);
        for (int i=0; i<a.length; i++) a[i]=l.get(i);
    }
    static void sortReverse(long[] a) {
        ArrayList<Long> l=new ArrayList<>();
        for (long i:a) l.add(i);
//        Collections.sort.(l);
        Collections.sort(l,Collections.reverseOrder());
        for (int i=0; i<a.length; i++) a[i]=l.get(i);
    }

    static class FastScanner {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer("");
        String next() {
            while (!st.hasMoreTokens())
                try {
                    st=new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
        int[] readArray(int n) {
            int[] a=new int[n];
            for (int i=0; i<n; i++) a[i]=nextInt();
            return a;
        }
        long[] readArrayLong(long n) {
            long[] a=new long[(int)n];
            for (int i=0; i<n; i++) a[i]=nextLong();
            return a;
        }
        long nextLong() {
            return Long.parseLong(next());
        }
    }


}

Measured memory_bytes: 35436
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define int long long
using namespace std;

typedef pair<int, int> Pii;

void readint(int N, vector<int> &a);
void readdouble(int N, vector<double> &a);
void readindex(int N, vector<int> &a);



signed main(){

    int N, M, X;
    cin >> N >> M >> X;
    vector<int> A(M);
    readint(M, A);
    vector<int> P(N + 1, 0);
    REP(i, M){
        P[A[i]] = 1;
    }

    int ansl = 0, ansr = 0;

    FOR(i, 0, X){
        ansl += P[i];
    }
    FOR(i, X + 1, N + 1){
        ansr += P[i];
    }

    cout << min(ansl, ansr);


    return 0;
}








void readint(int N, vector<int> &a){
    string s;
    for(int i = 0; i < N - 1; i++){
        getline(cin, s, ' ');
        a[i] = atoi(s.c_str());
    }
    getline(cin, s, '\n');
    a[N - 1] = atoi(s.c_str());
}
void readdouble(int N, vector<double> &a){
    string s;
    for(int i = 0; i < N - 1; i++){
        getline(cin, s, ' ');
        a[i] = atof(s.c_str());
    }
    getline(cin, s, '\n');
    a[N - 1] = atof(s.c_str());
}
void readindex(int N, vector<int> &a){
    string s;
    for(int i = 0; i < N - 1; i++){
        getline(cin, s, ' ');
        a[i] = atoi(s.c_str()) - 1;
    }
    getline(cin, s, '\n');
    a[N - 1] = atoi(s.c_str()) - 1;
}

Measured memory_bytes: 256
while True:
    total= input().split()
    a=int(total[0])
    op = total[1]
    b=int(total[2])
    if op=='?':
        break
    if op=='+':
        print('%d' %(a+b))
    elif op=='-':
        print('%d' %(a-b))
    elif op=='*':
        print('%d' %(a*b))
    else:
        print('%d' %(a/b))


Measured memory_bytes: 5596
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val l = readLine()!!.split(" ").map{it.toInt()}
    var tmp = 0
    for(i in 1 until n - 1){
        if(l[i] == l.subList(i - 1, i + 2).sorted()[1]){
            tmp += 1
        }
    }
    println(tmp)
}

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

#define debug(a) cerr << #a << " = " << (a) << endl; 
#define get(t, i) get<(i)>((t))
#define fst first
#define snd second

template<typename T> ostream& operator<<(ostream& o, const vector<T>& v) {
  int b = 0; for (const auto& a : v) o << (b++ ? " " : "") << a; return o;
}

template<typename T, typename U> ostream& operator<<(ostream& o, const pair<T, U>& p) {
  o << p.fst << ' ' << p.snd; return o;
}

int n, k;
vector<int> A;
int dp[101010];

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  cin >> n >> k;
  A.assign(n, 0);
  for (auto& a : A) cin >> a;

  for (int i = 1; i < n; i++) {
    dp[i] = 1<<30;
    for (int j = 1; j <= k; j++) {
      if (i-j >= 0) {
        dp[i] = min(dp[i], dp[i-j] + abs(A[i] - A[i-j]));
      }
    }
  }

  cout << dp[n-1] << endl;
}



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

int main() {
    int N, M;
    cin >> N >> M;
    int ans = 1;
    for (int i = 1; i * i <= M; i++) {
        if (M % i == 0 && M / N >= i && M - i * (N - 1) > 0 && i > ans) ans = i;
        int num = M / i;
        if (M % num == 0 && M / N >= num && M - num * (N - 1) > 0 && num > ans) ans = num;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256