akhauriyash/Code-Regression huggingface dataset:
n = int(input())
a = list(map(int, input().split()))
b = [0] * (n + 1)
for i in range(n):
    b[i + 1] = b[i] + a[i]
x = [[0, 0] for _ in range(n - 3)]
j = 1
for i in range(2, n - 1):
    while True:
        if i == j + 1:
            x[i - 2][0] = b[j]
            break
        if abs(b[i] - 2 * b[j]) > abs(b[i] - 2 * b[j + 1]):
            j += 1
        else:
            x[i - 2][0] = b[j]
            break
j = n - 1
for i in range(n - 2, 1, -1):
    while True:
        if i == j - 1:
            x[i - 2][1] = b[j]
            break
        if abs(b[n] + b[i] - 2 * b[j]) > abs(b[n] + b[i] - 2 * b[j - 1]):
            j -= 1
        else:
            x[i - 2][1] = b[j]
            break
ans = 1145141919810
for i in range(n - 3):
    s = [x[i][0], b[i + 2] - x[i][0], x[i][1] - b[i + 2], b[n] - x[i][1]]
    ans = min(ans, max(s) - min(s))
print(ans)

Measured memory_bytes: 45736
x, y = map(int, input().split())
x_rev = -x
y_rev = -y
ans_list = [y-x, y-x_rev+1, y_rev-x+1, y_rev-x_rev+2]
m = 100000000000
for i in ans_list:
    if i >= 0:
        m = min(i,m)
print(m)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;

const int maxn = 2010;
int n, K, ans, d[maxn][maxn];
vector<int> G[maxn];
queue<int> q;
vector<int> V;

int main() {
    scanf("%d %d", &n, &K);
    for (int i = 1, u, v; i < n; i++) {
        scanf("%d %d", &u, &v);
        G[u].push_back(v), G[v].push_back(u);
    }
    memset(d, -1, sizeof(d));
    for (int i = 1; i <= n; i++) {
        q.push(i), d[i][i] = 0;
        while (!q.empty()) {
            int v = q.front(); q.pop();
            if (i == 1) V.push_back(v);
            for (int u : G[v]) if (!~d[i][u]) {
                q.push(u), d[i][u] = d[i][v] + 1;
            }
        }
    }
    for (int i = 0; i < V.size(); i++) {
        int cur = 1;
        for (int j = 0; j < i; j++) {
            if (d[V[i]][V[j]] <= K) cur++;
        }
        ans = max(ans, cur);
    }
    printf("%d\n", n - ans);
    return 0;
}

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

constexpr auto EPS = 1e-9;

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

  int64_t w, h, x, y;
  cin >> w >> h >> x >> y;
  auto rect = w * h / 2.0;
  auto center_x = w / 2.0;
  auto center_y = h / 2.0;
  auto duplicate = abs (center_x - x) < EPS && abs (center_y - y) < EPS;
  cout << fixed << setprecision (15) << rect << " " << duplicate << endl;
}



Measured memory_bytes: 256
#include<stdio.h>
int main()
{
  int i,Ai,Bi,j,n,max=0;
  scanf("%d", &n);
  for(i=0;i<n;i++)
    {
      scanf("%d %d" ,&Ai,&Bi);
      if(max<=Ai)
	{
	  max=Ai;
	  j=Bi;
	}
    }
  printf("%d",max+j);
  return 0;
}


Measured memory_bytes: 128
def examB():
    N, M =LI()
    ans = [0]*N
    for i in range(M):
        a, b = LI()
        ans[a-1] +=1
        ans[b-1] +=1
    for v in ans:
        print(v)

import sys
import copy
import bisect
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examB()


Measured memory_bytes: 38256
#include <stdio.h>

int main(){
	int N, K, res=1;
	scanf("%d", &N);
	scanf("%d", &K);
	int *ptrK = &K;
	for(int i=1; i<=N; i++){
		if(res*2<res+K){
			res *= 2;
		}else{
			res += K;
		}
	}
	printf("%d\n", res);
	return 0;
}

Measured memory_bytes: 1732
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <chrono>
#include <climits>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

template <class T1, class T2>
ostream& operator << (ostream& out, const pair <T1, T2> p)
{
	out << '(' << p.first << ',' << p.second << ')';
	return out;
}

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

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

template <class T>
ostream& operator << (ostream& out, const vector<vector<T>> &v)
{
	for (const vector<T> &x : v)
		out << x << '\n';
	return out;
}

template <class T>
ostream& operator << (ostream& out, const vector<T> &v)
{
	for (const T &x : v)
		out << x << ' ';
	return out;
}

long long gcd (long long a, long long b)
{
	if (b > a)
		swap(a, b);
	return (b ? gcd(b, a % b) : a);
}

using ll   = long long;
using pii  = pair<int, int>;
using pll  = pair<long long, long long>;
using tiii = pair<pair<int, int>, int>;
using vi   = vector<int>;
using vl   = vector<long long>;
using vvi  = vector<vector<int>>;
using vvl  = vector<vector<long long>>;

#define F          first
#define S          second
#define First      first.first
#define Second     first.second
#define Third      second
#define mp         make_pair
#define rep(i,a,b) for (int i = (a); i < (b); i++)
#define per(i,b,a) for (int i = (b); i > (a); i--)
#define all(x)     x.begin(), x.end()
#define ret(x)     return cout << x, 0;
#define throwex    throw runtime_error ("Found the error.");

const int h = 1000000007;

signed main()
{
	ios::sync_with_stdio(false);
	#ifdef ONLINE_JUDGE
	cin.tie(nullptr);
	cout.tie(nullptr);
	cerr.setstate(ios::failbit);
	#endif

	ll x;
	cin >> x;
	ll y  = 0, m = 100;
	while(m < x)
	{
		y++;
		m += (m / 100);
	}
	cout << y;
}


Measured memory_bytes: 3636
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,b) FOR(i,0,b)
#define INF 1e9

int ans(int N, int K)
{
  int r = 1;
  REP(i,N) r = min(r*2, r+K);

  return r;
}

int main()
{
  int N,K;

  cin>>N>>K;

  cout<<ans(N,K)<<endl;

  return 0;
}

Measured memory_bytes: 256
import java.util.Map;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] H = new int[N];
        for (int i = 0; i < N; i++) {
            H[i] = sc.nextInt();
        }

        int max = H[0];
        int cnt = 1;

        for (int i = 1; i < N ; i++) {
            if (max <= H[i]) {
                max = H[i];
                cnt++;
            }
        }

        System.out.println(cnt);
    }
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N ((ll)301*1000)
#define MOD ((ll)1e9+7)

ll n,a[N];

bool check(ll x)
{
	set <ll> s;
	ll now=0;
	for(int i=0;i<=x;i++)now+=a[i];
	for(ll i=x+1;i<n;i++)s.insert(a[i]);
	while(s.size())
	{
		if(*s.begin()>2*now)return 0;
		now+=*s.begin();s.erase(s.begin());
	}
	return 1;
}

int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n;
	for(ll i=0;i<n;i++)cin>>a[i];
	sort(a,a+n);
	ll l=-1,r=n-1;
	while(l<r-1)
	{
		ll mid=(l+r)/2;
		if(check(mid))r=mid;
		else l=mid;
	}
	cout<<n-r<<"\n";
	return 0;
}

Measured memory_bytes: 5760
<?php
//error_reporting(0);
$S = trim(fgets(STDIN));
//list($N,$M,$K) = explode(" ",trim(fgets(STDIN)));
//$a[] = array_map('intval',explode(" ",trim(fgets(STDIN))));

if ($S=="AAA" || $S=="BBB") {
  printf("No\n");
}
else {
  printf("Yes\n");
}


Measured memory_bytes: 4856
n=int(input())
a=list(map(int,input().split()))
ans=0
cum=[0]
for i in range(n):
    cum.append((cum[i]+a[i])%(10**9+7))
for i in range(n):
    # print(a[i],cum[-1]-cum[i+1])
    ans+=a[i]*(cum[-1]-cum[i+1])%(10**9+7)
    ans%=(10**9+7)
print(ans)

Measured memory_bytes: 102020
N, K = map(int, input().split())
S = list(input())
if S[K-1] == 'A':
    S[K-1] = 'a'
elif S[K-1] == 'B':
    S[K-1] = 'b'
else:
    S[K-1] = 'c'
print(''.join(S))


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

int main(){
  int n;cin>>n;
  int res=0;
  vector <int> L(n);
  for(int i=0;i<n;++i) cin >> L[i];
  for(int i=1;i<n;++i){
    if(L[i-1] == L[i]){
      L[i] = -1;
      ++res;
    }
  }
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 256
package main
import "fmt"
func main(){
    var n int
    fmt.Scan(&n)
    
    var p int
    cnt := 0
    for i := 0; i < n; i ++{
        fmt.Scan(&p)
        if p != i + 1{
            cnt++
        }
    }
    if cnt <= 2{
        fmt.Println("YES")
    }else{
        fmt.Println("NO")
    }
}


Measured memory_bytes: 512
import java.util.Scanner;
import java.util.HashMap;
import java.util.Map;
import java.util.Arrays;
import java.io.PrintWriter;

public class Main { //クラス名はMain
    public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      PrintWriter out = new PrintWriter(System.out);
      int num = Integer.parseInt(sc.next());
      Map<String, Integer> map = new HashMap<>();
      long ans = 0;
      for(int i = 0;i<num;i++){
        char[] c = sc.next().toCharArray();
        Arrays.sort(c);
        String str = String.valueOf(c);
        if(map.containsKey(str)){
          int v = map.get(str);
          ans += v;
          map.put(str,v+1);
        }else map.put(str,1);
      }
      out.println(ans);
      out.flush();
    }
}


Measured memory_bytes: 53524
#include<bits/stdc++.h>
using namespace std;
 
main()
{
  double n,d;
  cin>>n>>d;
  
  int count=0;
  for(int i=0;i<n;i++)
  {
  	double x,y;
    cin>>x>>y;
    double dst=sqrt((x*x)+(y*y));
    if(dst<=d)
      count++;
  }
  cout<<count;
}


Measured memory_bytes: 3840
#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
#include <map>
#include <set>

using namespace std;

typedef long long i64;
typedef i64 int_t;
typedef vector<int_t> vi;
typedef vector<vi> vvi;

typedef pair<int_t, int_t> pi;

#define tr(c, i) for(auto i = (c).begin(); i != (c).end(); i++)
#define pb push_back
#define sz(a) int((a).size())
#define all(c) (c).begin(), (c).end()
#define REP(s, e, i) for(i=(s); i < (e); ++i)

i64 solve(const vector<pi> &v) {
  i64 N = sz(v), i;
  multiset<pi> sl, sr;
  REP(0, N, i) {
    sl.insert(v[i]);
    sr.insert(pi(v[i].second, v[i].first));
  }

  i64 ans = 0;
  i64 pos = 0;
  while(!sl.empty()) {
    auto l_max = sl.end();
    auto r_min = sr.begin();
    l_max--;
    if(l_max->first <= pos) {
      if(r_min->first >= pos) {
	break;
      }
    }
    else {
      i64 dlm = abs(pos - l_max->first);
      ans += dlm;
      pos = l_max->first;
      sr.erase(sr.find(pi(l_max->second, l_max->first)));
      sl.erase(l_max);
    }

    if(sl.empty()) {
      break;
    }
    l_max = sl.end();
    l_max--;
    r_min = sr.begin();
    if(r_min->first >= pos){
      if(l_max->first <= pos) {
	break;
      }
    }
    else {
      i64 drm = abs(pos - r_min->first);
      ans += drm;
      pos = r_min->first;
      sl.erase(sl.find(pi(r_min->second, r_min->first)));
      sr.erase(r_min);
    }
  }
  ans += abs(pos);
  return ans;
}

int main(int argc, char *argv[]) {

  i64 N, i;
  cin >> N;
  vector<pi> i1(N), i2(N);
  REP(0, N, i) {
    cin >> i1[i].first >> i1[i].second;
    i2[i].first = - i1[i].second;
    i2[i].second = - i1[i].first;
  }

  cout << max(solve(i1), solve(i2)) << endl;

  return 0;
}


Measured memory_bytes: 15872
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<string>
#include<map>
#include<set>
#include<functional>
#include<list>
#include<bitset>
#include<numeric>
using namespace std;
typedef long long ll;
typedef pair<int, int> p;

int main() {
	string s;

	cin >> s;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == 'C') {
			for (int j = i + 1; j < s.size(); j++) {
				if (s[j] == 'F') {
					cout << "Yes"<<endl;
					return 0;
				}
			}
		}
	}
	cout << "No"<<endl;
	return 0;
}


Measured memory_bytes: 256
h, w=[int(i) for i in input().split()]

field = []

for i in range(h):
	field.append( input())

for i in range(h):
	for j in range(w):
		if field[i][j] == ".":
			hmin = max(i-1, 0)
			hmax = min(i+1, h-1)
			wmin = max(j-1, 0)
			wmax = min(j+1, w-1)
			count = 0
			for m in range(hmin, hmax+1):
				for n in range(wmin, wmax+1):
					if field[m][n] == "#":
						count+=1

#			print (count)
			# field[i][j] = count
			field[i] = field[i][0:j]+ str(count) + field[i][j+1:]


for i in range(h):
	print (field[i])


Measured memory_bytes: 3064
#include<iostream>
using namespace std;
int main(){
  while(1){
    int n,q,i,j,m,d,c[101]={},a=0,mx=-1;
    cin>>n>>q;
    if(n==0)break;
    for(i=0;i<n;i++){
      cin>>m;
      for(j=0;j<m;j++){
	cin>>d;
	c[d]++;
	if(c[d]>mx&&c[d]>=q){
	  mx=c[d];
	  a=d;
	}
	else if(mx==c[d]&&a>d)a=d;
      }
    }
    cout<<a<<endl;
  }
  return 0;
}

Measured memory_bytes: 1160
// I SELL YOU...! 
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
signed main(){
  ll m,ans=0,cnt=0;
  ll sum = 0;
  cin >> m;
  ll d[m],c[m];
  for(int i=0;i<m;i++){
    cin >> d[i] >> c[i];
    sum += d[i]*c[i];
    cnt += c[i];
  }
  cout <<cnt-1 + (sum-1)/9 << endl;
}


Measured memory_bytes: 3328
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>   
#include<limits.h>
using namespace std;
#define i64  long long
#define lint long long

#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807

void solve()
{
  int A,B;
  cin>>A>>B;
  if(A > 9) 
  {cout<<-1<<endl;
  return;
  }
  if(B > 9) 
  { 
    cout<<-1<<endl;
    return;
  }

  cout<<A*B<<endl;
  
  return;
}

int main(int argc, const char *argv[])
{

  solve();

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N,Q;
  string S;
  cin>>N>>Q;
  vector<int>R(Q);
  vector<int>L(Q);
  cin>>S;
  for(int i=0;i<Q;i++){
    cin>>L.at(i)>>R.at(i);
  }
  vector<int>AC(N);
  vector<int>CA(N);
  AC.at(0)=0;
  for(int i=1;i<N;i++){
    if(S.at(i-1)=='A'&&S.at(i)=='C'){
      AC.at(i)=AC.at(i-1)+1;
    }
    else{
      AC.at(i)=AC.at(i-1);
    }
  }
  for(int i=0;i<Q;i++){
    cout<<AC.at(R.at(i)-1)-AC.at(L.at(i)-1)<<endl;
  }
}

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

typedef long double ld;									// XD
#define int long long
#define PB push_back
#define all(x) (x).begin(),(x).end()
#define ii pair <int,int>
#define mii map <int,int>
#define vi vector<int>
#define vii vector< ii >
#define F first
#define S second
#define rep(i,a,b)  for(int i=a;i<b;i++)
#define rep1(i,a,b) for(int i=a;i<=b;i++)
#define repd(i,a,b) for(int i=a; i>=b; --i)
#define sz(x) (int)((x).size())
#define mem(a,x) memset(a,x,sizeof(a))
const long double PI=3.141592653589793238462643383279502884197169399375105820974944;
inline void io(){
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

const int mod = 1e9+7;
const int INF = 1e18;
const int maxn = 2e5+5;


void solve(){
	string s; cin>>s;
	int ans =0, cnt=0 ;
	int n = sz(s);
	rep(i, 0, n){
		if(s[i] == 'R') cnt++; else cnt= 0;
		ans = max(ans, cnt);
	}
	cout<<ans;
}
signed main() 
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); //io();
    cout<<setprecision(16);
    
    int tc=1;// cin>>tc; 
    while(tc--){
        solve();cout<<'\n';
    }
    return 0;
}



Measured memory_bytes: 3608
from collections import deque
 
H, W = [int(x) for x in input().split()]
cell = [list(input()) for i in range(H)]
 
painted = deque()
for h in range(H):
    for w in range(W):
        if cell[h][w] == '#':
            painted.append([h, w, 0])
 
ans = 0
while len(painted) > 0:
    blackcell = painted.popleft()
    for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        nh = blackcell[0] + dy
        nw = blackcell[1] + dx
        d = blackcell[2]
        if 0 <= nh < H and 0 <= nw < W and cell[nh][nw] == '.':
            cell[nh][nw] = '#'
            painted.append([nh, nw, d + 1])
        ans = d
 
print(ans)

Measured memory_bytes: 176092
#include "iostream"
#include "map"
using namespace std;

int n,a,alice=0,bob=0;
map<int, int,greater<int>> cards;
bool flag=true;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a;
		cards[a]++;
	}
	for(auto it=cards.begin();it!=cards.end();++it){
		if(it->second>1){
			for(int i=0;i<it->second;i++){
				if(flag){
					alice+=it->first;
					flag=false;
				}
				else{
					bob+=it->first;
					flag=true;
				}
			}
		}
		else{
			if(flag){
				alice+=it->first;
				flag=false;
			}
			else{
				bob+=it->first;
				flag=true;
			}
		}
	}
	cout<<alice-bob;
	return 0;
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
x, y = [], []
for i in range(n):
    if a[i] > b[i]:
        x.append(a[i] - b[i])
    else:
        y.append(b[i] - a[i])
ans = -1
if sum(x) >= sum(y):
    if sum(y) == 0:
        ans = 0
    else:
       dif = sum(x) - sum(y)
       x = sorted(x)
       index = 0
       total = 0
       while total + x[index] <= dif:
           total += x[index]
           index += 1
       ans = n - index
print(ans)


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

vector<P> primes(ll n){
    vector<P> ans;
    for(ll i=2; i*i<=n; i++){
        int cnt = 0;
        if(n%i!=0)continue;
        while(n%i==0){
            n/=i;
            cnt++;
        }
        ans.push_back(P(i,cnt));
    }
    if(n!=1)ans.push_back(P(n,1));
    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll a,b;cin>>a>>b;
    ll g = __gcd(a,b);
    vector<P> pr = primes(g);
    cout<<pr.size()+1<<endl;
    return 0;
}

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

#define pb push_back
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define REP(i,n) for(int _n=n, i=0;i<_n;++i)
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)
#define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;--i)
using ull = uint64_t;
using ll = int64_t;
using PII = pair<int, int>;
using VI = vector<int>;

string to_string(string s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string) 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 debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H); debug_out(T...); }
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

const ll mod = 1000000007;

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int H, W, K;
    cin >> H >> W >> K;
    int ans = H * W;
    vector<VI> grid(H, VI(W, 0));
    REP(i, H) {
    	string s;
    	cin >> s;
    	REP(j, W) {
    		grid[i][j] = s[j] - '0';
    	}
    }
    FOR(mask, 0, (1 << (H - 1)) - 1) {
    	int sum =  __builtin_popcount(mask);
    	VI cnt(sum + 1, 0);
    	// debug(sum);

    	for (int i = 0; i < W; i++) {
    		int idx = 0;
	    	int ss = 0;
	    	for (int j = 0; j < H; j++) {
				ss += grid[j][W - 1];
				if (ss > K) goto fail;
				if (mask & (1 << j)) {
					ss = 0;
				}
	    	}
    		REP(j, H) {
    			cnt[idx] += grid[j][i];
    			if (cnt[idx] > K) {
    				sum++;
    				cnt = VI(sum + 1, 0);
    				i--;
    				goto done;

    			}
    			if (mask & (1 << j)) {
    				idx++;
    			}
    		}
    		done:;
    	}
    	ans = min(ans, sum);
    	fail:;
    }
    cout << ans << endl;

}

Measured memory_bytes: 384
#include <iostream>

using namespace std;

int main(){
  int a;
  cin >> a;
  if(a%2 == 0){
    printf("%lf\n", (a/2.0) / (double)a );
  }else{
    printf("%lf\n", (a/2+1) / (double)a );
  }
  return 0;
}


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

using namespace std;

using ll = long long;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<ll> a(n);
    ll s = 0, s2 = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        s += a[i];
        a[i] *= 2;
        if (i % 2 == 1) s2 += a[i];
    }

    vector<ll> ans(n);
    ans[0] = s - s2;
    for (int i = 0; i < n - 1; i++) {
        ans[i + 1] = a[i] - ans[i];
    }

    for (int i = 0; i < n; i++) {
        cout << ans[i] << " \n"[i + 1 == n];
    }
    return 0;
}

Measured memory_bytes: 2944
package main

import "fmt"

func main() {
	var h, n int
	fmt.Scan(&h, &n)

	a := make([]int, n)
	b := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&a[i], &b[i])
	}

	dp := [10100]int{}
	for i := 0; i < len(dp); i++ {
		dp[i] = 1e10
	}
	dp[h] = 0

	for i := 0; i < n; i++ {
		for hp := h; hp >= 0; hp-- {
			hpp := max(0, hp-a[i])
			dp[hpp] = min(
				dp[hpp],
				dp[hp]+b[i],
			)
		}
	}

	fmt.Println(dp[0])
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}


Measured memory_bytes: 640
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int A = Integer.parseInt(sc.next());
        int B = Integer.parseInt(sc.next());

        System.out.println(Math.max(A + B, Math.max(A - B, A * B)));
    }
}

Measured memory_bytes: 23764
import java.util.*;

public class Main {
    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Map<String, Integer> freq = new HashMap<>();
        for(int i = 0; i < n; i++) {
        	String s = sc.next();
        	freq.put(s, freq.getOrDefault(s, 0) + 1);
        }
		int m = sc.nextInt();
        for(int i = 0; i < m; i++) {
        	String s = sc.next();
        	freq.put(s, freq.getOrDefault(s, 0) - 1);
        }
        int max = 0;
        for(int v : freq.values())
        	max = Math.max(v, max);
        System.out.println(max);
    }
}


Measured memory_bytes: 21716
ABM = input().split()
A = int(ABM[0])
B = int(ABM[1])
M = int(ABM[2])

A_list = []
tmp = input().split()
for i in range(A):
  A_list.append(int(tmp[i]))
  
B_list = []
tmp = input().split()
for i in range(B):
  B_list.append(int(tmp[i]))
  
  
min_ = min(A_list)+min(B_list)

  
for i in range(M):
  tmp = input().split()
  tmp_goukei = A_list[int(tmp[0])-1]+B_list[int(tmp[1])-1]-int(tmp[2])
  if tmp_goukei < min_:
    min_ = tmp_goukei

print(min_)

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

int main(){
//srandom((unsigned long)time(NULL));

int n;
cin>>n;
int a[2][n];
for(int i=0;i<2;i++){
    for(int j=0;j<n;j++){
        cin>>a[i][j];
    }
}
int mx=0;
for(int c=0;c<n;c++){
    int cnt=0;
    for(int i=0;i<=c;i++){
        cnt+=a[0][i];
    }
    for(int i=c;i<n;i++){
        cnt+=a[1][i];
    }
    mx=max(mx,cnt);
}
cout<<mx<<endl;

return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader
import java.io.InputStream
import java.io.InputStreamReader
import java.util.*

fun main(args : Array<String>) {
    val scan = FastScanner(System.`in`)

    var s = scan.next()
    val q = Integer.parseInt(scan.next())

    var rvFlag = false
    val str = ArrayDeque<Char>(s.toList())

    repeat(q) {
        val q1 = Integer.parseInt(scan.next())

        if (q1 == 1) {
            rvFlag = !rvFlag
        } else {
            val q2 = Integer.parseInt(scan.next())
            val c = scan.next()[0]

            if (rvFlag) {
                if (q2 == 1) {
                    str.addLast(c)
                } else {
                    str.addFirst(c)
                }
            } else {
                if (q2 == 1) {
                    str.addFirst(c)
                } else {
                    str.addLast(c)
                }
            }
        }
    }

    if (rvFlag) {
        println(str.reversed().joinToString(separator = ""))
    } else {
        println(str.joinToString(separator = ""))
    }
}

class FastScanner(s: InputStream) {
    private var st = StringTokenizer("")
    private val br = BufferedReader(InputStreamReader(s))

    fun next(): String {
        while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine())

        return st.nextToken()
    }

    fun nextInt() = next().toInt()
    fun nextLong() = next().toLong()
    fun nextLine() = br.readLine()
    fun nextDouble() = next().toDouble()
    fun ready() = br.ready()
}

Measured memory_bytes: 59820
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <utility>
#include <functional>
#include <deque>
#include <cctype>
#include <stack>
#include <bitset>
#include <set>

using namespace std;
using ll = long long;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

const ll MOD = 1000000007;
const ll INF = 1 << 30;
const ll INF2 = 9000000000000000000LL;
const double INF3 = 900000000000000;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
const int tx[8] = { -1,0,1,-1,1,-1,0,1 }, ty[8] = { -1,-1,-1,0,0,1,1,1 };
#define ALL(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define sc second


int main() {
	int h, w, a[30] = { 0 };
	cin >> h >> w;
	for (int i = 0;i < h;i++) {
		for (int j = 0;j < w;j++) {
			char c;
			cin >> c;
			a[(int)c - 'a']++;
		}
	}
	bool fl = false;
	if (h % 2 == 0 && w % 2 == 0) {
		for (int i = 0;i < 26;i++) {
			if (a[i] % 4 != 0)fl = true;
		}
		if (!fl)cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	else if (h % 2 == 1 && w % 2 == 0 || h % 2 == 0 && w % 2 == 1) {
		int cnt = 0;
		for (int i = 0;i < 26;i++) {
			if (a[i] % 4 == 0){}
			else if (a[i] % 2 == 0 && a[i] % 4 == 2)cnt += 2;
			else fl = true;
		}
		if (h % 2 == 1) {
			if (fl || cnt > w)cout << "No" << endl;
			else cout << "Yes" << endl;
		}
		else if (w % 2 == 1) {
			if (fl || cnt > h)cout << "No" << endl;
			else cout << "Yes" << endl;
		}
	}
	else {
		int odd = 0;
		for (int i = 0;i < 26;i++) {
			if (a[i] % 2 == 1)odd++;
		}
		if (odd > 1)cout << "No" << endl;
		else {
			int cnt = 0;
			for (int i = 0;i < 26;i++) {
				if (a[i] % 4 == 0) {}
				else if (a[i] % 2 == 0 && a[i] % 4 == 2)cnt += 2;
				else {
					if ((a[i] - 1) % 2 == 0 && (a[i] - 1) % 4 == 2)cnt += 2;
				}
			}
			if (cnt > h*w - ((h / 2)*(w / 2)) * 4 - 1)cout << "No" << endl;
			else cout << "Yes" << endl;
		}
	}
}

Measured memory_bytes: 256
package main

import (
	"fmt"
	"sort"
)

func main() {
	var (
		s string
		t string
	)
	fmt.Scan(&s, &t)

	sMap := make(map[rune]int)
	tMap := make(map[rune]int)
	for _, r := range s {
		sMap[r]++
	}
	for _, r := range t {
		tMap[r]++
	}

	var (
		sVals []int
		tVals []int
	)

	for _, v := range sMap {
		sVals = append(sVals, v)
	}
	for _, v := range tMap {
		tVals = append(tVals, v)
	}

	sort.Ints(sVals)
	sort.Ints(tVals)

	for i := 0; i < len(sVals); i++ {
		if sVals[i] != tVals[i] {
			fmt.Println("No")
			return
		}
	}
	fmt.Println("Yes")
}


Measured memory_bytes: 2176
#include <stdio.h>

int const NUM[3][13] = {
	{0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0},
	{0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0},
	{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
};

int main() {
	int x, y, size;
	int i, zero, max;
	int paper[100] = {0};
	int const *vrange;
	while (scanf(" %d,%d,%d", &x, &y, &size) != EOF) {
		int xrange[] = {
			x, x-1, x, x+1, x-2, x-1, x, x+1, x+2, x-1, x, x+1, x
		};
		int yrange[] = {
			y-2, y-1, y-1, y-1, y, y, y, y, y, y+1, y+1, y+1, y+2
		};
		vrange = NUM[size-1];
		for (i = 0; i < 13; i++) {
			if (xrange[i] < 0 || 9 < xrange[i] ||
				yrange[i] < 0 || 9 < yrange[i]) {
				continue;
			}
			paper[xrange[i] + yrange[i] * 10] += vrange[i];
		}
	}
	zero = max = 0;
	for (i = 0; i < 100; i++) {
		if (!paper[i])
			++zero;
		if (paper[i] > max)
			max = paper[i];
	}
	printf("%d\n%d\n", zero, max);
	return 0;
}

Measured memory_bytes: 600
n = int(input())

withdraw = [1, 6, 9, 36, 81, 216, 729, 1296, 6561, 7776, 46656, 59049]
min_draw = [0] * 100001
for i in range(1, n + 1):
    draw = []
    for j in withdraw:
        if j <= i:
            draw.append(min_draw[i - j] + 1)
            min_draw[i] = min(draw)
print(min_draw[i])

Measured memory_bytes: 3828
import numpy as np

data = input().split()

h = int(data[0])
w = int(data[1])

count = 0
# creating math
i = 0
math = []
while i < h:
    x = input()
    x = list(x)
    math.append(x)
    i += 1
math = np.array(math).reshape(h,w)


# row check

i = 0 # row
j = 0 # colum
while i < h:
    while j < w:
        if math[i][j] == ".":
            
            j += 1
            if j == w:
                math = np.delete(math,i,0)
                h = h-1
                i -=1
                
                
                
        else:
            break
    j = 0
    i += 1
i = 0
j = 0

# colum check

while j < w:
    while i < h:
        if math[i][j] == ".":
            
            i += 1
            if i == h:
                math = np.delete(math,j,1)
                w = w-1
                j -= 1
                
                
        else:
            break
    i = 0
    j += 1
i = 0
j = 0
while i < h:
    while j < w:
        print(*math[i][j],end = "")
        j += 1
    i += 1
    j = 0
    print()


    
    


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

const int mod = 1e9 + 7;
const long long INF = 1LL<<60;
using ll = long long;
using P = pair<int,int>;


// i番目の問題が採用されうるか否かを調べる
// 入れても構わない表の総数がmv以上になるかどうかを調べよ
bool isOK(int i, vector<long long> &a, long long n, long long m, long long v, int p){
    
    // はじめから上位p以内ならば無条件で採用される
    if (n - i <= p) return true;
    if (a[i] + m < a[n-p]) return false;
    
    // 入れられても構わない表の総数 >= mv かどうかを調べる
    long long comparison = m * v;
    
    long long res = 0;
    
    rep(j, n){
        
        if (a[j] <= a[i]) res += m; //a[i]以下の値ならば, m個入れ込んでOk
        else if (n - (p-1) <= j) res += m; //上位1, 2, ,,,p-1個にもm個入れ込んでOK
        else{
            res  = res + (a[i] + m - a[j]); //入れられても問題ない個数の上限である
        }
    }
    
    if (res >= comparison) return true; //ここの理屈はeditorial pdfに丁寧に書いてある.
    else return false;
    
}


int main(){
    long long n, m, v, p;
    cin >> n >> m >> v >> p;
    
    vector<long long> a(n);
    rep(i, n) cin >> a[i];
    
    sort(a.begin(), a.end());
    
    // 昇順ソートがポイントである
    // a[i] が採用されるならば, a[i+1],,,も採用される
    // 単調性がある
    // binary_serchである
    // めぐる式のアイデアを利用する
    
    int ng = -1; //絶対に条件を満たさない
    int ok = n; //条件を満たす最小のインデックスを表す
    
    while (abs(ok - ng) > 1){
        int mid = (ok + ng) / 2;
        
        if (isOK(mid, a, n, m, v, p)) ok = mid;
        else ng = mid;
        
        //cout << ng << " " <<  ok << endl;
    }
    
    int ans = n - ok; // okは0-indexベースで返されることに注意せよ
    cout << ans << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>

using namespace std;

int main(void) {
    int i, len, t1, t2;
    string s, s1, s2;
    cin >> s;
    len = s.length();
    s1 = s;
    s2 = s;
    t1 = 0;
    for (i=1;i<len;i++) {
        if (s1[i-1] == s1[i]) {
            t1++;
            s1[i] = 1-(s1[i]-'0')+'0';
        }
    }
    t2 = 0;
    for (i=0;i<len-1;i++) {
        if (s2[i] == s2[i+1]) {
            t2++;
            if (i>0) {
                if (s2[i-1] == s2[i]) s2[i] = 1-(s2[i]-'0')+'0';
                else s2[i+1] = 1-(s2[i+1]-'0')+'0';
            } else s2[i] = 1-(s2[i]-'0')+'0';
        }
    }

    cout << min(t1,t2) << endl;
    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define rep(i,N) for(long long i = 0; i < (long long)(N); i++)
#define repr(i,N) for(long long i = (long long)(N) - 1; i >= 0; i--)
#define rep1(i,N) for(long long i = 1; i <= (long long)(N) ; i++)
#define repr1(i,N) for(long long i = (N) ; (long long)(i) > 0 ; i--)
#define each(x,v) for(auto& x : v)
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define ini(...) int __VA_ARGS__; in(__VA_ARGS__)
#define inl(...) long long __VA_ARGS__; in(__VA_ARGS__)
#define ins(...) string __VA_ARGS__; in(__VA_ARGS__)
using namespace std; void solve();
using ll = long long; template<class T = ll> using V = vector<T>;
using vi = V<int>; using vl = V<>; using vvi = V< V<int> >;
constexpr int inf = 1001001001; constexpr ll infLL = (1LL << 61) - 1;
struct IoSetupNya {IoSetupNya() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(7);} } iosetupnya;
template<typename T, typename U> inline bool amin(T &x, U y) { return (y < x) ? (x = y, true) : false; }
template<typename T, typename U> inline bool amax(T &x, U y) { return (x < y) ? (x = y, true) : false; }
template<typename T, typename U> ostream& operator <<(ostream& os, const pair<T, U> &p) { os << p.first << " " << p.second; return os; }
template<typename T, typename U> istream& operator >>(istream& is, pair<T, U> &p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator <<(ostream& os, const vector<T> &v) { int s = (int)v.size(); rep(i,s) os << (i ? " " : "") << v[i]; return os; }
template<typename T> istream& operator >>(istream& is, vector<T> &v) { for(auto &x : v) is >> x; return is; }
void in(){} template <typename T,class... U> void in(T &t,U &...u){ cin >> t; in(u...);}
void out(){cout << "\n";} template <typename T,class... U> void out(const T &t,const U &...u){ cout << t; if(sizeof...(u)) cout << " "; out(u...);}
template<typename T>void die(T x){out(x); exit(0);}
#ifdef NyaanDebug
  #include "NyaanDebug.h"
  #define trc(...) do { cerr << #__VA_ARGS__ << " = "; dbg_out(__VA_ARGS__);} while(0)
  #define trca(v,N) do { cerr << #v << " = "; array_out(v , N);cout << endl;} while(0)
#else
  #define trc(...)
  #define trca(...)
  int main(){solve();}
#endif

#define in2(N,s,t) rep(i,N){in(s[i] , t[i]);}
#define in3(N,s,t,u) rep(i,N){in(s[i] , t[i] , u[i]);}
using vd = V<double>; using vs = V<string>; using vvl = V< V<> >;
template<typename T>using heap = priority_queue< T , V<T> , greater<T> >;

using P = pair<int,int>; using vp = V<P>;
constexpr int MOD = /** 1000000007; //*/ 998244353;
//////////////////

void solve(){
  ins(S);
  string T;
  rep(i , sz(S)){
    T.pb(S[i]);
    while(T.size() >= 2 && T.back()=='T' && T[sz(T)-2]=='S'){
      T.pop_back(); T.pop_back();
    }
  }
  out(sz(T));
}

Measured memory_bytes: 916
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>

using namespace std;

void b_ATCoder(void) {
	string s;
	cin >> s;

	int cnt = 0;
	int max_length = 0;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] != 'A' && s[i] != 'C' && s[i] != 'G' && s[i] != 'T') {
			max_length = max(max_length, cnt);
			cnt = 0;
		}
		else cnt++;
	}

	max_length = max(max_length, cnt);

	cout << max_length << endl;
}

int main()
{
    b_ATCoder();

    return 0;
}


Measured memory_bytes: 3604
#include<bits/stdc++.h>
using namespace std;
int P[3][1010][1010];
int main(){
  int h,w,n;
  cin >> h >> w >> n;
  memset(P,0,sizeof(P));
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      char c; cin >> c;
      for(int k=0;k<3;k++){
	P[k][i][j+1] = P[k][i][j];
      }
      if(c == 'J') P[0][i][j+1]++;
      else if(c == 'O') P[1][i][j+1]++;
      else P[2][i][j+1]++;
    }
  }
  for(int i=0;i<n;i++){
    int a,b,c,d; cin >> a >> b >> c >> d;
    int sum[3] = {0};
    for(int j=a-1;j<=c-1;j++){
      for(int k=0;k<3;k++){
	sum[k] += P[k][j][d] - P[k][j][b-1];
      }
    }
    int flg = 0;
    for(int j=0;j<3;j++){
      if(flg) cout << " ";
      cout << sum[j];
      flg = 1;
    }
    cout << endl;
  }
}

Measured memory_bytes: 13124
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <array>
#include <cassert>
#include <utility>
#include <vector>
#include <atcoder/all>

template <class InputIterator>
std::ostream& range_output(std::ostream& os_arg, InputIterator first_arg, InputIterator last_arg){ if(first_arg != last_arg){ do{ os_arg << *(first_arg++); if(first_arg == last_arg) break; os_arg << ' '; } while(true); }  return os_arg; }
template <class Tp> std::ostream& operator << (std::ostream& os_arg, const std::vector<Tp>& arr_arg){ return range_output(os_arg, arr_arg.cbegin(), arr_arg.cend()); }
template <class Tp, std::size_t Size> std::ostream& operator << (std::ostream& os_arg, const std::array<Tp, Size>& arr_arg){ return range_output(os_arg, arr_arg.cbegin(), arr_arg.cend()); }
template <class S, class T> std::ostream& operator << (std::ostream& os_arg, const std::pair<S, T>& pair_arg){ return os_arg << '(' << pair_arg.first << ", " << pair_arg.second << ')'; }

#ifndef ONLINE_JUDGE
    template <typename Head> void dump_out(Head head_arg){ std::cerr << head_arg << '\n'; }
    template <typename Head, typename... Tail>
    void dump_out(Head head_arg, Tail... tail_args){ std::cerr << head_arg << ", "; dump_out(tail_args...); }
    #define dump(...) do { std::cerr << "[in line " << __LINE__ << "] " << #__VA_ARGS__ << " : "; dump_out(__VA_ARGS__); } while(false)
#else
    #define dump(...) (void(0))
#endif

using mint = atcoder::modint998244353;
using S = std::pair<mint, int>;
using F = std::pair<mint, mint>;
S op(S x, S y){ return {x.first + y.first, x.second + y.second}; }
S e(void){ return {0, 0}; }
S mapping(F lazy, S val){ return {lazy.first * val.first + lazy.second * val.second, val.second}; }
F composition(F x, F y){
    return {x.first * y.first, x.first * y.second + x.second};
}
F id(void){ return {1, 0} ;}



using lazy_segment_t = atcoder::lazy_segtree<
    S,
    op,
    e,
    F,
    mapping,
    composition,
    id
>;

int main(void){
    std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); 
    std::cout << std::fixed << std::setprecision(16);
    int n, q; std::cin >> n >> q;
    std::vector<S> A(n);
    for(int i = 0; i < n; ++i){  int a; std::cin >> a; A[i].first = a; A[i].second = 1; }
    lazy_segment_t ST(A);
    while(q--){
        char c; int l, r; std::cin >> c >> l >> r;
        if(c == '0'){
            int b, c; std::cin >> b >> c;
            ST.apply(l, r, F(b, c));
        }
        else{
            std::cout << ST.prod(l, r).first.val() << '\n';
        }
    }

    return 0;
}

Measured memory_bytes: 19224
while True:

    n, m = list(map(int, input().split()))

    if n == 0 and m == 0:
        break

    medicines = set(map(int, input().split()))
    weights = list(map(int, input().split()))

    possibles = {0}

    for i in weights:
        pre = possibles.copy()
        for j in possibles:
            plus = i + j
            minus = abs(i - j)
            pre.add(plus)
            pre.add(minus)
        possibles = pre
    possibles.discard(0)

    medicines -= possibles

    if len(medicines) == 0:
        print(0)
        continue

    add = []

    for i in medicines:
        pre_add = {0}
        for j in possibles:
            plus = i + j
            minus = abs(i - j)
            pre_add.add(plus)
            pre_add.add(minus)
            pre_add.add(i)
            pre_add.discard(0)
        add.append(pre_add)

    ans = add[0]

    for i in add:
        pre_ans = ans & i
        ans = pre_ans

    ans_list = []

    for i in ans:
        ans_list.append(i)

    if len(ans_list) == 0:
        print(-1)
    elif len(ans_list) == 1:
        print(ans_list[0])
    else:
        print(min(ans_list))



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

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

using namespace std;

typedef long long ll;
const ll MOD = 1000000007LL;
int N;
ll fact[200000];

int bit[200000];
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<200000){
    bit[i] += x;
    i += i & -i;
  }
}

ll compute(vector<int> vec){
  ll ret = fact[vec.size()];
  set<int> S;
  rep(i,vec.size()) {
    ll coef = N - ( sum(N) - sum(vec[i]-1) ) - vec[i];
    assert( coef >= 0 );
    ret = ( ret -  ( coef * fact[N-i-1] ) % MOD + MOD ) % MOD;
    S.insert(vec[i]);
    add(vec[i],1);
  }
  return (ret-1LL+MOD)%MOD;
}

int main(){
  fact[0] = fact[1] = 1LL;
  REP(i,2,200000) fact[i] = ( fact[i-1] * ll(i) ) % MOD;
  while( cin >> N, N ){
    rep(i,N+1) bit[i] = 0;
    vector<int> vec(N);
    rep(i,N) vec[i] = i+1;
    int R;
    cin >> R;
    rep(_,R){
      int s,t;
      cin >> s >> t;
      --s, --t;
      swap(vec[s],vec[t]);
    }
    cout << compute(vec) << endl;
  }
  return 0;
}

Measured memory_bytes: 8444
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define SZ(c) int(c.size())
#define pb push_back
#define loop(i,start,n)  for(int i=start;i<n;i++)
#define rloop(i,start,n)  for(int i=start;i>n;i--)

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vi>;
using vs = vector<string>;
const ll inf = 2e9+3;

void solve(){
    int tc=1 ;
    //cin >> tc;
    while(tc--) {
        unordered_map<string, ll> m;
        ll n; cin >> n;
        m.insert({"AC",0});
        m.insert({"WA",0});
        m.insert({"TLE",0});
        m.insert({"RE",0});
        loop(i,0,n){
            string s; cin >> s;
            m[s]++;
        }
        cout << "AC" << " x " << m["AC"] << "\n";
        cout << "WA" << " x " << m["WA"] << "\n";
        cout << "TLE" << " x " << m["TLE"] << "\n";
        cout << "RE" << " x " << m["RE"] << "\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

Measured memory_bytes: 3580
#include <bits/stdc++.h>
#include <math.h>
int n,i,j,k,count1=0,count2=0;
using namespace std;
void ABC110(void);
void ABC111(void);
void ABC112(void);
void ABC113(void);
void ABC114(void);
void ABC115(void);
void ABC116(void);
void ABC117(void);
void ABC118(void);
void ABC119(void);

int main(void){
    ABC117();
}

void ABC117(){
    int sum=0;
    cin>>n;
    vector<int> vec(n);
    for(i=0;i<n;i++){
        cin>>vec[i];
        sum+=vec[i];
    }
    sort(vec.begin(),vec.end());
    reverse(vec.begin(),vec.end());
    if(vec[0]<(sum-vec[0]))cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

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

#define LL                      long long
#define Ulong                   unsigned long long
#define REP(i,n)                for(long long i=0; i < n ; i++ )
#define mp                      make_pair
#define pb                      push_back
#define all(x)                  (x).begin(),(x).end()
#define PI                      acos(-1.0)
#define EPS                     1e-14
#define F                       first
#define S                       second
#define di(x)                   int x; input(x)
#define in(x)                   input(x)
#define in2(x,y)                in(x),in(y)
#define in3(x,y,z)              in(x),in2(y,z)
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl
#define nl                      cout<<endl
#define ms(ara_name,value)      memset(ara_name,value,sizeof(ara_name))
#define IO                      ios_base::sync_with_stdio(0);cin.tie(0)
#define READ                    freopen("/home/matrixcode/Desktop/in.txt","r",stdin)
#define WRITE                   freopen("out.txt","w",stdout)
template<class T> inline void input(T &x) {
  register char c = getchar();x = 0;
  int neg = 0;
  for(; ((c<48 || c>57) && c != '-'); c = getchar());
  if(c=='-'){neg = 1;c = getchar();}
  for(; c>47 && c<58 ; c = getchar()){x = (x<<1) + (x<<3) + c - 48;}
  if(neg) x = -x;
}
inline long long bigmod(long long p,long long e,long long M){
  long long ret = 1;
  for(; e > 0; e >>= 1){
    if(e & 1) ret = (ret * p) % M;
    p = (p * p) % M;
  } return ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}

/***************************** END OF TEMPLATE *******************************/

const int N = 3e5+5;
int w[105];
int v[105];
LL dp[105][N];
int main()
{
  int n, W;
  in2(n,W);
  for(int i = 1; i <= n; i ++) {
    in2(w[i], v[i]);
  }

  for(int i = 1; i <= n; i ++) {
    for(int j = 0; j <=W; j ++) {
      dp[i][j] = dp[i-1][j];
      if(w[i] <= j) {
        dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + v[i]);
      }
    }
  }
  LL iMax = INT_MIN;
  for(int i = 0; i <= W; i ++ ) iMax = max(iMax, dp[n][i]);
  cout << iMax << endl;
}


Measured memory_bytes: 233728
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
#define LOG 20
#define SIZE 200000
vector<int>pat[SIZE];
int par[LOG][SIZE];
int dep[SIZE];
bool flag[SIZE];
void dfs(int node, int d)
{
	if (flag[node])return;
	flag[node] = true;
	dep[node] = d;
	for (int i = 0; i < pat[node].size(); i++)
	{
		if (!flag[pat[node][i]])
		{
			par[0][pat[node][i]] = node;
			dfs(pat[node][i], d + 1);
		}
	}
}
void lcainit(int num)
{
	for (int i = 1; i < LOG; i++)
	{
		for (int j = 0; j < num; j++)
		{
			par[i][j] = par[i - 1][par[i - 1][j]];
		}
	}
}
bool isanc(int a, int b)
{
	for (int i = 19; i >= 0; i--)if (dep[a] >= dep[b] + (1 << i))a = par[i][a];
	return a == b;
}
vector<int>np[SIZE];
bool iswin[SIZE];
int maxi = 0;
void calc(int node, int t)
{
	if (flag[node])return;
	flag[node] = true;
	if (t >= dep[node])return;
	if (iswin[node])maxi = 1000000000;
	maxi = max(maxi, dep[node]);
	for (int i = 0; i < np[node].size(); i++)calc(np[node][i], t + 1);
}
int main()
{
	int num, st, root;
	scanf("%d%d%d", &num, &st, &root);
	st--, root--;
	for (int i = 0; i < num - 1; i++)
	{
		int za, zb;
		scanf("%d%d", &za, &zb);
		za--, zb--;
		np[za].push_back(zb);
		np[zb].push_back(za);
	}
	for (int i = 0; i < num - 1; i++)
	{
		int za, zb;
		scanf("%d%d", &za, &zb);
		za--, zb--;
		pat[za].push_back(zb);
		pat[zb].push_back(za);
	}
	dfs(root, 0);
	par[0][root] = root;
	lcainit(num);
	for (int i = 0; i < num; i++)
	{
		for (int j = 0; j < np[i].size(); j++)
		{
			int y = np[i][j];
			if (!isanc(y, par[0][i]) && par[0][par[0][i]] != y)iswin[i] = true;
		}
	}
	fill(flag, flag + num, false);
	calc(st, 0);
	if (maxi == 1000000000)printf("-1\n");
	else printf("%d\n", maxi * 2);
}

Measured memory_bytes: 47484
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

public class Main {
	static long ans = 0;
	static int n;
	static List<List<Integer>> list;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] sa = br.readLine().split(" ");
		n = Integer.parseInt(sa[0]);
		list = new ArrayList<>(n);
		for (int i = 0; i < n; i++) {
			list.add(new ArrayList<>());
		}
		for (int i = 0; i < n - 1; i++) {
			sa = br.readLine().split(" ");
			int a = Integer.parseInt(sa[0]) - 1;
			int b = Integer.parseInt(sa[1]) - 1;
			list.get(a).add(b);
			list.get(b).add(a);
		}
		br.close();

		dfs(0, -1);
		long n2 = power(2, n);
		ans = divide(ans, n2, 1000000007);
		System.out.println(ans);
	}

	static long divide(long a, long b, int m) {
		BigInteger ba = BigInteger.valueOf(a);
		BigInteger bm = BigInteger.valueOf(m);
		BigInteger bb = BigInteger.valueOf(b).modInverse(bm);
		return ba.multiply(bb).mod(bm).longValue();
	}

	static int dfs(int x, int p) {
		long val = power(2, n - 1) - 1;
		int sum = 1;
		for (int i : list.get(x)) {
			if (i == p) {
				continue;
			}
			int num = dfs(i, x);
			val -= power(2, num) - 1;
			sum += num;
		}
		val -= power(2, n - sum) - 1;
		ans += val;
		return sum;
	}

	static long power(long x, long n) {
		if (n == 0) {
			return 1;
		}
		int mod = 1000000007;
		long val = power(x, n / 2);
		val = val * val % mod;
		if (n % 2 == 1) {
			val = val * x % mod;
		}
		return val;
	}
}


Measured memory_bytes: 100276