akhauriyash/Code-Regression huggingface dataset:
S = input()

ind = (len(S) + 1) // 2

left = S[:ind-1]
right = S[ind:]

def check(x):
    if len(x) % 2 == 0:
        ind = len(x) // 2
        if x[:ind] == x[ind:][::-1]:
            return True
        else:
            return False
    else:
        ind = (len(x) + 1) // 2
        if x[:ind-1] == x[ind:][::-1]:
            return True
        else:
            return False

if check(S) and check(left) and check(right):
    print("Yes")
else:
    print("No")


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

//const long double PIL = 3.141592653589793238462643383279502884L;
//const double PI = 3.14159265358979323846;

#define sz(a) int((a).size())
#define all(c) (c).begin(), (c).end()
#define what_is(x) cerr << #x << " is " << x << endl;

using ll = long long;
using ii = pair<int,int>;
using vi = vector<int>;
using vll = vector<long long>;
using vii = vector<pair<int,int>>;

int main() {
	//~ ios::sync_with_stdio(0);
	//~ cin.tie(0);
	int a, b, c;
	cin >> a >> b >> c;
	cout << min(c, b/a) << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = 1; i <= n; i++)
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a,b); }
using P = pair <int, int>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

ll MOD = 1000000007;
ll INF =1<<30;

int main(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    int r = 0,w = 0;
    rep(i,n){
        if(s[i]=='R') r++;
        else w++;
    }
    //cout << r <<' ' <<w <<endl;
    int left = 0,right=0;
    rep(i,r){
        if(s[i]!='R') left++; 
    }
    for(int i = r;i<n;++i){
        if(s[i]=='R') right++;
    }
    //cout << left << ' ' <<right <<endl;
    cout << min(left,right)+abs(left-right) <<endl;
}

Measured memory_bytes: 3724
#include<bits/stdc++.h>
using namespace std;
int main(){
  long long  a,j=0;
  cin>>a;
  for(long long i=1;i<=a;i++){
    if(i%3 == 0 || i%5 == 0){
      continue;
    }
    else{
      j+=i;
    }
  }
  cout<<j<<'\n';
}


Measured memory_bytes: 3604
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+5;
int a[N],n;
ll k;
ll ceil(ll x,ll y) {
    if(x>=0) return x/y;
    return (-x-y-1)/(-y);
}
ll floor(ll x,ll y) {
    if(x>=0) return x/y;
    return -(-x+y-1)/y;
}
ll cal() {
    ll l=-1e18,r=1e18;
    while(l<=r) {
        ll mid=(l+r)>>1,cnt=0;
        for(int i=1;i<=n;i++) {
            if(a[i]==0) {
                if(mid<0) cnt+=n;
            }
            else if(a[i]<0) {
                int x=lower_bound(a+1,a+n+1,ceil(mid,a[i]))-a-1;
                cnt+=x;
            }
            else {
                int x=upper_bound(a+1,a+n+1,floor(mid,a[i]))-a-1;
                cnt+=n-x;
            }
        }
        for(int i=1;i<=n;i++) {
        	if(1LL*a[i]*a[i]>mid) cnt--;
        }
        cnt/=2;
        //printf("%lld %lld\n",mid,cnt);
        if(cnt<k) r=mid-1;
        else l=mid+1;
    }
    return l;
}
int main() {
    scanf("%d%lld",&n,&k);
    k=1LL*(n-1)*n/2+1-k;
    for(int i=1;i<=n;i++) {
        scanf("%d",&a[i]);
    }
    sort(a+1,a+n+1);
    ll ans=cal();
    printf("%lld\n",ans);
    return 0;
}

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

bool solve(string s,string t){
	vector<char> v(128,'?');
	for (int i=0;i<s.size();i++){
		if (v[s[i]]=='?' || v[s[i]]==t[i]) v[s[i]]=t[i];
		else return false;
	}
}

int main(){
	string s,t;
	cin>>s>>t;
	if (solve(s,t) && solve(t,s)) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 1544
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
using namespace std;
#define ll long long
const int mod = 1000000007;
const ll INF = 1000000000000000000;

int main()
{
	int N, M;
	cin >> N >> M;
	if (N == M) cout << "Yes" << endl;
	else cout << "No" << endl;
}


Measured memory_bytes: 256
#include <stdio.h>

unsigned int N;
unsigned long long a[10000];

int fact0(int c) {
    register unsigned int i, j;
    for (i=0; i < N/2 ;i++) {
        if (a[i] % 2 == 0) break;
    }
    if (i == N/2) return c;

    for (j=0; j < N/2 ;j++) {
        a[j] = (i==j?a[i]/2:a[j]*3);
    }
    return fact0(c+1);
}

int fact1(int c) {
    register unsigned int i, j;
    for (i=N/2; i < N ;i++) {
        if (a[i] % 2 == 0) break;
    }
    if (i == N) return c;

    for (j=N/2; j < N ;j++) {
        a[j] = (i==j?a[i]/2:a[j]*3);
    }
    return fact1(c+1);
}

int main() {
    int i;
    scanf("%d", &N);
    for (i=0; i < N ;i++) {
        scanf("%d", &a[i]);
    }
    printf("%d\n", fact1(fact0(0)));
    return 0;
}

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

int main(){

    int N;
    cin >> N;
    vector<int> X(N);
    double sumX = 0;
    rep (i, N){
        cin >> X[i];
        sumX += X[i];
    }

    int P1 = ceil(sumX/N);
    int P2 = floor(sumX/N);
    int ans1 = 0; 
    int ans2 = 0;
    rep (i, N){
        ans1 += pow(X[i] - P1, 2);
        ans2 += pow(X[i] - P2, 2);
    }

    if (ans1 <= ans2) cout << ans1 << endl;
    else cout << ans2 << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <iomanip>	//cout << fixed << setprecision(桁数);

#define debug(x) (#x " : " + to_string(x))
#define debug_cout(x) (cout << #x << " : " << to_string(x) << endl)
#define rep(i, n) for(int i=0, i##_len=(n); i<i##_len; i++)
#define rep1(i, n) for(int i=1, i##_len=(n); i<=i##_len; i++)
#define rrep(i, n) for(int i=(n)-1; i >= 0; i--)
#define rrep1(i, n) for(int i=(n); i > 0; i--)
#define all(x) (x).begin(), (x).end()
#define pair(a, b) make_pair((a), (b));
using namespace std;
using ll = long long;
//#define int long long
template<class T> bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
constexpr int INF = (int)2e9;

/*****/

int n, W;
vector<pair<int, int>> things;

int main()
{
	int N, A, B;
	cin >> N >> A >> B;

	int res = 0;
	if (N * A > B)
		res = B;
	else
		res = N * A;

	cout << res << endl;

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair< ll, ll > Pi;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define rep3(i,i0,n) for(int i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
const ll INF = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}
#define all(x) x.begin(), x.end()
#define mp make_pair
bool compare(Pi a, Pi b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}


bool In_map(ll y,ll x,ll h,ll w){
    if(y<0 || x<0 || y>=h || x>=w){
        return 0;
    }else{
        return 1;
    }
}
const vector<ll> dx{1,0,-1,0};
const vector<ll> dy{0,1,0,-1};
vector<pair<long long, long long> > prime_factorize(long long N) {
    vector<pair<long long, long long> > res;
    for (long long a = 2; a * a <= N; ++a) {
        if (N % a != 0) continue;
        long long ex = 0; // 指数

        // 割れる限り割り続ける
        while (N % a == 0) {
            ++ex;
            N /= a;
        }

        // その結果を push
        res.push_back({a, ex});
    }

    // 最後に残った数について
    if (N != 1) res.push_back({N, 1});
    return res;
}


int main() {
    ll A,B;
    cin >>A>>B;


    
    const auto &res = prime_factorize(gcd(A,B));
  
    cout<<res.size()+1<<endl;


    return 0;
    

}

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

int main(){
    int n;
    cin >> n;
    vector<int> d(n);
    for(int i = 0;i < n;i++)cin >> d.at(i);
    int count = 1;
    sort(d.begin(), d.end());
    for(int i = 1;i < n;i++){
        if(d.at(i - 1) < d.at(i))count++;
    }
    cout << count << endl;
}

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

using namespace std;
#define int long long
#define F first
#define S second
const int N = 1e5 + 10, inf = 1e18;
int dis[N];
vector < pair <int , int> > g[N];

void dijkstra(int v, int t)
{
    fill(dis, dis + N, inf);
    dis[v] = 0;
    priority_queue < pair <int , int> > pq;
    pq.push({0, v});
    while (pq.size()) {
        v = (pq.top()).S; pq.pop();
        if (v == t) return ;
        for (auto e : g[v]) {
            int u = e.F, w = e.S;
            if (dis[v] + w < dis[u]) {
                dis[u] = dis[v] + w;
                pq.push({-dis[u], u});
            }
        }
    }
}


int32_t main()
{
    int n, m; cin >> n >> m;
    for (int i = 2; i <= n; i ++) g[i].push_back({i - 1, 0});
    for (int i = 0; i < m; i ++) {
        int l, r, w; cin >> l >> r >> w;
        g[l].push_back({r, w});
    }
    dijkstra(1, n);
    cout << (dis[n] == inf ? -1 : dis[n]) << "\n";
}


Measured memory_bytes: 10232
#include <iostream>
#include <sstream>

int main() {
    int m, f, r;
    std::stringstream ss;
    while (std::cin >> m >> f >> r) {
        if (m == -1 && f == -1 && r == -1) break;
        else {
            if (m == -1 || f == -1) ss << "F" << std::endl;
            else if (m + f >= 80) ss << "A" << std::endl;
            else if (m + f >= 65) ss << "B" << std::endl;
            else if (m + f >= 50) ss << "C" << std::endl;
            else if (m + f >= 30) {
                if (r >= 50) ss << "C" << std::endl;
                else ss << "D" << std::endl;
            }
            else ss << "F" << std::endl;
        }
    }
    std::cout << ss.str();
    return 0;
}


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

int main() {
  int64_t A,B,K;
  cin>>A>>B>>K;
  if(A>=K){
    cout<<A-K<<" "<<B<<endl;
  }
  else if(A+B>=K){
    cout<<"0"<<" "<<A+B-K<<endl;
  }
  else{
    cout<<"0"<<" "<<"0"<<endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,s,n) for (int i = (s); i < (n); ++i)
#define rrep(i,n,g) for (int i = (n)-1; i >= (g); --i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define len(x) (int)(x).size()
#define dup(x,y) (((x)+(y)-1)/(y))
#define pb push_back
#define Field(T) vector<vector<T>>
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
  int n;
  cin >> n;
  map<int, int> a;
  rep(i,0,n) {
    int ai;
    cin >> ai;
    a[ai]++;
  }
  int k = 0;
  for (auto i = a.begin(); i != a.end(); ++i) {
    int p = i->first, q = i->second;
    if (p > q) k += q;
    else k += q - p;
  }
  cout << k << endl;
  return 0;
}

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

int p[100006], l[100006];

struct BIT {
	int N; vector<int> bit;
	void init(int n) {
		N = n;
		bit.resize(n + 1);
	}
	int sum(int i) {
		int s = 0;
		while (i > 0) {
			s += bit[i];
			i -= i&-i;
		}
		return s;
	}
	void add(int i, int x) {
		while (i <= N) {
			bit[i] += x; i += i&-i;
		}
	}
};
BIT B;
signed main() {
	int n; cin >> n;
	rep(i, n)cin >> p[i];
	rep(i, n)cin >> l[i];
	rep(i, n - 1)p[i + 1] += p[i];
	B.init(n + 1);
	rep(i, n)B.add(i + 1, 1);

	vector<int>V;
	rep(i, n)V.push_back(p[i]);
	sort(V.begin(), V.end());
	for (int i = n - 1; i > 0; i--) {
		V[i] = V[i] - V[i - 1];
	}
	rep(i, n) {
		if (l[i] > V[i]) {
			cout << -1 << endl; return 0;
		}
	}

	vector<P>V2;
	rep(i, n)V2.push_back(P(p[i], i));
	sort(V2.begin(), V2.end());
	int res = 0;
	rep(i, n) {
		int pos = V2[i].second;
		res += B.sum(pos);
		B.add(pos + 1, -1);
	}
	cout << res << endl;
}


Measured memory_bytes: 8088
import numpy as np

n = int(input())
a = np.array(input().split(), dtype=np.int32)
b = np.array(input().split(), dtype=np.int32)

ans = 0
mod = 1
for k in range(30):
    mod <<= 1
    t = mod >> 1
    bb = np.sort(b % mod)
    aa = a % mod
    l1, r1, l2, r2 = (np.searchsorted(bb, v - aa).sum() for v in (t, 2*t, 3*t, 4*t))
    cnt = r1 - l1 + r2 - l2

    if cnt % 2:
        ans += t

print(ans)


Measured memory_bytes: 38860
#include<bits/stdc++.h>
#define LL long long
#define clr(x,i) memset(x,i,sizeof(x))
using namespace std;
const int N=100005;
int n,a[N];
map<int,int> mp;
LL ans,w,h; 
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	  scanf("%d",&a[i]),mp[a[i]]++;
	mp[0]++;
	map<int,int>::iterator it;
	it=mp.end(); it--;
	while(it!=mp.begin()&&it->second<2) it--;
	w=it->first; it->second-=2;
	while(it!=mp.begin()&&it->second<2) it--;
	h=it->first;
	ans=w*h;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 5376
#include <stdio.h>

#define MAX 500000
#define SENTINEL 2000000000

int L[MAX/2+2], R[MAX/2+2];
int cnt;

void merge(int A[],int n,int left, int mid, int right) {
  int i, j, k;
  int n1 = mid -left;
  int n2 = right - mid;
  for(i=0;i<n1;i++) L[i] = A[left + i];
  for(i=0;i<n2;i++) R[i] = A[mid + i];
  L[n1] = R[n2] = SENTINEL;
  i=0, j=0;
  for(k=left; k<right; k++) {
    cnt++;
    if(L[i]<=R[j]) {
      A[k] = L[i++];
    } else {
      A[k] = R[j++];
    }
  }
}

void mergeSort(int A[],int n,int left,int right) {
  int mid;
  if(left+1 < right) {
    mid = (left+right) / 2;
    mergeSort(A,n,left,mid);
    mergeSort(A,n,mid, right);
    merge(A,n,left,mid,right);
  }
}

int main(void) {
  int A[MAX], n, i;
  cnt = 0;

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

  mergeSort(A, n, 0, n);
  for(i=0;i<n;i++) {
    if(i) printf(" ");
    printf("%d",A[i]);
  }
  printf("\n%d\n",cnt);

  return 0;
}


Measured memory_bytes: 5616
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <map>
#define rep(i, N) for (int i = 0; i < (int)N; i++)
using namespace std;
typedef long long ll;
const ll LLINF = 9223372036854775807;
const ll MOD = 1000000007;
const int S_MAX = pow(10,5);

string S;
vector<vector<int>> dp(S_MAX+1, vector<int>(4, -1));

ll dfs(int n, int abc) {
  if (dp[n][abc]!=-1) return dp[n][abc];
  if (n==0) return dp[n][abc] = abc==0 ? 1 : 0;
  ll result = dfs(n-1, abc);
  if (S[n-1]=='A') { if (abc==1) result += dfs(n-1,0); }
  if (S[n-1]=='B') { if (abc==2) result += dfs(n-1,1); }
  if (S[n-1]=='C') { if (abc==3) result += dfs(n-1,2); }
  if (S[n-1]=='?') { 
    if (abc!=0) result += dfs(n-1,abc-1);
    result += dfs(n-1, abc) * 2;
  }
  return dp[n][abc] = result % MOD;
}

int main() {
  cin >> S;
  dfs(S.length(), 3);
  // rep(i,S.length()+1) { rep(j,4) cout << dp[i][j] << " "; cout << endl; }
  cout << dp[S.length()][3] << endl;
  return 0;
}

Measured memory_bytes: 12160
N, T = map(int,input().split())
A = list(map(int,input().split()))
ans = 0
pre = A[0]
left = T
for i in range(1, N):
    a = A[i]
    if a - pre < T:
        ans += a - pre
        left = T
    else:
        ans += left
        left = T
    pre = a

ans += left
print(ans)

Measured memory_bytes: 26836
#include <bits/stdc++.h>
#define rep(i,a,b) for (i=a;i<b;i++)
#define rep2(i,a,b) for (i=a;i>=b;i--)
#define mod 1000000007
#define mod2 998244353
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define INF  1e9+5
#define f first
#define s second
#define endl '\n'
#define ll long long int
#define ii pair <int,int>
#define pll pair <ll,ll>
#define vi vector <int>
#define vl vector <ll>
#define vvi vector < vi >
#define vii vector < ii >
#define vpl vector < pll >
#define vvii vector < vii >
#define vll vector < ll >
#define vb  vector <bool>
#define pb push_back
#define mk make_pair
#define eb emplace_back
#define pg priority_queue<ll, vector<ll>, greater<ll>>
#define pq priority_queue<ll>
#define sz(a) a.size()
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define cset(a) __builtin_popcountll(a)
#define FILL(a, b, T) fill_n((T *)a, sizeof(a) / sizeof(T), b)
#define debug(x) cerr << #x << " is " << x << endl;
using namespace std;
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
#define pis pair<ll,pll>
#define mex 100005
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << " = " << a << endl;
    err(++it, args...);
}
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
 
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
// unordered_map<long long, int, custom_hash> safe_map;
// FOR VIEWERS, CODE STARTS HERE

int main()
{
    FIO;
    ll t, q, n, m, prev, maxx,  i, j, k1, k2, k3, k, x, y, flag, sum, cnt, ans;
    cin>>n>>m;
    cout<<min(m - n%m, n%m)<<endl;
} 

Measured memory_bytes: 256
parseInt(x)=parse(Int,x)
parseMap(x::Array{SubString{String},1})=map(parseInt,x)

function main()
	q = readline() |> parseInt
	for i in 1:q
		a,b = readline() |> split |> parseMap
		temp = min(a,b)
		b = max(a,b)
		a = temp
		c = ceil(Int, sqrt(a*b))-1
		if a == b
			println(2*a-2)
		elseif a+1 == b
			println(2*a-2)
		elseif c*(c+1) >= a*b
			println(2*c-2)
		else
			println(2*c-1)
		end
	end
end

main()


Measured memory_bytes: 111628
f=lambda:map(int,input().split())
h,w,n=f()
c=[0]*10
c[0]=(h-2)*(w-2)
d={}
while n:
 n-=1;x,y=f()
 for i in range(9):
  a=(x+i%3,y+i//3)
  if h>=a[0]>2<a[1]<=w:d[a]=d.get(a,0)+1;c[d[a]-1]-=1;c[d[a]]+=1
print(*c)

Measured memory_bytes: 166480
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define INF 1<<30
#define LINF 1LL<<60

int main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
	ll N; cin >> N;
	string s, t; cin >> s >> t;
	ll ans = 2 * N;
	for (int i = 0; i < N;i++) {
		if (s[i] != t[0]) continue;
		bool f = false;
		for (int j = i; j < N;j++) {
			if (s[j] != t[j - i]) {
				f = true;
				break;
			}
		}
		if (f) continue;
		ans = min(ans, N + i);
	}
	cout << ans << endl;
	return 0;
}

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 pii = pair<int, int>;

int main() {
	ll k, a, b;
	cin >> k >> a >> b;
	ll ans;
	if (a + 2 <= b) {
		ll q = (k - a + 1) / 2;
		ll r = k - (a - 1 + 2 * q);
		ans = a + (b - a) * q + r;
	}
	else {
		ans = k + 1;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3636
// Sky's the limit :)
#include <bits/stdc++.h>
using namespace std;
#define int long long

// Nice problem.. Started simulating the answer, whereas the correct answer was binary serch
signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int T = 1; 
    // cin >> T; 
    while (T--) {
        int n, k;
        cin >> n >> k;
        vector<int> a(n);
        for (auto && x : a)
            cin >> x;

        auto check = [&] (int x) {
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                if (x > 0)
                    cnt += (a[i] - 1) / x;
                else
                    cnt += a[i];
            }
            return cnt;
        };

        int lo = 0, hi = 1e10, lst = 1;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            cerr << mid << ' ' << check(mid) << '\n';
            if (check(mid) <= k) {
                lst = mid;
                hi = mid - 1;
            }
            else
                lo = mid + 1;
        }

        cout << max(lst, 1LL) << '\n';
    }
    
    return 0;
}



Measured memory_bytes: 4748
#include<bits/stdc++.h>
using namespace std;
#define ran 100010
int a[ran],b[ran],la,lb;
int add(int x,int y){
	return x+y+min(x,y);
}
int main(){
	int n,x,k;
	for(scanf("%d%d",&n,&k); n--;){
		scanf("%d",&x);
		if(x < 0)a[la++] = -x;else
			b[lb++] = x;
	}
	sort(a,a+la);
	sort(b,b+lb);
	int res = (int)2e9;
	for(int i=0; i<=la; i++){
		int i2 = k-i;
		if(i2 >= 0 && i2 <= lb)
			res = min(res, add((i==0?0:a[i-1]),(i2==0?0:b[i2-1])));
	}
	printf("%d\n",res);
	return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
LL n,k,a[N];
int main() {
  ios::sync_with_stdio(false);
  cin>>k>>n;
  for(int i=1;i<=n;i++)cin>>a[i];
  sort(a+1,a+1+n);
  LL ans=a[n]-a[1];
  for(int i=1;i<n;i++){
    ans=min(ans,k-(a[i+1]-a[i]));
  }
  cout<<ans<<'\n';
  return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    bool x=1;
    cin>>s;
    for(int i=0;i<s.size();i++)
    {
        if((i%2)&&s[i]=='R')
            x=0;
        if((i%2==0)&&s[i]=='L')
            x=0;
    }
    if(x) cout<<"Yes";
    else cout<<"No";

}


Measured memory_bytes: 256
x=[0]*100000
y=[0]*100000
ct=-1
while True:
    ct+=1
    x[ct],y[ct]=map(int,raw_input().split())
    if x[ct]==y[ct]==0:
        break
    else:
        continue
for i in xrange(ct):
    if x[i]>=y[i]:
        print y[i],x[i]
    else:
        print x[i],y[i]
        

Measured memory_bytes: 7756
# -*- coding: utf-8 -*-
n = int(input())
a = [int(i) for i in input().split()]

ans = 0
count = [0 for _ in range(n)]
j = 0
for i in range(n - 1):
    if a[i] == a[i + 1]:
        count[j] += 1
    if a[i] != a[i + 1]:
        count[j] += 1
        j += 1
count[j] += 1
#print(count)

for i in count:
    ans += i // 2
print(ans)


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

int main(){
    int a,b,c; cin >> a >> b >> c;
    if(c>=a && c<=b) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 3644
#include<bits/stdc++.h>
using namespace std;
int main(){
    long long a,b;
    cin>>a>>b;
    a--;
    long long tmp=a;
    if(tmp&1)
        tmp=0;
    long long tot=a;
    if(tot%4==1||tot%4==2)
        tot=1;
    else
        tot=0;
    long long tt=tmp+tot;
    long long ttmp=b;
    if(ttmp&1)
        ttmp=0;
    long long ttot=b;
    if(ttot%4==1||ttot%4==2)
        ttot=1;
    else
        ttot=0;
    long long ttt=ttmp+ttot;
    long long ans=tt^ttt;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
# edpc e dp

import itertools
from math import factorial
import sys
import heapq
from collections import Counter
from collections import deque
from fractions import gcd
from functools import reduce

sys.setrecursionlimit(4100000)
INF = 1 << 60
MOD = 10 ** 9 + 7

# ここから書き始める
N, W = map(int, input().split())
w = [0 for _ in range(N)]
v = [0 for _ in range(N)]
for i in range(N):
    w[i], v[i] = map(int, input().split())
dp = [[0 for j in range(W + 1)] for i in range(N)]
for i in range(W + 1):
    if i == w[0]:
        dp[0][i] = v[0]
    else:
        dp[0][i] = 0
for i in range(1, N):
    for j in range(W + 1):
            dp[i][j] = dp[i - 1][j]
            if j >= w[i]:
                dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i])
ans = -INF
for i in range(W + 1):
    ans = max(ans, dp[-1][i])
print(ans)


Measured memory_bytes: 179772
class in{struct It{int it;const bool rev;explicit constexpr It(int it_, bool rev=false):it(it_),rev(rev){}int operator*(){return it;}bool operator!=(It& r){return it!=r.it;}void operator++(){rev?--it:++it;}};const It i,n;public:explicit constexpr in(int n):i(0),n(n<0?0:n){}explicit constexpr in(int i,int n):i(i,n<i),n(n){}const It& begin(){return i;}const It& end(){return n;}};
 
#include <iostream>
#include <vector>
#include <string>
#include <functional>
using namespace std;
const int INF = 1e9;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, m;
    while(cin >> n >> m && n) {
        vector<int> t(m);
        for(int& x : t) {
            string s;
            cin >> s;
            int k = 1;
            for(char c : s)
                x += (c - '0') * k, k *= 2;
        }
        vector<vector<int>> dp(1 << n, vector<int>(1 << n, -1));
        function<int(int, int)> dfs = [&](int s1, int s2) {
            int& res = dp[s1][s2];
            if(res != -1) return res;
            res = INF;
            int cnt = 0;
            for(int x : t) if((s1 & x) == s2) ++cnt;
            if(cnt <= 1) return res = 0;
            for(int i : in(n)) {
                if((1 << i) & s1) continue;
                int ns = s1 | (1 << i);
                res = min(res, max(dfs(ns, s2 | (1 << i)), dfs(ns, s2)) + 1);
            }
            return res;
        };
        
        cout << dfs(0, 0) << endl;
    }
    return 0;
}

Measured memory_bytes: 19180
#define LOCAL
#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second	
#define db 0
#define EPS (1e-7)    //0.0000001 the value
#define PI (acos((ld)-1.0))
#define MAXN (300006)
#define ll long long int 
#define ld long double
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
#define FOR(ii, ss, ee) for(ll ii = (ss); ii < (ll)(ee); ++ii)
#define space " "
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ((ll)x.size())
#define ph push
#define btinpct(x) __builtin_popcountll((x))
#define MSB(bm) ((bm==0)?-1:(63-__builtin_clzll((bm))))
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
typedef pair <ll, ll> pi;
typedef pair <ll, pi> spi;
typedef pair <pi, pi> dpi;
inline ll rand(ll x, ll y) { ++y; return (rng() % (y-x)) + x; } //inclusivesss
string to_string(char c) {string s(1,c);return s;}string to_string(bool b){return (b ? "true" : "false");}template <typename A, typename B>string to_string(pair<A, B> p) {return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}template <typename A>string to_string(A v) {bool first = true;string res = "{";for (const auto &x : v) {if (!first) {res += ", ";}first = false;res += to_string(x);}res += "}";return res;}void degug_out() { cerr << endl; }template <typename Head, typename... Tail>void degug_out(Head H, Tail... T) {cerr << " " << to_string(H);degug_out(T...);}inline ll gcd(ll a,ll b){if(a>b)swap(a,b);if(a==0)return b;return gcd(b%a,a);}
#ifdef LOCAL
// #define degug(...) cerr << "[" << #__VA_ARGS__ << "]:", degug_out(__VA_ARGS__)
#else
// #define degug(...) 663
#define cerr if(0)cout
#endif

const ll MOD=1e9+7;
void add(ll &x,ll y) { x%=MOD, y%=MOD; x+=y; if(x<0) x+=MOD; else x%=MOD; }
ll mult(ll x,ll y){ return (x%MOD * (y%MOD))%MOD; }

ll dp[52][52][52*52];
int main()
{
	FAST
	ll n,K; cin>>n>>K;
	dp[0][0][0]=1;
	FOR(i,1,n+1) FOR(j,0,n+1) FOR(k,0,K+1) if(k-2*j >= 0) { // i th pair, j unmatched, k oddness
		add(dp[i][j][k],dp[i-1][j][k-2*j]); // match the two name appearance
		if(j>0) add(dp[i][j][k],dp[i-1][j-1][k-2*j]); // don't match
		add(dp[i][j][k],(j+1)*(j+1)*dp[i-1][j+1][k-2*j]); // match both
		add(dp[i][j][k],2*j*dp[i-1][j][k-2*j]); // match one
	}
	cout<<dp[n][0][K];
}


Measured memory_bytes: 55168
import sys
sys.setrecursionlimit(10**5)


class unionFind:
    parent = []
    nums = []

    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.nums = [1]*n

    def root(self, x):
        if self.parent[x] == x:
            return(x)
        else:
            self.parent[x] = self.root(self.parent[x])
            return(self.parent[x])

    def same(self, x, y):
        x, y = x-1, y-1
        return(self.root(x) == self.root(y))

    def unite(self, x, y):
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            self.nums[y] += self.nums[x]
            self.nums[x] = 0
            return


N, M = map(int, input().split())
G = unionFind(N)
ans = [0]*M
ab = [tuple(map(int, input().split())) for i in range(M)]

tmp = (N * (N-1)) // 2
for i, x in enumerate(reversed(ab)):
    a, b = x[0], x[1]
    ans[M-1-i] = tmp
    a = G.root(a-1)
    b = G.root(b-1)
    if a == b:
        continue
    else:
        tmp -= G.nums[a] * G.nums[b]
        G.parent[a] = b
        G.nums[b] += G.nums[a]
        G.nums[a] = 0


for i in range(M):
    print(ans[i])


Measured memory_bytes: 37268
#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 1001001001
#define LINF 1001001001001001001
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define bit(n) (1LL<<(n))
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> LLP;

int main() {
  
  ll N, X, M;
  cin >> N >> X >> M;


  ll k = 0;
  vector<ll> count(M, -1);
  vector<ll> sum;
  count[X] = k;
  sum.push_back(X);

  k++;
  while (true) {
    X *= X;
    X %= M;
    if (count[X] >= 0) break;
    count[X] = k;
    sum.push_back(sum[k - 1] + X);
    k++;
    if (k == N) {
      cout << sum[k - 1] << endl;
      return 0;
    }
  }

  ll ans = sum[count[X]];
  ll totalSum = sum[k - 1] + X;
  ll loopLength = k - count[X];
  ll loopSum = totalSum - sum[count[X]];
  N -= count[X] + 1;

  ll loopCount = N / loopLength;
  ans += loopCount * loopSum;
  N -= loopCount * loopLength;
  while (N > 0) {
    X *= X;
    X %= M;
    ans += X;
    N--;
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 4668
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var lines = input.split('\n');



if(lines.length > 200) {
	console.log("Invalid dataset size. Dataset size is "+lines.length+" but must be <= 200");
} else {
	for (var i = 0; i < lines.length; i++) {
		var line = lines[i].trim();
	    if (line == '') break;
	    var vals = line.split(' ').map(function(i){return +i;});
	    if(vals.length != 2 || isNaN(vals[0])|| isNaN(vals[1]) || vals[0] < 0 || vals[0] > 1000000 || vals[1] < 0 || vals[1] > 1000000) {
	    	console.log("invalid dataset: "+line+ ". Use 0 <= a, b <= 1,000,000");
	    } else {
	    	var a = vals[0] + vals[1];
	    	var str = a + '';
	    	console.log(str.length);
		}
	}
}

Measured memory_bytes: 16104
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int MAXN = 1e3 + 5;
int n, m, qx, qy, zx, zy;
char s[MAXN][MAXN];
int vis[MAXN][MAXN];
int move_1_x[10] = {0,1,0,-1,0};
int move_1_y[10] = {0,0,1,0,-1};
struct node{
	int x,y,time;
	node(){}
	node(int X,int Y,int TIME){x = X,y = Y,time = TIME;}
	bool operator < (node Y) const {return time > Y.time;}
};
priority_queue<node> Q;
bool check(int x,int y,int time) {
	if(x < 1 || y < 1 || x > n || y > m || vis[x][y] <= time || s[x][y] == '#')
	return false;
	return true;
}
void bfs() {
	int Time = 0x3f3f3f3f;
	memset(vis,0x3f,sizeof(vis));
	Q.push(node(qx, qy, 0));
	vis[qx][qy] = 0;
	while(!Q.empty()) {
		node f = Q.top();
		Q.pop();
		for(int i = 1;i <= 4;i ++) {
			int nx = f.x + move_1_x[i];
			int ny = f.y + move_1_y[i];
			int time = f.time;
			if(check(nx, ny, time)) {
				vis[nx][ny] = time;
				if(nx == zx && ny == zy) {
					Time = min(Time,time);
				}
				Q.push(node(nx,ny,time));
			}
		}
		for(int i = -2;i <= 2;i ++) {
			for(int j = -2;j <= 2;j ++) {
				if(i == 0 && j == 0)
				continue;
				int nx = f.x + i;
				int ny = f.y + j;
				int time = f.time + 1;
				if(check(nx, ny, time)) {
					vis[nx][ny] = time;
					if(nx == zx && ny == zy) {
						Time = min(Time,time);
					}
					Q.push(node(nx,ny,time));
				}
			}
		}
	}
	if(Time == 0x3f3f3f3f) {
		printf("-1");
	}
	else {
		printf("%d",Time);
	}
}
int main() {
	scanf("%d %d %d %d %d %d", &n, &m, &qx, &qy, &zx, &zy);
	for(int i = 1;i <= n;i ++) {
		scanf("\n");
		for(int j = 1;j <= m;j ++) {
			scanf("%c",&s[i][j]);
		}
	}
	bfs();
	return 0;
}

Measured memory_bytes: 8692
#include <stdio.h>
int main(){
    int c,i,a[26]={};
    while((c=getchar())!=EOF){
        a[c-97]++;
        if(a[c-97]==2){
            printf("no");
            return 0;
        }
    }
    for(i=0;i<26;i++){
        if(a[i]>=2){
            printf("no");
            return 0;
        }
    }
    printf("yes");
    return 0;
    
}


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

int gcd(int a, int b) {
int r;
  if(a<b) a=a+b, b=a-b, a=a-b;
  r = a % b;
  while(r>0) a=b, b=r, r=a%b;
  return b;
}

int main(){
int A, B, C;
  
  cin >> A >> B >> C;
  
  if(C % gcd(A,B) == 0) cout << "YES" << endl;
  else cout << "NO" << endl;

  return 0;
}

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

const int MIN = -2147483647;

using type = long long;

using namespace std;

type * vec;
int n;
long long ans = 0;

bool check_mon_up(type * start, type * end)
{
	if (end - start <= 1)
		return true;
	
	for (auto i = start; i < end - 1; i++)
		if (*i >= *(i + 1))
			return false;
	return true;
}

bool chec_mon_do(type * start, type * end)
{
	if (end - start <= 1)
		return true;

	for (auto i = start; i < end - 1; i++)
		if (*i <= *(i + 1))
			return false;
	return true;
}

type * m_find_max(type * start, type * end)
{
	int max = MIN;
	type * numb = nullptr;
	for (type * i = start; i < end; i++)
		if (max < *i) max = *i, numb = i;
	return numb;
}

void m_find_two_max(type * start, type * end, type *& max, type *& tax)
{
	int mm = MIN, mt = MIN;
	for (type * i = start; i < end; i++)
	{
		if (*i > mm)
		{
			mt = mm;
			mm = *i;
			tax = max;
			max = i;
		}
		else if (*i > mt)
		{
			mt = *i;
			tax = i;
		}
	}
}

void m_find_tax(type * start, type * end, type * max, type *& tax)
{
	int mm = *max, mt = MIN;
	for (type * i = start; i < end; i++)
		if (*i > mt)
			if (i != max)
			{
				tax = i;
				mt = *i;
			}
}

void fu(type * start, type * end, type * max)
{
	if (end - start == 1)
		return;
	type * tax = 0;
	m_find_tax(start, end, max, tax);
	if (tax == max)
		return;
	if (tax > max)
	{
		ans += (*tax) * (max - start + 1) * (end - tax);
		fu(start, tax, max);
	}
	else
	{
		ans += (*tax) * (tax - start + 1) * (end - max);
		fu(tax + 1, end, max);
	}
	return;
}

void func(type * start, type * end)
{
	if (end - start <= 1)
		return;
	if (end - start == 2)
	{
		ans += min(*(end - 1), *start);
		return;
	}
	if (check_mon_up(start, end))
	{
		for (int i = 0; i < end - start - 1; i++)
			ans += (*(start + i)) * (i + 1);
		return;
	}
	if (chec_mon_do(start, end))
	{
		for (int i = 1; i < end - start; i++)
			ans += (*(start + i)) * (end - start - i);
		return;
	}
	type * max = m_find_max(start, end);
	fu(start, end, max);
	func(start, max);
	func(max + 1, end);
	return;
}

int main()
{
	cin >> n;
	vec = new type[n];
	type * const start = vec;
	type * const end = vec + n;
	for (type * i = start; i < end; i++)
		scanf("%lld", i);
	func(start, end);
	cout << ans;
	//system("pause");
	return 0;
}

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

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x)  cerr << #x << " = " << x << endl
using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ld PI = 3.14159265359;

const ll MOD = (ll) 1e9 + 7;
const ll MAXN = (ll) 1e5 + 10;
const ll INF = (ll) 2242545357980376863;
const ld EPS = (ld) 1e-12;

ll con(str s){
	if(s == "Male") return 1;
	if(s == "Female") return 2;
	return 0;
}

ll ask(ll x){
	cout << x << endl;
	str ans;
	cin >> ans;
	ll c = con(ans);
	if(c == 0) exit(0);
	return c;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n;
	cin >> n;
	ll fs = ask(0);
	ll la = ask(n - 1);
	
	ll l = 0;
	ll r = n - 1;
	ll mid, res;
	while(l + 1 < r){
		mid = (l + r) / 2;
		res = ask(mid);
		if((fs + l + res + mid) % 2 == 1){
			la = res;
			r = mid;
		} else {
			fs = res;
			l = mid;
		}
	}
	
	return 0;
}


/*

                                 ____              ,----..               ,----..
   ,---,                       ,'  , `.           /   /   \             /   /   \
  '  .' \                   ,-+-,.' _ |          /   .     :           /   .     :
 /  ;    '.              ,-+-. ;   , ||         .   /   ;.  \         .   /   ;.  \
:  :       \            ,--.'|'   |  ;|        .   ;   /  ` ;        .   ;   /  ` ;
:  |   /\   \          |   |  ,', |  ':        ;   |  ; \ ; |        ;   |  ; \ ; |
|  :  ' ;.   :         |   | /  | |  ||        |   :  | ; | '        |   :  | ; | '
|  |  ;/  \   \        '   | :  | :  |,        .   |  ' ' ' :        .   |  ' ' ' :
'  :  | \  \ ,'        ;   . |  ; |--'         '   ;  \; /  |        '   ;  \; /  |
|  |  '  '--'          |   : |  | ,             \   \  ',  /          \   \  ',  /
|  :  :                |   : '  |/               ;   :    /            ;   :    /
|  | ,'                ;   | |`-'                 \   \ .'              \   \ .'
`--''                  |   ;/                      `---`                 `---`
                       '---'

*/




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

int main(){
  int n,i,j,l,r,x;
  cin >> n;
  vector<int> a(n),b(n),ca(n,0),cb(n,0);
  for(i=0;i<n;i++){
    cin >> a.at(i);
    ca.at(a.at(i)-1)++;
  }
  for(i=0;i<n;i++){
    cin >> b.at(i);
    cb.at(b.at(i)-1)++;
  }
  
  for(i=0;i<n;i++){
    if(ca.at(i)+cb.at(i)>n){
      cout << "No" << endl;
      return 0;
    }
  }
  
  i=0;
  j=0;
  
  while(i<n){
    if(a.at(i)==b.at(i)){
      l=i;
      x=a.at(l);
      while(i<n&&a.at(i)==x&&b.at(i)==x){
        i++;
      }
      r=i;
      j=0;
      for(i=l;i<r;i++){
        while(a.at(j)==x||b.at(j)==x){
          j++;
        }
        swap(b.at(i),b.at(j));
      }
      i=r;
    }else{
      i++;
    }
  }
  
  cout << "Yes" << endl;
  for(i=0;i<n;i++){
    cout << b.at(i);
    if(i==n-1){
      cout << endl;
    }else{
      cout << " ";
    }
  }
}

Measured memory_bytes: 6416
#include <bits/stdc++.h>
#include <random>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using Pt = pair<int, int>;

namespace
{
	struct modint
	{
		static constexpr ll MOD = 1000000007;
		ll x_;
		modint() : x_(0) {}
		modint(ll x) : x_(x% MOD) {}
		modint& operator+=(const modint& src)
		{
			if ((x_ += src.x_) >= MOD)
				x_ -= MOD;
			return *this;
		}
		modint& operator-=(const modint& src)
		{
			if ((x_ += MOD - src.x_) >= MOD)
				x_ -= MOD;
			return *this;
		}
		modint& operator*=(const modint& src)
		{
			(x_ *= src.x_) %= MOD;
			return *this;
		}

		modint& operator/=(const modint& src)
		{
			return (*this) *= src.inv();
		}
		modint inv() const
		{
			return pow(MOD - 2);
		}
		modint pow(ll t) const
		{
			if (t == 0)
				return 1;
			modint a = pow(t >> 1);
			a *= a;
			if (t & 1)
				a *= *this;
			return a;
		}
	};
}

int main()
{
	ll MOD = 1000000007;
	int N;
	cin >> N;
	vl A(N);
	for (auto& x : A)
		cin >> x;
	modint sum = 0;
	modint sqSum = 0;
	for (int i = 0; i < N; ++i)
	{
		sum += A[i];
		ll x = A[i] * A[i];
		x %= MOD;
		sqSum += x;
	}
	modint sumSq = sum;
	sumSq *= sum;
	sumSq -= sqSum;
	sumSq /= 2;
	cout << sumSq.x_ << endl;
	return 0;
}


Measured memory_bytes: 4768
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MD=1e9+7;
const int M=22;
int mat[21][21],n;
int dp[(1<<M)];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<n;j++)
		scanf("%d",&mat[i][j]);
	}
	dp[0]=1;
	for(int msk=1;msk<(1<<n);msk++)
	{
		int cnt=__builtin_popcount(msk);
		for(int j=0;j<n;j++)
		{
			if(mat[cnt][j] && (msk&(1<<j)))
			dp[msk]=(dp[msk]+dp[msk^(1<<j)])%MD;
		}
	}
	printf("%d",dp[(1<<n)-1]);
	return 0;
}

Measured memory_bytes: 10496
import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

def main():
    N = I()
    S = _S()
    print("Yes" if S[:int(len(S)/2)]==S[int(len(S)/2):] else "No")

main()



Measured memory_bytes: 27092
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    int n, a[102] = {}, z = 0;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) for (int j = 0; j < i; j++) for (int k = 0; k < j; k++) if (a[i] != a[j] && a[j] != a[k] && a[k] != a[i] && a[i] + a[j] > a[k] && a[j] + a[k] > a[i] && a[k] + a[i] > a[j]) z++;
    cout << z;
}


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

#define int long long

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

signed main() {
    int N;
    cin >> N;
    int a[N] = {};
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }
    sort(a, a + N);
    int ans = 0;
    int cur = a[0], kosuu = 0;
    for (int i = 0; i < N; i++) {
        if (cur != a[i]) {
            if (kosuu < cur) {
                ans += kosuu;
            } else {
                ans += kosuu - cur;
            }
            cur = a[i];
            kosuu = 1;
        } else {
            kosuu++;
        }
    }
    if (kosuu < cur) {
        ans += kosuu;
    } else {
        ans += kosuu - cur;
    }
    cout << ans << endl;
    return 0;
}


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

int N;
double p[3009];
double dp[3009][3009];

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

    dp[0][0] = 1;

    for(int i = 0; i < N; i++) {
        // j > i となることはないので、このような条件式にしている。
        // j <= N でも構わない。
        for(int j = 0; j <= i; j++) {
            dp[i + 1][j + 1] += dp[i][j] * p[i];
            dp[i + 1][j] += dp[i][j] * (1 - p[i]);
        }
    }

    double res = 0;
    for(int j = (N + 1) / 2; j <= N; j++)
        res += dp[N][j];

    cout << fixed << setprecision(10) << res << endl;

    return 0;
}

Measured memory_bytes: 69120
h, w = [int(i) for i in input().split()]
s = [['.' for j in range(w+2)] for i in range(h+2)]

for i in range(1, h+1):
    line = input()
    for j in range(1, w+1):
        s[i][j] = line[j-1]

flag = True

for i in range(1, h+1):
    for j in range(1, w+1):
        if s[i][j] == '#':
            if s[i-1][j] == '#' or s[i+1][j] == '#' or s[i][j-1] == '#' or s[i][j+1] == '#':
                pass
            else:
                flag = False
                break

if flag:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 3064
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
#define repl(i, l, r) for (ll i = l; i < r; i++)
#define rep(i, n) repl(i, 0, n)
const ll MOD = 1000000007;
const ll MAX = 1100000;

ll fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	repl(i, 2, MAX) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}
ll COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 or k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
int main() {
	COMinit();
	ll n, k;
	cin >> n >> k;
	ll a[n];
	rep(i, n) cin >> a[i];
	sort(a, a + n);
	ll M = 0, m = 0;
	rep(i, n) {
		M += a[i] * COM(i, k - 1);
		m += a[i] * COM(n - 1 - i, k - 1);
		M %= MOD, m %= MOD;
	}
	cout << (M - m + MOD) % MOD << endl;
	return 0;
}

Measured memory_bytes: 26752
# -*- coding: utf-8 -*-
"""
Created on Sun Nov 19 13:32:42 2017

@author: yamakoshi
"""

n = int(input())

seq = {}
a1n = map(int, input().split())
for a in a1n:
    if a not in seq:
        seq[a] = 1
    else:
        seq[a] += 1

ret = 0
for a in seq:
    if not seq[a] == a:
        if seq[a]-a > 0:
            ret += seq[a]-a
        else:
            ret += seq[a]

print(ret)

Measured memory_bytes: 23288
using System;

 class Program
 {
     static void Main(string[] args)
     {
         double data0, data1, data2;

         String nyuryoku;
         string[] data; 
         nyuryoku = Console.ReadLine();
         data0 = Double.Parse(nyuryoku);
         nyuryoku = Console.ReadLine();
         string[] in2 = new string[(int)data0];
         in2 = nyuryoku.Split(' ');
         double temp,max, min, avg=0;
         max = min = avg = Double.Parse(in2[0]);
         for (int i = 1; i < data0; i++)
         {
             temp = Double.Parse(in2[i]);
             if(max < temp)
                 max = temp;
             else if(min > temp)
                 min = temp;
             avg = avg + temp;
         }
         Console.WriteLine("{0} {1} {2}",min, max, avg);

      }
 }



Measured memory_bytes: 20304
n = int(input())
ans = 0
y = [0 for i in range(10000)]
for i in range(1,100):
    for k in range(1,100):
        for x in range(1,100):
            ans = i**2 + k**2 + x**2 + i*k + k*x + i*x
            if n<ans:
                continue
            y[ans-1] += 1

for i in range(n):
    print(y[i])


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

using namespace std;

long dp[100+1][2];

int main() {
  long N, P;
  cin >> N >> P;
  vector<long> a(N);
  for (long i = 0; i < N; i++) {
    cin >> a[i];
  }
  dp[0][0] = 1;
  dp[0][1] = 0;
  for (long i = 0; i < N; i++) {
    if (a[i] % 2 == 0) {
      dp[i+1][0] = dp[i][0]*2;
      dp[i+1][1] = dp[i][1]*2;
    } else {
      dp[i+1][0] = dp[i][0]+dp[i][1];
      dp[i+1][1] = dp[i][0]+dp[i][1];
    }
  }
  cout << dp[N][P] << endl;
  return 0;
}

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

int main()
{
  vector<int> a = { 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51 };
  
  int k;
  cin >> k;
  
  cout << a.at(k - 1) << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

const int INF = (1<<20);

typedef struct{
  int ID;
  int sum;
}TEAM;

int main(){

  int in;
  while(cin >> in && in){
    TEAM data[in];
    for(int i = 0; i < in; i++){
      cin >> data[i].ID;
      data[i].sum = 0;
      for(int j = 0; j <4; j++){
	int min, sec;
	cin >> min >> sec;
	data[i].sum += min*60 + sec;
      }
    }

    TEAM max;
    int Tnum;
    max.sum = INF;
    for(int i = 0; i < in; i++){
      if(data[i].sum < max.sum){
	max = data[i];
	Tnum = i;
      }
    }
    cout << max.ID << endl;
    data[Tnum].sum = INF;

    max.sum = INF;
    for(int i = 0; i < in; i++){
      if(data[i].sum < max.sum){
	max = data[i];
	Tnum = i;
      }
    }

    cout << max.ID << endl;
    data[Tnum].sum = INF;

    max.sum = 0;
    for(int i = 0; i < in; i++){
      if(data[i].sum > max.sum && data[i].sum != INF){
	max = data[i];
	Tnum = i;
      }
    }
    data[Tnum].sum = INF;
    max.sum = 0;
    for(int i = 0; i < in; i++){
      if(data[i].sum > max.sum && data[i].sum != INF) max = data[i];
    }
    cout << max.ID << endl;
  }
  return 0;
}

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

const int INF = 1e+8;
const int C[6] = {1,5,10,50,100,500};
int n[6] = {0};

// x 円を支払う最小の硬貨の枚数 (おつり)
int f(int x){
	int cnt=0;
	while( x ){
		for(int i=5 ; i >= 0 ; i-- ){
			while( C[i] <= x ){
				x -= C[i];
				cnt++;
			}
		}
	}
	return cnt;
}

// x を支払う最小の硬貨の枚数 (硬貨はn[0]..n[5]持っている)
int solve(int x){
	int ans = 0;
	for(int i=5 ; i >= 0 ; i-- ){
		int t = min( x/C[i] , n[i] );
		x -= t * C[i];
		ans += t;
	}
	return ans;
}

int main(){
	int p;
	while( cin >> p, p ){
		
		for(int i=0 ; i < 6 ; i++ ){
			cin >> n[i];
		}
		int ans = INF;
		for(int i=p ; i <= p+500 ; i++ ){
			//if( solve(i) == -1 ) continue;
			ans = min( ans , solve(i) + f(i-p) );
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 0