akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int n;
    cin >> n ;
    vector<string> s(n) ;
    for (size_t i = 0; i < n; i++)
    {
        cin >> s.at(i) ;
        sort(s.at(i).begin() ,s.at(i).end()) ;
    }
    sort(s.begin(),s.end()) ;
    int64_t ans = 0;
    int count = 0;
    for (size_t i = 0; i < n-1; i++)
    {
        
        
            /* code */
        
            if (s.at(i) == s.at(i+1))
            {
                count ++ ;
                ans += count ;
            }
            else
            {
                count = 0 ;
            }
        
        
    }
    cout << ans << endl ;
}

Measured memory_bytes: 7296
n, m = map(int, input().split())

empty = []
graphs = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a1 = a - 1
    b1 = b - 1
    graphs[a1].append(b1)
    graphs[b1].append(a1)

def dfs(v, seen):
    seen[v] = True
    if all(seen):
        return 1

    ans = 0
    for nextCandidate in graphs[v]:
        if seen[nextCandidate]:
            continue
        ret = dfs(nextCandidate, seen[:])
        ans += ret

    return ans


firstSeen = [False]*n

total = dfs(0, firstSeen)

print(total)





Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <set>

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,j) FOR(i,0,j)
#define mp std::make_pair

const int INF = 1 << 24;
const int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1}, dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};

typedef unsigned long long ull;
typedef std::pair<int,int> P;

int N, M;
int a[10];

int bitCount(int n){
    int res = 0;
    while(n > 0){
        if(n & 1){res++;}
        n >>= 1;
    }
    return res;
}

int pow(int a, int n){
    int res = 1;
    while(n > 0){
        if(n & 1){res *= a;}
        a *= a;
        n >>= 1;
    }
    return res;
}

int main(){
    std::cin >> N;

    std::string id;
    std::cin >> id;
    std::reverse(id.begin(), id.end());

    int sum = 0;
    int even = 0, odd = 0, total = 0;
    REP(i, N){
        if(id[i] == '*'){
            if(i % 2 == 0){
                even++;
            }else{
                odd++;
            }
            total++;
        }else{
            if(i % 2 == 0){
                sum += id[i] - '0';
            }else{
                int n = (id[i] - '0') * 2;
                sum += n % 10 + n / 10;
            }
        }
    }

    std::cin >> M;
    REP(i, M){
        std::cin >> a[i];
    }
    
    int r[10];
    std::fill(r, r+10, 0);
    REP(i, pow(M, even)){
        int _i = i, _sum = 0;
        REP(j, even){
            _sum = (_sum + a[_i%M]) % 10;
            _i /= M;
        }
        r[_sum]++;
    }

    int res = 0;
    REP(i, pow(M, odd)){
        int _i = i, _sum = 0;
        REP(j, odd){
            int n = a[_i%M] * 2;
            _sum = (_sum + n % 10 + n / 10) % 10;
            _i /= M;
        }
        REP(j, 10){
            if((sum + _sum + j) % 10 == 0){
                res += r[j];
            }
        }
    }

    std::cout << res << std::endl;
}

Measured memory_bytes: 1332
#include <iostream>
#include <vector>
#include <string>
#define rep(i, n)   for(int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;

int main(){
    int n,r;    cin >> n >> r;
    int ans = 0;
    if(n >= 10){
        ans = r;
    }else{
        ans = r + 100*(10 - n);
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <cassert>
#include <cstdio>
#include <cstdlib>

int
main()
{
    int c[3][3];
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            assert(scanf("%d", &c[i][j]) == 1);
    int diff[3];
    for (int j = 0; j < 3; j++)
        diff[j] = c[0][j] - c[0][0];
    for (int i = 1; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (c[i][j] - c[i][0] != diff[j]) {
                printf("No\n");
                exit(0);
            }
        }
    }
    printf("Yes\n");
    exit(0);
}


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

int main() {
  int A,B,C,D;
  cin >> A >> B >> C >>D;
  while(A>0 && C>0) {
    C -= B;
    if(C<=0) {
      cout << "Yes" << endl;
      return 0;
    }
    A -= D;
    if(A<=0) {
      cout << "No" << endl;
      return 0;
    }
  }
}

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

#define ll long long
#define P pair<int,int>
#define rep(i,n) for(int i = 0; i < (n); i++)
#define asort(x) sort(x.begin(),x.end())

int main() {
    int cnt = 0;
    long long x, m = 100;
    cin >> x;
    while(m < x){
       m *= 1.01;
       cnt++;
    }
    cout << cnt << endl;
    return 0;
}

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

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using pint = pair<int, int>;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const int MOD = 1000000007;
const long long INF = 1LL << 60;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

vector<int> h;
vector<ll> memo;

ll rec(int i) {
    if (i == 0) return 0;

    if (memo[i] != -1) return memo[i];
    ll res = INF;
    chmin(res, rec(i-1) + abs(h[i] - h[i-1]));
    if (i > 1) chmin(res, rec(i-2) + abs(h[i] - h[i-2]));
    return memo[i] = res;
}

int main() {
    memo.assign(100100, -1);
    int N; cin >> N;
    h.resize(N);
    for (int i = 0; i < N; ++i) cin >> h[i];
    cout << rec(N-1) << endl;
    return 0;
}

Measured memory_bytes: 9036
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i = a; i<n; i++)
#define per(i,a,n) for (int i = n-1; i>=a; i--)
#define pb push_back
#define mp make_pair
#define all(now) (now).begin(),(now).end()
#define fi first
#define se second
#define SZ(now) ((int)(now).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod = 1000000007;
inline int read(int &n){char c=getchar();int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+(c-'0');c=getchar();}return n = x*f;}
ll powmod(ll a,ll b,ll mod) {ll res = 1; a%=mod; assert(b>=0); for(;b; b>>=1){if(b&1)res = res*a%mod; a = a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
const int N = 1e5+7;
int T,n,m;
int a[N];
int main()
{
    //ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    int len = m / n;
    per(i, 1, len+1){
        if(m%i==0){
            printf("%d\n", i);
            return 0;
        }
    }
    return 0;
}

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

typedef long long ll;

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

int main() {
  int N;
  cin >> N;
  vector<ll> a(N),b(N);
  rep(i,N) cin >> a[i];
  rep(i,N) cin >> b[i];
  ll timea = 0,timeb = 0;
  rep(i,N) timea += b[i]-a[i];
  timeb = timea;
  rep(i,N) {
    if (b[i]-a[i] <= 0) timeb -= a[i]-b[i];
    else timea -= (b[i]-a[i]+1)/2;
  }
  if ((timea >= 0) && (timeb >= 0)) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 3748
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a, b;
    cin >> a >> b;
    int arr[a-1];
    int ans = 0;
    for(int i=0; i<a; i++)
    {
        cin >> arr[i];
        ans += arr[i];
    }
    sort(arr, arr+a);
    int dif = a-b;
    for(int i=0; i<dif; i++)
    {
        ans = ans - arr[i];
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>

using namespace std;

typedef long long ll;
typedef vector <int> vi;
typedef vector < vector <int> > vvi;
const int HUGEI = 2147483647;  // (1 << 31) - 1
const ll HUGEL = 9223372036854775807;  // (1 << 63) - 1
const string ABC = "abcdefghijklmnopqrstuvwxyz";

int main(void) {
    long n, k;
    vector <long> an;
    vector <long> sum_all, sum_positive;  // offset. sum_all[i + 1] is sum of elements [0, i]
    cin >> n >> k;
    sum_all.push_back(0);
    sum_positive.push_back(0);
    for (long i = 0; i < n; i++) {
        long a;
        cin >> a;
        an.push_back(a);
        sum_all.push_back(sum_all.back() + a);
        sum_positive.push_back(sum_positive.back() + max(a, long(0)));
    }

    long res = 0;
    for (long i = 0; i <= n - k; i++) {
        long re;
        re = sum_positive[i] + sum_positive[n] - sum_positive[i + k];
        re += max(long(0), sum_all[i + k] - sum_all[i]);
        res = max(re, res);
    }
    cout << res << endl;
    return 0;
}



Measured memory_bytes: 2912
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+9, INF = 0x3f3f3f3f;
int dt[N], n, k;

int check( int p ) {
    int cnt = 0, i = 0, sum = 0;
    while( i < n ) {
        if( sum + dt[i] <= p ) {
            sum += dt[i]; ++i;
        }
        else {
            ++cnt; sum = 0;
        }
        if( cnt >= k ) break;
    }
    if( sum ) ++cnt;
    return cnt <= k && i == n;
}

int cxk() {
    int l = 0, r = 1e9, mid;
    while( l < r ) {
        mid = l + r >> 1;
        if( check( mid ) ) r = mid;
        else l = mid + 1;
    }
    return r;
}

int main( void ) {
    ios::sync_with_stdio( false );
    cin >> n >> k;
    for( int i = 0; i < n; ++i ) cin >> dt[i];
    cout << cxk() << '\n';
    return 0;
}



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

int main() {
  map<int, int> mp;
  rep(i,3){
    int tmp;
    cin >> tmp;
    mp[tmp]++;
  }
  if(mp[5] == 2 && mp[7] == 1){
    cout << "YES" << endl;
  }else {
    cout << "NO" << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  string n;
  cin>>n;
  for(int i=1;i<=3;i++){
    if(n[i]==n[i-1]){
      cout<<"Bad\n";
      return 0;
    }
  }
  cout<<"Good\n";
  return 0;
}

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

#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define RFOR(i,b,a) for(int i = (b) - 1; i >= (a); i--)
#define ITER(it, a) for(typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a, value) memset(a, value, sizeof(a))

#define SZ(a) (int) a.size()
#define ALL(a) a.begin(),a.end()
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;

const double PI = acos(-1.0);
const LL INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL)INF;

const int MAX = 1000 * 100 + 47;
int A[MAX];

void imp()
{
    cout << "IMPOSSIBLE" << endl;
    exit(0);
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	ios::sync_with_stdio(false); cin.tie(0);
	int n, k;
	cin >> n >> k;
	FOR(i,0,n) cin >> A[i];
	
	int g = A[0];
	int mx = A[0];
	
	FOR(i,0,n)
	{
	    g = __gcd(A[i], g);
	    mx = max(A[i], mx);
	}
	
	if (mx < k) imp();
	if ((mx - k) % g != 0) imp();
	
	cout << "POSSIBLE" << endl;
}

Measured memory_bytes: 640
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;} return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;} return 0;}
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(vec) vec.begin(),vec.end()
typedef long long ll;
typedef pair<ll,ll> l_l;
typedef pair<int,int> i_i;
const ll mod=1e9+7;
const int inf=1<<30;
ll kiri(ll a,ll b){return a%b==0?a/b:a/b+1;}

int main(){
  int n; cin >> n;
  cout << kiri(n,2) << endl;
  
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n,count=0;
  string s,t;
  cin>>n>>s>>t;
  for(int i=1; i<=n; i++){
    if(s.substr(n-i,i)==t.substr(0,i)){
      count=i;
    }
  }
  cout<<n*2-count<<'\n';
  return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <cmath>
#include <numeric>
#include <vector>
#include <bitset>
#include <queue>
using namespace std;

int g(int n){
    if(n == 2) return 1;
    if(n == 4 || n == 6 || n == 9 || n == 11) return 2;
    return 3;
}
int main(){
    int a, b;
    cin >> a >> b;
    int ag, bg;
    ag = g(a);
    bg = g(b);
    if(ag == bg){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

INF = float('inf')

def solve():
    n = II()
    A = LI()
    ans = [0] * n
    for i, a in enumerate(A):
        ans[a-1] += 1

    for a in ans:
        print(a)


if __name__ == '__main__':
    solve()


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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    long long n, m, k;
    cin >> n >> m >> k;

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

    for (int i = 0; i < m; ++i)
        cin >> b[i];

    vector<long long> prefixa(n + 1), prefixb(m + 1);
    for (int i = 1; i <= n; ++i)
        prefixa[i] += prefixa[i - 1] + a[i - 1];
    for (int i = 1; i <= m; ++i)
        prefixb[i] += prefixb[i - 1] + b[i - 1];
    
    long long ans = 0;
    for (int i = 0; i <= n; i++){
        if (k - prefixa[i] >= 0)
            ans = max(ans, (long long) (upper_bound(prefixb.begin(), prefixb.end(), k - prefixa[i]) - prefixb.begin()) + i - 1);
    }

    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 7936
#include<iostream>
#include<algorithm>
using namespace std;
int N;
long K;
long A[2<<17],F[2<<17];
main()
{
	cin>>N>>K;
	for(int i=0;i<N;i++)cin>>A[i];
	sort(A,A+N);
	for(int i=0;i<N;i++)cin>>F[i];
	sort(F,F+N);
	reverse(F,F+N);
	long L=-1,R=4e18;
	while(R-L>1)
	{
		long M=(L+R)/2;
		long T=0;
		for(int i=0;i<N;i++)
		{
			long X=A[i]*F[i]-M;
			if(X>0)T+=(X+F[i]-1)/F[i];
		}
		if(T<=K)R=M;
		else L=M;
	}
	cout<<R<<endl;
}

Measured memory_bytes: 3968
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> P;
ll Mod = 1000000007;
bool Can_Match[10];
int main() {
  int n,m;
  cin >> n >> m;
  int a[n];
  int star[m];
  int end[m];
  int fall[m];
  ll diff[m];
  for (int i = 0; i < m; i++) {
    star[i] = 0;
    end[i] = 0;
    fall[i] = 0;
    diff[i] = 0;
  }
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    a[i]--;
  }

  for (int i = 1; i < n; i++) {
    if (a[i-1] < a[i]) {
      if (a[i] - a[i-1] >= 2) {
        star[a[i-1]+2]++;
        end[a[i]]++;
      }
    } else {
      if (a[i] + m - a[i-1] >= 2) {
        if (a[i-1]+2 < m) {
          star[a[i-1]+2]++;
          end[m-1]++;
        }
        star[0]++;
        end[a[i]]++;
      }
    }
  }
  diff[0] = 0;
  for (int i = 1; i < n; i++) {
    if (a[i-1] < a[i]) {
      if (a[i] - a[i-1] >= 2) {
        fall[(a[i]+1)%m] += a[i] - a[i-1] - 1;
      }
    } else {
      if (a[i] - a[i-1] + m >= 2) {
        fall[(a[i]+1)%m] += a[i] - a[i-1] + m - 1;
      }
    }
  }
  int Kukan = 0;
  Kukan += star[0];
  Kukan -= end[0];
  for (int i = 1; i < m; i++) {
    Kukan += star[i];
    diff[i] = diff[i-1] + Kukan;
    diff[i] -= fall[i];
    Kukan -= end[i];
  }
  ll max_diff = 0;
  for (int i = 0; i < m; i++) {
    max_diff = max(max_diff,diff[i]);
  }
  ll ans = 0;
  for (int i = 1; i < n; i++) {
    if (a[i-1] < a[i]) {
      ans += a[i] - a[i-1];
    } else {
      ans += 1 + a[i];
    }
  }
  cout << ans - max_diff << endl;
  return 0;
}

Measured memory_bytes: 5916
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T> void assign(V<T>& v, int n, const T& a = T()) { v.assign(n, a); }
template<class T, class... U> void assign(V<T>& v, int n, const U&... u) { v.resize(n); for (auto&& i : v) assign(i, u...); }

const int inf = 1e9;
struct edge { int to, cost; edge(int to, int cost) : to(to), cost(cost) {} };

template<class T> bool bellman_ford(int s, const VV<edge>& g, V<T>& d) {
  d.assign(g.size(), inf);
  d[s] = 0;
  for (int i = 0; i < g.size(); i++) {
    bool upd = false;
    for (int v = 0; v < g.size(); v++) {
      for (auto&& e : g[v]) {
        if (d[v] != inf and d[e.to] > d[v] + e.cost) {
          d[e.to] = d[v] + e.cost;
          upd = true;
        }
      }
    }
    if (!upd) return false;
  }
  return true;
}

int main() {
  cin.tie(NULL); ios::sync_with_stdio(false);
  int n, m, s; cin >> n >> m >> s;
  VV<edge> g(n);
  for (int i = 0; i < m; i++) {
    int a, b, c; cin >> a >> b >> c;
    g[a].emplace_back(b, c);
  }
  V<> d;
  if (bellman_ford<int>(s, g, d)) cout << "NEGATIVE CYCLE" << '\n';
  else {
    for (int i = 0; i < n; i++) cout << (d[i] != inf ? to_string(d[i]) : "INF") << '\n';
  }
}


Measured memory_bytes: 3312
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
int main(){
  int n;
  cin>>n;
  if(n%10==3)
    cout<<"bon";
  else if(n%10==0||n%10==1||n%10==6||n%10==8)
    cout<<"pon";
  else
    cout<<"hon";
}


Measured memory_bytes: 3632
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
using namespace std;
#define mp make_pair
#define pb push_back
#define x first
#define y second
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
int dp[4000][4000],g[4000],head[4000];
int n,k,ans;
struct edge
{
	int to,next;
}e[4000];
bool v[4000];
vector<int> graph[4000];
void push(int k,int x,int y)
{
	e[k].to=y;e[k].next=head[x];head[x]=k;
}
void dfs(int x)
{
	int p=head[x];
	dp[x][0]=1;
	for (int j=1;j<=k+1;j++)
	{
		dp[x][j]=0;
	}
	v[x]=1;
	//while (p)
	for(int second : graph[x])
	{
		//if (!v[e[p].to])
		if(!v[second])
		{
		//dfs(e[p].to);
		dfs(second);
		
		g[0]=dp[x][0];
		for (int j=1;j<=k+1;j++) g[j]=min(g[j-1],dp[x][j]);
		for (int j=1;j<=k+1;j++) dp[x][j]=n;
		for (int j=1;j<=min(k+1,dp[x][0]);j++)
			for (int w=0;w<=min(k,dp[second][0]);w++)
				if (j-1+w<=k) dp[x][max(j,w+1)]=min(dp[x][max(j,w+1)],g[j]+dp[second][w]);
		dp[x][0]+=dp[second][0];
		}
		//p=e[p].next;
	}
	for (int j=1;j<=k+1;j++) dp[x][j]=min(dp[x][j],dp[x][j-1]);
	ans=min(ans,n-dp[x][0]+dp[x][k+1]);
}

int main()
{
	scanf("%d%d",&n,&k);
	for (int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		//push(2*i-1,x,y);push(2*i,y,x);
		graph[x].push_back(y);
		graph[y].push_back(x);
	}
	memset(v,0,sizeof(v));
	ans=n;
	dfs(1);
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 27580
#include <stdio.h>
#include <stdlib.h>
#include <queue>

#define N_MAX 100001

int desc(const void *a, const void *b){
  if(*(long *)a > *(long *)b){
    return -1;
  }else if(*(long *)a == *(long *)b){
    return 0;
  }else{
    return 1;
  }
}

int main(void){
  int i, j;

  int n, m;
  scanf("%d%d", &n, &m);

  std::priority_queue<double> q;

  long a;
  double b;
  for(i=0; i<n; i++){
    scanf("%ld", &a);
    double b=a;
    q.push(b);
  }

  for(i=0; i<m; i++){
    b=q.top();
    q.pop();
    b/=2;
    q.push(b);
  }

  long ans=0;
  for(i=0; i<n; i++){
    a=q.top();
    q.pop();
    ans+=a;
  }

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

  return 0;
}


Measured memory_bytes: 1400
# Union Find
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    # xの根を返す
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            # 経路圧縮
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # xの根とyを連結させる
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    # xとyの親が同じ根か判別
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # xが連結している木の大きさを返す
    def size(self, x):
        return -self.parents[self.find(x)]


n, m, k = map(int, input().split())
uf = UnionFind(n)
deg = [0 for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    deg[a - 1] += 1
    deg[b - 1] += 1
    uf.union(a - 1, b - 1)

block = [[] for _ in range(n)]
for _ in range(k):
    a, b = map(int, input().split())
    block[a - 1].append(b - 1)
    block[b - 1].append(a - 1)

ans = []
for i in range(n):
    res = uf.size(i) - 1 - deg[i]
    for u in block[i]:
        if uf.same(i, u):
            res -= 1
    ans.append(res)

print(*ans)


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

// {U}{INT,LONG,LLONG}_{MAX,MIN}
#define INF         INT_MAX/3
#define LLINF       LLONG_MAX/3
#define MOD         (1000000007LL)
#define MODA(a, b)  a=((a)+(b))%MOD
#define MODP(a, b)  a=((a)*(b))%MOD
#define inc(i, l, r)   for(int i=(l);i<(r);i++)
#define dec(i, l, r)   for(int i=(r)-1;i>=(l);i--)
#define pb          push_back
#define se          second
#define fi          first
#define mset(a, b)  memset(a, b, sizeof(a))

using LL  = long long;
using G   = vector<vector<int>>;

int di[] = {0, -1, 0, 1};
int dj[] = {1, 0, -1, 0};
// }}}

int main() {
    cin.tie(0);ios::sync_with_stdio(false);
    int a, b, c;cin >> a >> b >> c;
    cout << a*b/2 << endl;
    return 0;
}


Measured memory_bytes: 256
const lines=readlines()
input()=shift!(lines)
int(x)=parse(Int,x)
intLine()=map(int,split(input()))
function main()
    n=int(input())
    b=intLine()
    a=b[1]
    for i=2:n
        a$=b[i]
    end
    println(a>0?"No":"Yes")
end
main()

Measured memory_bytes: 168700
#include<stdio.h>
#include<math.h>
#define PI 3.141592653589793
int main()
{
          double a,b,C,ag,s,c;
          double S,L,H;
          scanf("%lf %lf %lf",&a,&b,&C);
          c=sqrt(a*a+b*b-2*a*b*cos((PI*C)/180));
          L=a+b+c;
          s=L/2;
          S=sqrt(s*(s-a)*(s-b)*(s-c));
          H=(2*S)/a;
          printf("%.8lf\n%.8lf\n%.8lf\n",S,L,H);
          return 0;

}



Measured memory_bytes: 2108
#include<stdio.h>

//線形探索

int search(int A[], int n, int key){
	int i=0;
	A[n] = key;
	while( A[i] != key ) i++;
	return i != n;
}

int main(){
	int i,n,A[10000+1],q,key,sum=0;
	
	scanf("%d",&n);
	for(i=0; i<n; i++) scanf("%d",&A[i]);
	
	scanf("%d",&q);
	for(i=0; i<q; i++)
	{
		scanf("%d", &key);
		if(search(A,n,key)) sum++;
	}
	printf("%d\n", sum);
	
	return 0;
}


Measured memory_bytes: 2100
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using ll = long long int;
using P = std::pair<int, int>;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

int a[100100],b[100100];
std::multiset<int> st;
int ufr[100100],ufp[100100],uff[100100];
std::vector<P> v,u;

void ufinit(int n){
	int i;
	for(i=0; i<=n; ++i){
		ufr[i] = 1;
		ufp[i] = i;
		uff[i] = (a[i]==a[n]);
	}
}

int ufind(int x){
	if(x==ufp[x]){
		return x;
	}
	return ufp[x] = ufind(ufp[x]);
}

void unionf(int x, int y){
	x = ufind(x); y = ufind(y);
	if(x==y){
		return;
	}
	if(ufr[x]<ufr[y]){
		std::swap(x,y);
	}
	ufr[x] += ufr[y];
	uff[x] |= uff[y];
	ufp[y] = x;
}

int main(void){
	int n,i,ans=0,cnt=0;
	std::cin >> n;
	for(i=0; i<n; ++i){
		std::cin >> a[i];
		u.push_back(P(a[i],i));
		a[n] ^= a[i];
	}
	u.push_back(P(a[n],n));
	for(i=0; i<n; ++i){
		std::cin >> b[i];
		if(a[i] != b[i] && a[i]==a[n]){
			++cnt;
		}
		v.push_back(P(b[i],i));
		b[n] ^= b[i];
	}
	v.push_back(P(b[n],n));
	std::sort(v.begin(),v.end());
	std::sort(u.begin(),u.end());
	for(i=0; i<=n; ++i){
		if(v[i].first != u[i].first){
			std::cout << "-1" << std::endl;
			return 0;
		}
	}
	v.clear(); u.clear();
	for(i=0; i<=n; ++i){
		if(a[i] == b[i]){
			continue;
		}
		u.push_back(P(a[i],i));
		v.push_back(P(b[i],i));
	}
	std::sort(v.begin(),v.end());
	std::sort(u.begin(),u.end());	
	ufinit(n);
	for(i=(v.l_ength()-1); i>=0; --i){
		unionf(u[i].second,v[i].second);
	}
	for(i=(v.l_ength()-1); i>0; --i){
		if(v[i].first==v[i-1].first){
			unionf(v[i].second,v[i-1].second);
			unionf(u[i].second,u[i-1].second);
		}
	}
	for(i=0; i<=n; ++i){
		// printf("%d: %d\n",i,ufind(i));
		if(a[i] == b[i]){
			continue;
		}
		++ans;
		if(ufind(i)==i){
			if(!uff[i]){
				++ans;
			}else if(ufind(n)==i){
				--ans;
			}
		}
	}
	std::cout << ans << std::endl;
	return 0;
}


Measured memory_bytes: 3956
s = input()
n = len(s)
sformer = s[:int((n - 1) / 2)]
slatter = s[int((n + 1) / 2):]
if s == s[-1::-1] and sformer == sformer[-1::-1] and slatter == slatter[-1::-1]:
  print('Yes')
else:
  print('No')

Measured memory_bytes: 9044
#ifdef DBG1
  #define LOCAL
#endif

#ifdef LOCAL
  #define _GLIBCXX_DEBUG
#endif

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>

#ifdef DBG1
    #define dbg(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dbg(...)
#endif

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;

bool check(int n, const vector<int> & a, int cnt) {
  if (cnt < 1) { return false; }
  int len = a[0];
  vector<pii> st;
  st.push_back(pii(a[0], 0));
  for (int i = 1; i < n; ++i) {
    assert(len == a[i - 1]);
    if (a[i] > a[i - 1]) {
      len += a[i] - a[i - 1];
      st.push_back(pii(a[i] - a[i - 1], 0));
    } else {
      while (len - st.back().first > a[i]) {
        len -= st.back().first;
        st.pop_back();
      }
      if (len > a[i]) {
        st.back().first -= len - a[i];
        len -= len - a[i];
      }

      int add = 0;
      while (!st.empty() && (st.back().second == cnt - 1 || st.back().first == 0)) {
        add += st.back().first;
        st.pop_back();
      }

      if (st.empty()) { return false; }

      assert(st.back().second < cnt - 1);
      assert(st.back().first > 0);
      st.back().first -= 1;
      st.push_back(pii(1, st.back().second + 1));

      if (add) {
        st.push_back(pii(add, 0));
      }
    }
  }
  return true;
}

bool solve() {
  int n;
  if (scanf("%d", &n) != 1) { return false; }

  vector <int> a(n);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
  }
  
  int L = 0;
  int R = n;
  while (L + 1 < R) {
    int M = (L + R) / 2;
    if (check(n, a, M)) {
      R = M;
    } else {
      L = M;
    }
  }

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

  return true;
}

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

Measured memory_bytes: 4692
//#define _GLIBCXX_DEBUG

#include<bits/stdc++.h>
using namespace std;
const int INF= 1e9+5;
typedef long long ll;

int main(){
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  cout<<max(a*b,c*d)<<endl;
}
    
    

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const static ll INF = 1e9;
const static ll MAXN = 301;



int main(){
    int N; cin >> N;
    int MAXW = 0;
    vector<int> H(N), H_(N); for(int i = 0; i < N; i++) {cin >> H[i]; MAXW = max(MAXW, H[i]);}
    ll ans = 0;
    for(int w = 1; w <= MAXW; w++){
        vector<int> W(N);
        ll tmp=0;
        for(int i = 0; i < N; i++){
            if(H[i] > H_[i]) {W[i]++;H_[i]++;}
        }

        for(int i = 0; i < N; i++){
            if(W[i] == 1){
                if(i == N-1) tmp++;
                else if(W[i+1] == 0) tmp++;
            }
        }
        ans+= tmp;
    }
    cout << ans << endl;

}


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

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

	vector<int> a(n);
	vector<int> b(n);
	vector<int> c(n-1);

	int happy = 0;
	rep(i, n) cin >> a.at(i);
	rep(i, n){
		cin >> b.at(i);
		happy += b.at(i);
	}
	rep(i,n-1) cin >> c.at(i);

	rep(i, n-1){
		if(a.at(i)+1 == a.at(i+1)) happy += c.at(a.at(i)-1);
	}

	cout << happy << endl;

	return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include <bitset>
using namespace std;
#define INF 110000000000
#define MOD 1000000007
typedef long long ll;
typedef pair<ll,int> P;

int main(){
  int N;
  string s[110000];
  cin>>N;
  for(int i=0;i<N;i++){
    cin>>s[i];
    sort(s[i].begin(),s[i].end());
  }
  sort(s,s+N);
  ll count=0,ans=0;

  for(int i=1;i<N;i++){
    if(s[i]==s[i-1]){
      count++;
      ans+=count;
    }else count=0;
  }
  cout<<ans<<endl;

}


Measured memory_bytes: 2816
#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <queue>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <cstdio>
#include <climits>
#include <complex>
#include <cstdint>
#include <tuple>

#define M_PI       3.14159265358979323846

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }
inline int readInt() { int x; scanf("%d", &x); return x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<int, PII> TIII;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;

//container util

//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SQ(a) ((a)*(a))
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,s,n) for(int i=s;i<(int)n;++i)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
int n, m;


int GCD(int a, int b){
    if(a < b) swap(a, b);
    if(b==0) return a;
    return GCD(b, a%b);
}

LL pow(LL x, LL n){
    LL res = 1;
    while(n>0){
        if(n&1){
            res *= x;
        }

        x = x*x;
        n >>= 1;
    }
    return res;
}
int main() {
    cout << fixed << setprecision(15);

    int N, K; cin >> N >> K;

    long double ans = 0.0;

    for(int i=1; i<=N; ++i){
        LL t=i;
        LL cn = 1;
        while(t<K){
            t *= 2;
            cn <<= 1;
        }

        ans += (double)1/N / cn;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
class Array
	def accum
		inject([0]){|a, x| a + [a[-1] + x]}
	end

	def accum!
		(1..size-1).each{|i|
			self[i] += self[i-1]
		}
		self.unshift(0)
	end

	def accum_2d
		ac = map{|r| r.accum}
		(1..size-1).each{|i|
			(1..ac[0].size-1).each{|j|
				ac[i][j] += ac[i-1][j]
			}
		}
		ac.unshift([0] * ac[0].size)
		ac
	end

	def accum_2d!
		each{|r| r.accum!}
		(1..size-1).each{|i|
			(1..self[0].size-1).each{|j|
				self[i][j] += self[i-1][j]
			}
		}
		unshift([0] * self[0].size)
	end
		
	def bsearch_first_index(l = 0, r = size - 1, &pred)
		return nil if l > r
		c = (l + r) / 2 
		if pred[self[c]]
			bsearch_first_index(l, c-1, &pred) || c
		else
			bsearch_first_index(c+1, r, &pred)
		end
	end

	def bsearch_first_item(l = 0, r = size - 1, &pred)
		i = bsearch_first_index(l, r, &pred)
		i ? self[i] : nil
	end

	def bsearch_last_index(l = 0, r = size - 1, &pred)
		return nil if l > r
		c = (l + r) / 2 
		if pred[self[c]]
			bsearch_last_index(c+1, r, &pred) || c
		else
			bsearch_last_index(l, c-1, &pred)
		end
	end

	def bsearch_last_item(l = 0, r = size - 1, &pred)
		i = bsearch_last_index(l, r, &pred)
		i ? self[i] : nil
	end
end

loop {
	n = gets.to_i
	break if n == 0
	h, w = gets.split.map &:to_i
	a = (1..h).map { [0] * w }
	n.times {
		i, j = gets.split.map &:to_i
		a[i-1][j-1] = 1
	}
	a.accum_2d!
	s, t = gets.split.map &:to_i
	max = 0
	(s..h).each{|i|
		(t..w).each{|j|
			x = a[i][j] - a[i-s][j] - a[i][j-t] + a[i-s][j-t]
			max = x if x > max
		}
	}
	p max
}

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

int main() {
    int N,Y;
    cin >> N >> Y;
    int flag = 0;
    int ans_a = -1, ans_b = -1, ans_c = -1;
    for(int a = 0; a <= N; a++){
        for(int b = 0; b <= N-a; b++) {
            int c = N-a-b;
            if(Y == 10000*a + 5000*b + 1000*c) {
                ans_a = a;
                ans_b = b;
                ans_c = c; 
                flag = 1;
                break;
            }
            if(flag == 1)break;
        }
        if(flag == 1)break;
    }
    cout << ans_a << " " << ans_b << " " <<ans_c << endl;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;
import java.math.BigInteger;
public class Main {

static long[] list=new long[87];

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

   String nyuA=sc.nextLine();
   
int N=Integer.parseInt(nyuA);

String[] data=sc.nextLine().split(" ");

int[] num=new int[data.length];

for(int i=0;i<data.length;i++){
num[i]=Integer.parseInt(data[i]);
}
Arrays.sort(num);


System.out.println(num[num.length-1]-num[0]);

}

}



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

using namespace std;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
template<class T> inline T sqr(T x) {return x*x;}

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;

#define all(a)  (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define pb push_back
#define mp make_pair
#define each(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define exist(s,e) ((s).find(e)!=(s).end())
#define range(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  range(i,0,n)
#define clr(a,b) memset((a), (b) ,sizeof(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

const double eps = 1e-10;
const double pi  = acos(-1.0);
const ll INF =1LL << 62;
const int inf =1 << 29;

const int vmax=100010;
int sdist[vmax];
int tdist[vmax];

ll snum[vmax];
ll tnum[vmax];

vi graph[vmax];

int main(void){
	int n,m,s,t;
	cin  >> n >> m >> s >> t;
	s--,t--;

	rep(i,m){
		int x,y;
		cin >> x >> y;
		x--,y--;
		graph[x].pb(y);
		graph[y].pb(x);
	}
	rep(i,vmax) sdist[i]=tdist[i]=-1;

	queue<pii> q;
	sdist[s]=0; q.push(mp(s,0));
	while(!q.empty()){
		pii cur=q.front();q.pop();
		int v=cur.first;
		int c=cur.second;
		for(auto &v2:graph[v]){
			if(sdist[v2]==-1){
				sdist[v2]=c+1;
				q.push(mp(v2,c+1));
			}
		}
	}

	tdist[t]=0; q.push(mp(t,0));
	while(!q.empty()){
		pii cur=q.front();q.pop();
		int v=cur.first;
		int c=cur.second;
		for(auto &v2:graph[v]){
			if(tdist[v2]==-1){
				tdist[v2]=c+1;
				q.push(mp(v2,c+1));
			}
		}
	}
	rep(i,n) snum[sdist[i]]++;
	rep(i,n) tnum[tdist[i]]++;
	int sp=sdist[t];
	ll ans=0LL;
	rep(i,sp-1) ans+=snum[i]*tnum[sp-2-i];
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 10224
#include<bitset>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
using namespace std;

const int N=510,mod=998244353;
int n,m,y,rk,ans,a[N][N],pw[N];
bitset<N> b[N];

int main(){
	scanf("%d%d",&n,&m); pw[0]=1;
	rep(i,1,n){
		bitset<N>x(0);
		rep(j,1,m) scanf("%d",&y),x[j-1]=y;
		for(int j=m-1; ~j; j--)
			if (x[j]){
				if (b[j].any()) x^=b[j];
				 else{ b[j]=x; break; }
			}
	}
	rep(i,1,max(n,m)) pw[i]=2*pw[i-1]%mod;
	rep(i,0,m-1) if (b[i].any()) rk++;
	ans=1ll*(pw[n]-pw[n-rk])*pw[m-1]%mod;
	printf("%d\n",(ans+mod)%mod);
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, ll> Pl;
const double PI = 3.1415926535897932;   // acos(-1)
const double EPS = 1e-15;
const int mod = 1e+9 + 7;
const int INF = 1e+9; 

struct edge{
    int u, v;
    edge(int u, int v) : u(u), v(v) {}
    bool operator<(const edge& other) const{
        if(u == other.u){
            return v < other.v;
        }
        return u < other.u;
    }
};
vector<int> graph[100005];
vector<edge> edges;
bool num_used[100005];
map<edge, int> colors;

void dfs(int u, int pre = -1, int color = 0){
    int c = color;
    for(int i = 0; i < (int)graph[u].size(); ++i){
        int v = graph[u][i];
        if(v == pre)    continue;
        if(color == 1)    ++c;
        else if(color == 0){
            ++c;
        }
        else{
            if(c == color)  c = 1;
            else if(c == color - 1) c = color + 1;
            else        ++c;
        }
        int tu = u, tv = v;
        if(tu > tv) swap(tu, tv);
        colors[edge(tu, tv)] = c;
        num_used[c] = true;
        dfs(v, u, c);
    }

    return;
}

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

    int n;
    cin >> n;
    for(int i = 0; i < n-1; ++i){
        int a, b;
        cin >> a >> b;
        --a, --b;
        if(a > b)   swap(a, b);
        edges.push_back(edge(a, b));
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    dfs(0);
    int cnt = 0;
    for(int i = 1; i < n; ++i){
        if(num_used[i]) ++cnt;
    }
    cout << cnt << "\n";
    for(int i = 0; i < n-1; ++i){
        cout << colors[edge(edges[i].u, edges[i].v)] << "\n";
    }
}

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

using namespace std;
const double pi=acos(-1.0);
const double eps=1e-9;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair <int,int>
#define piii pair < pii, int>
#define pll pair <long long , long long>
#define plll pair <pll , long long>
#define hjsagjfasjg y1
typedef long long ll;

const int N=(int)1e5+5;
ll n,l,a[N],t;

int main()
{
	ios:: sync_with_stdio(false);
	cin >> n >> l;
	for(int i=0;i<n;i++)
		cin >> a[i];
	t=-1;
	for(int i=0;i<n-1;i++)
		if(a[i]+a[i+1]>=l)t=i;
	if(t==-1)
	{
		cout << "Impossible";
		return 0;
	}
	cout << "Possible" << endl;
	for(int i=0;i<t;i++)
		cout << i+1 << endl;
	for(int i=n-2;i>=t+1;i--)
		cout << i+1 << endl;
	cout << t+1;
	return 0;
}

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

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<int>> v(n, vector<int>(3));
    for(auto& i : v) {
        for(auto& j : i) {
            cin >> j;
        }
    }

    vector<vector<int>> best(n, vector<int>(3,0));
    best[0] = v[0];
    for(int i = 1; i < n; i++) {
        best[i][0] = max({v[i][0] + best[i-1][1], v[i][0] + best[i-1][2]});
        best[i][1] = max({v[i][1] + best[i-1][0], v[i][1] + best[i-1][2]});
        best[i][2] = max({v[i][2] + best[i-1][0], v[i][2] + best[i-1][1]});
    }

    cout << max({best[n-1][0], best[n-1][1], best[n-1][2]}) << endl;
}


Measured memory_bytes: 11136
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for (ll i = m; i < n; i++)
#define IFOR(i, m, n) for (ll i = n - 1; i >= m; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)
#define FOREACH(x, a) for (auto&(x) : (a))
#define ALL(v) (v).begin(), (v).end()
#define SZ(x) ll(x.size())

int main() {
  ll n, k;
  cin >> n >> k;
  vector<ll> a(n);
  REP(i, n) { cin >> a[i]; }

  ll ng = 0, ok = 1e9;
  while (ng + 1 < ok) {
    ll m = (ok + ng) / 2;
    ll cnt = 0;
    REP(i, n) {
      if (a[i] % m == 0) {
        cnt += a[i] / m - 1;
      } else {
        cnt += a[i] / m;
      }
    }
    (cnt <= k ? ok : ng) = m;
  }
  cout << ok << endl;
}

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

int main(){
	int N,ans=99;
	cin >> N;
	vector<int> D(13,0);
	for(int i=0;i<N;i++){
		int d;
		cin >> d;
		D[d]++;
	}
	int l=0,r=0;
	for(int i=0;i<=12;i++){
		if(i==0){
			if(D[i]>0)ans=0;
		}
		else if(i<12){
			if(D[i]>2)ans=0;
			else if(D[i]==2){
				ans=min(ans,i-r);
				ans=min(ans,i-l);
				l=r=i;
			}
			else if(D[i]==1){
				if(l<r){
					ans=min(ans,i-l);
					l=i;
				}
				else{
					ans=min(ans,i-r);
					r=i;
				}
			}
		}
		else{
			if(D[i]>2)ans=0;
			else if(D[i]==1){
				ans=min(ans,i-max(l,r));
			}
			else ans=min(ans,24-l-r);
		}
	}
	
	cout << ans << endl;
	return 0;
}

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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> Pll;

const int MAX_N = 3000;
const int MAX_HW = 100000;
const ll MOD = 1000000007;

ll dp[MAX_N+1][2];
ll fact[2*MAX_HW+1], rfact[2*MAX_HW+1];

ll perm(ll n, ll r){
    return (fact[n] * rfact[r]) % MOD;
}

ll comb(ll n, ll r){
    return (perm(n, r) * rfact[n-r]) % MOD;
}

ll modpow(ll a, ll t) {
    ll ret = 1LL;
    while(t){
        if(t & 1LL){
            ret *= a;
            ret %= MOD;
        }
        a *= a;
        a %= MOD;
        t >>= 1;
    }
    return ret;
}

void init(ll n){
    fact[0] = fact[1] = 1;
    rfact[0] = rfact[1] = 1;
    for(int i=2;i<=n;++i) {
        fact[i] = (fact[i-1] * (ll)i) % MOD;
        rfact[i] = 1;
        ll k = MOD-2;
        ll a = fact[i];
        while(k > 0){
            if(k & 1){
                rfact[i] *= a;
                rfact[i] %= MOD;
            }
            a *= a;
            a %= MOD;
            k  >>= 1;
        }
    }
}

int main() {
    ll H,W,N;
    cin >> H >> W >> N;
    vector<Pll> walls(N+1, Pll(1, 1));
    for(int i=1;i<=N;++i) {
        cin >> walls[i].first >> walls[i].second;
    }
    sort(walls.begin(), walls.end());

    init(H+W+1);

    dp[0][0] = comb(H+W-2, H-1);
    dp[0][1] = 0;
    for(int i=1;i<=N;++i) {
        for(int j=0;j<2;++j) {
            for(int ii=0;ii<i;++ii) {
                if(dp[ii][1-j] == 0) continue;
                if(walls[ii].first > walls[i].first || walls[ii].second > walls[i].second) continue;
                ll tmp = dp[ii][1-j];
                tmp *= modpow(comb(H+W-walls[ii].first-walls[ii].second, H-walls[ii].first), MOD-2);
                tmp %= MOD;
                tmp *= comb(walls[i].first+walls[i].second-walls[ii].first-walls[ii].second, walls[i].first-walls[ii].first);
                tmp %= MOD;
                tmp *= comb(H+W - walls[i].first - walls[i].second, H-walls[i].first);
                tmp %= MOD;
                dp[i][j] += tmp;
                dp[i][j] %= MOD;
            }
        }
    }

    ll ans = 0LL;
    for(int i=0;i<=N;++i) {
        ans += (dp[i][0] - dp[i][1] + MOD) % MOD;
        ans %= MOD;
    }

    cout << ans << endl;
}

Measured memory_bytes: 3456
import bisect,sys
import math
from collections import deque

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))

INF = 1 << 29

DIV = (10**9) + 7

def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(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

    class CONV:
        def __init__(self):
            self.fac =fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % DIV) % DIV
        
    return CONV()



sys.setrecursionlimit(200005)


def main():
    N = iRaw()
    ans = 0
    for n in range(1,N+1):
        if n%3!=0 and n%5!=0:
            ans+=n
    return ans
    
if __name__ == "__main__":
    print(main())


Measured memory_bytes: 73420
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int lli;
const lli mod = 1e9+7;

lli ExGCD(lli a, lli b, lli &x, lli &y){
    lli d=a;
    x=1; y=0;
    if(b!=0){ d=ExGCD(b, a%b, y, x); y-=a/b*x; }
    return d;
}
lli inverse(lli a){
    lli x,y;
    ExGCD(a, mod, x, y);
    return x>0? x: mod+x;
}

constexpr int arrmax=300001;
lli fact[arrmax];
lli inv[arrmax];
void maketable(){
    fact[0] = 1;
    for(int i=0; i<arrmax-1; i++){
        fact[i+1] = fact[i]*(i+1) %mod;
    }
    inv[arrmax-1] = inverse(fact[arrmax-1]);
    for(int i=arrmax-1; i>0; i--){
        inv[i-1] = inv[i]*i %mod;
    }
}
lli combination(lli n, lli r){
    if(r<0 or n<r) return 0;
    return fact[n] *inv[n-r] %mod *inv[r] %mod;
}

int main(){
    maketable();
    lli n,m,k;
    cin >> n >> m >> k;
    lli ans = 0;
    for(int i=0; i<=k; i++){
        int j = k-i;
        lli x = combination(n+2*i, i) -combination(n+2*i, i-1) +mod;
        lli y = combination(m+2*j, j) -combination(m+2*j, j-1) +mod;
        lli p = combination(n+m+2*k, n+2*i);
        ans += x%mod *y%mod *p%mod;
    }
    ans %= mod;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 7804
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<cstring>
#include<math.h>
#include<map>
using namespace std;
int main()
{
    long long n;
    while(cin>>n)
    {
        long long sum=0;
        long long m=(int)sqrt(sum);
        long long i;
        for( i=m;; i++)
        {
            if(i*i<=n)
                sum=i*i;
            else
                break;
        }
        cout<<sum<<endl;
    }

}


Measured memory_bytes: 256