akhauriyash/Code-Regression huggingface dataset:
N,M=map(int, input().split())
#島、橋
class UnionFind():
  # 作りたい要素数nで初期化
  # 使用するインスタンス変数の初期化
  def __init__(self, n):
    self.n = n
    # root[x]<0ならそのノードが根かつその値が木の要素数
    # rootノードでその木の要素数を記録する
    self.root = [-1]*(n+1)
    # 木をくっつける時にアンバランスにならないように調整する
    self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
    # ここで代入しておくことで、後の繰り返しを避ける
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]

    # 木の併合、入力は併合したい各ノード
  def Unite(self, x, y):
    # 入力ノードのrootノードを見つける
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    # すでに同じ木に属していた場合
    if (x == y):
      return 
      # 違う木に属していた場合rnkを見てくっつける方を決める
      #rnkが大きい方に結合
    elif (self.rnk[x] > self.rnk[y]):
      self.root[x] += self.root[y]
      self.root[y] = x

    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      # rnkが同じ（深さに差がない場合）は1増やす
      if(self.rnk[x] == self.rnk[y]):
        self.rnk[y] += 1

  # xとyが同じグループに属するか判断
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  # ノードxが属する木のサイズを返す
  def Count(self, x):
    return -self.root[self.Find_Root(x)]

L=[]
for i in range(M):
  a,b=map(int, input().split())
  L.append((a-1,b-1))
uni=UnionFind(N)
ans=[0]*M
L=reversed(L)
for i,t in enumerate(L):
  a,b=t
  ca=uni.Count(a)
  cb=uni.Count(b)
  if uni.isSameGroup(a,b):
    ans[-(i+1)]=0
  else:
    ans[-(i+1)]=uni.Count(a)*uni.Count(b)
  uni.Unite(a,b)
final=[0]*M
final[0]=ans[0]
#print(ans)
for i in range(1,M):
  final[i]=final[i-1]+ans[i]
for f in final:
  print(f)
   

Measured memory_bytes: 23220
#include <iostream>
#include <algorithm>
using namespace std;
long long v[7];
int main() {
	for (int i = 0; i < 7; i++) cin >> v[i];
	long long I = v[0], O = v[1], J = v[3], L = v[4];
	long long ret = 0;
	for (long long i = 0; i <= min({ I, J, L, 1LL }); i++) {
		ret = max(ret, (I - i) / 2 * 2 + (J - i) / 2 * 2 + (L - i) / 2 * 2 + i * 3);
	}
	cout << ret + O << endl;
	return 0;
}

Measured memory_bytes: 256
import numpy as np
N = int(input())

c = np.zeros((10,10),dtype = int)

for k in range(1,N+1):
	c[int(str(k)[0])][int(str(k)[-1])] += 1

ans = 0
for i in range(10):
	for j in range(10):
		ans += c[i][j]*c[j][i]
print(ans)

Measured memory_bytes: 14272
import sys
readline = sys.stdin.readline


def main():
    a,b,q = map(int,readline().split())
    A = [int(readline()) for i in range(a)]
    B = [int(readline()) for i in range(b)]
    def search(A,x):
        left =0
        right = len(A)-1
        
        if x<A[0]:
            return (float('inf'),abs(x - A[left]))
        if x >A[-1]:
            return (abs(x - A[right]),float('inf'))
        
        while left != right-1:
            center = (left+right)//2
            
            if A[center] > x:
                right = center
            else:
                left = center
        
        return (abs(x - A[left]),abs(x - A[right]))
    
    
    def dist(A,x,lr):
        if lr == float('inf'):
            return float('inf')
        return abs(x - A[lr])
    
    for _ in range(q):
        x = int(readline())
        sl,sr = search(A,x)
        tl,tr = search(B,x)
        print(min(min(sl,sr)+min(tl,tr)+min(min(sl,sr),min(tl,tr)),max(sl,tl),max(sr,tr)))

if __name__ == '__main__':
    main()

Measured memory_bytes: 12164
while (1):
    try:
        s=raw_input()
    except EOFError:
        break
    B=False
    if s[0]==s[4]==s[8]=="o":
        print "o"
        B=True
    elif s[0]==s[4]==s[8]=="x":
        print "x"
        B=True
    if s[2]==s[4]==s[6]=="o":
        print "o"
        B=True
    elif s[2]==s[4]==s[6]=="x":
        print "x"
        B=True
    for i in range(3):
        if s[i*3]==s[i*3+1]==s[i*3+2]=="o":
            print "o"
            B=True
            break
        elif s[i*3]==s[i*3+1]==s[i*3+2]=="x":
            print "x"
            B=True
            break
        elif s[i]==s[i+3]==s[i+6]=="o":
            print "o"
            B=True
            break
        elif s[i]==s[i+3]==s[i+6]=="x":
            print "x"
            B=True
            break
    if B==False:
        print "d"

Measured memory_bytes: 4276
import sys
from collections import deque
import copy
import math

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N] = [(input_raw[0])]
    a = 0
    for s in N:
        a += int(s)

    if int(N) % a == 0:
        print "Yes"
    else:
        print "No"

if __name__ == '__main__':
    main()


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

using ll = long long;
#define debug(x) cerr << #x << ": " << x << endl;
#define line() cerr << "---------------" << endl;

int main() {
   string s;
   cin >> s;
   vector<int> v(s.size());
   for (int i = 0; i < v.size(); i++) {
      v[i] = s[i] - '0';
   }

   ll ans = 0;
   for (ll mask = 0; mask < (1 << (v.size()) - 1); mask++) {
      string t = to_string(v[0]);
      for (int i = 0; i < v.size()-1; i++) {
         if ( (mask>>i) & 1 ) {
            t += '+';
         }
         t += to_string(v[i+1]);
      }
      ll sum = 0;
      string a;
      for (int i = 0; i < t.size(); i++) {
         if (t[i] == '+') {
            sum += stoll(a);
            a = "";
         } else {
            a += t[i];
         }
      }
      sum += stoll(a);
      ans += sum;
   }

   cout << ans << endl;

   return 0;
}

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

const int INF = 1000000000;
const int N = 50;

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

  int n;
  cin >> n;

  vector<vector<int>> cnt(N, vector<int> (N));

  for (int i = 0; i < n; i++) {
    double x;
    cin >> x;

    int y = llround(x * INF);
    int two = 0;
    int five = 0;
    while(y % 2 == 0) {
      y /= 2;
      two++;
    }
    while(y % 5 == 0) {
      y /= 5;
      five++;
    }
    cnt[two][five]++;
  }

  int answer = 0;
  for (int two1 = 0; two1 < N; two1++) {
    for (int five1 = 0; five1 < N; five1++) {

      for (int two2 = 0; two2 < N; two2++) {
        for (int five2 = 0; five2 < N; five2++) {
          int tmp = 0;
          if(two1 + two2 >= 18 && five1 + five2 >= 18) {
            if(two1 == two2 && five1 == five2) tmp = cnt[two1][five1] * (cnt[two1][five1] - 1);
            else
              tmp = cnt[two1][five1] * cnt[two2][five2];
          }
          answer += tmp;
        }
      }

    }
  }

  cout << answer/2 << '\n';

  return 0;
}

Measured memory_bytes: 3732
n = int(input())
a = list(map(int,input().split()))

d = {}
for i in a:
    if i in d:
        d[i] += 1
    else:
        d[i] = 1

ans = sum(a)
q = int(input())

for i in range(q):
    b,c = map(int,input().split())
    if b in d:
        ans -= b * d[b]
        ans += c * d[b]
        if c in d:
            d[c] += d[b]
        else:
            d[c] = d[b]
        d[b] = 0
    print(ans)


Measured memory_bytes: 85376
/*
 KUNAL RAUT (ZUKONIT14)  :- "DO WHAT YOU LIKE!"
 -PICT,PUNE! :)
 */
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define ld long double
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define mod 1000000007
#define mod9 1000000009
#define pi 3.1415926535
#define MAXN 1000005
#define N 1000001
#define MAX2N 1*1000 + 10
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define ms(s, n) memset(s, n, sizeof(s))
#define prec(n) fixed<<setprecision(n)
#define forci(p,n) for(ll i=p;i<(ll)n;i++)
#define forcj(p,n) for(ll j=p;j<(ll)n;j++)
#define bolt ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define bits(a) __builtin_popcount(a)
#define test ll t;cin>>t;for(ll testi=1;testi<=t;testi++)
#define djokovic  freopen("input00.txt", "r", stdin);freopen("output00.txt", "w", stdout);
ll gcd(ll a, ll b) {    if (b == 0) return a;    return gcd(b, a % b);}
ll lcm(ll a, ll b) {    return (a / gcd(a, b) * b);}
ll expo(ll x, ll y) {
    ll res = 1; x = x % mod; while (y > 0) {
        if (y & 1)res = (1ll * res * x) % mod;
        y = y >> 1; x = (1ll * x * x) % mod;
    } return res;
}
ll ncr(ll n, ll r) { ll res = 1; if (r > n - r)r = n - r; for (ll i = 0; i < r; i++) {  res *= n - i;  res /= i + 1; } return res;}
ll max(ll a, ll b) {return (a > b) ? a : b;}
bool prime(ll n) {ll i; for (i = 2; i <= sqrt(n); i++) {if (n % i == 0)return false;} return true;}
bool sortbysec(const pair<ll, ll> &a, const pair<ll, ll> &b)
{   if (a.second == b.second)
        return a.first < b.first;
    return (a.second < b.second);
}

//https://www.youtube.com/watch?v=WTJSt4wP2ME

ll rr[] = {0, 1, 1, 1, 0, -1, -1, -1};
ll cc[] = {1, 1, 0, -1, -1, -1, 0, 1};
ll n, m, ans[MAXN], mini[MAXN], a[MAXN];
void solve()
{
    cin >> n >> m; ll sum = 0, x;
    forci(0, m)  cin >> x, sum += x;
    cout << max(-1ll, n - sum);
}
signed main()
{
    bolt;
//#ifndef ONLINE_JUDGE
  //  djokovic;
//#endif
    solve();
}




Measured memory_bytes: 3668
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    int h = sc.nextInt();
    int w = sc.nextInt();
    int k = sc.nextInt();
    char[][] c = new char[h][w];
    char[][] cpy = new char[h][w];
    int sum = 0;

    for (int i = 0; i < h; i++) {
      String s = sc.next();
      for (int j = 0; j < w; j++) {
        c[i][j] = s.charAt(j);
        cpy[i][j] = c[i][j];
      }
    }

    for (int bit = 0; bit < Math.pow(2, h); ++bit) {
      for (int bitw = 0; bitw < Math.pow(2, w); ++bitw) {

        int cnt = 0;
        for (int i = 0; i < h; i++) {
          for (int j = 0; j < w; j++) {
            c[i][j] = cpy[i][j];
          }
        }

        for (int i = 0; i < h; ++i) {
          if ((1 & (bit >> i)) == 1) { // i が bit に入るかどうか
            for (int j = 0; j < w; j++) {
              c[i][j] = '*';
            }
          }
        }

        for (int i = 0; i < w; ++i) {
          if ((1 & (bitw >> i)) == 1) { // i が bit に入るかどうか
            for (int j = 0; j < h; j++) {
              c[j][i] = '*';
            }
          }
        }

        for (int i = 0; i < h; i++) {
          for (int j = 0; j < w; j++) {
            if (c[i][j] == '#') {
              cnt++;
            }
          }
        }

        if (cnt == k) {
          sum++;
        }
      }
    }

    System.out.println(sum);

  }
}

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

#define fo(i,s,t) for(int i = s; i <= t; ++ i)
#define fd(i,s,t) for(int i = s; i >= t; -- i)
#define bf(i,s) for(int i = head[s]; i; i = e[i].next)
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define VI vector<int>
#define sf scanf
#define pf printf
#define fp freopen
#define SZ(x) ((int)(x).size())
#ifdef MPS
#define D(x...) printf(x)
#else
#define D(x...)
#endif
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const int inf = 1<<30;
const ll INF = 1ll<<60;
const db Inf = 1e20;
const db eps = 1e-9;

void gmax(int &a,int b){a = (a > b ? a : b);}
void gmin(int &a,int b){a = (a < b ? a : b);}

const int maxn = 1005;

int n, now, x[maxn], y[maxn];
char ans[maxn][32];

void calc(int v)
{
	++ now;
	fo(i,1,n)
	{
		if(abs(x[i]) > abs(y[i]))
		{
			if(x[i] > 0) x[i] -= v, ans[i][now] = 'R';
			else x[i] += v, ans[i][now] = 'L';
		}
		else
		{
			if(y[i] > 0) y[i] -= v, ans[i][now] = 'U';
			else y[i] += v, ans[i][now] = 'D';
		}
	}
}
int main()
{
	sf("%d",&n);
	int S = 0;
	fo(i,1,n) {sf("%d%d",&x[i],&y[i]); if((x[i] + y[i]) % 2 == 0) S = 1;}
	fd(i,30,0) calc((1<<i));  
	if(S) calc(1);
	fo(i,1,n) if(x[i] || y[i]) return 0 * pf("-1\n");
	if(S) pf("32\n1"); else pf("31\n");
	if(S) fo(i,0,30) pf(" %d", (1<<i)); else fo(i,0,30) pf("%d ",(1<<i));
	puts("");
	fo(i,1,n) {fd(j,now,1) pf("%c",ans[i][j]); puts("");}
	return 0;
}

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

public class Main {

	public static void main(String[] args) {
		exec();
	}
	
	private static void exec() {
		
		
		try(Scanner sc = new Scanner(System.in)) {
			int N = sc.nextInt();
			
			int K = sc.nextInt();
			
			int R = sc.nextInt();
			
			int S = sc.nextInt();
			
			int P = sc.nextInt();
			
			String T = sc.next();
			
			Map<String, Integer> score = new HashMap<>();
			
			score.put("r", P);
			score.put("s", R);
			score.put("p", S);
			
			String[] past = new String[K];
			
			Long ans = 0L;
			for(int i=0; i<N; i++) {
				String ene = String.valueOf(T.charAt(i));
				
				if(ene.equals(past[i%K])) {
					past[i%K] = null;
				} else {
					ans += score.get(ene);
					past[i%K] = ene;
				}
			}
			
			System.out.println(ans);
		}
		
	}
}


Measured memory_bytes: 34476
N, K = map(int, input().split())
A = list(map(int, input().split()))

c = [0]*N
cc = [0]
c[0] = 1
i = 0
while True:
  c[A[i]-1] += 1  # 来た場所に1を足す
  cc.append(A[i]-1)
  if c[A[i]-1] > 1:
    memo = A[i]-1
    break
  i = A[i] - 1  # 次の場所
    
used = [i for i in range(N) if c[i] > 0]

pos = [i for i in range(len(cc)) if cc[i] == memo]

res = pos[1] - pos[0]
loop = [i for i in cc[pos[0]:pos[1]]]

if K < N:
  ans = cc[K]+1
else:
  i = (K - (pos[0])) % res
  ans = loop[i]+1
  
print(ans)

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

int main()
{
    int n, k, x, y;
    cin >> n >> k >> x >> y;
    if (n <= k)
    {
        cout << n * x << endl;
    }
    else
    {
        cout << k * x + (n - k) * y << endl;
    }
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

template <typename T1, typename T2>
string print_iterable(T1 begin_iter, T2 end_iter, int counter) {
    bool done_something = false;
    stringstream res;
    res << "[";
    for (; begin_iter != end_iter and counter; ++begin_iter) {
        done_something = true;
        counter--;
        res << *begin_iter << ", ";
    }
    string str = res.str();
    if (done_something) {
        str.pop_back();
        str.pop_back();
    }
    str += "]";
    return str;
}

vector<int> SortIndex(int size, std::function<bool(int, int)> compare) {
    vector<int> ord(size);
    for (int i = 0; i < size; i++) ord[i] = i;
    sort(ord.begin(), ord.end(), compare);
    return ord;
}

template <typename T>
bool MinPlace(T& a, const T& b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template <typename T>
bool MaxPlace(T& a, const T& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template <typename Container>
int SZ(const Container& S) { return S.size(); }

template <typename S, typename T>
ostream& operator <<(ostream& out, const pair<S, T>& p) {
    out << "{" << p.first << ", " << p.second << "}";
    return out;
}

template <typename T>
ostream& operator <<(ostream& out, const vector<T>& v) {
    out << "[";
    for (int i = 0; i < (int)v.size(); i++) {
        out << v[i];
        if (i != (int)v.size()-1) out << ", ";
    }
    out << "]";
    return out;
}

#if DEBUG && !ONLINE_JUDGE
    ifstream input_from_file("input.txt");
    #define cin input_from_file

    #define dbg_var(x) clog << #x  << ": " << x << endl;
    #define dbg_array(x, len) clog << #x << ": " << print_iterable(x, x+len, -1) << endl;
#else
    #define dbg_var(x)
    #define dbg_array(x, len)
#endif

///////////////////////////////////////////////////////////////////////////
//////////////////// DO NOT TOUCH BEFORE THIS LINE ////////////////////////
///////////////////////////////////////////////////////////////////////////

const int MAXN = -1; 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); // Remove in problems with online queries!

    LL Q, H, S, D;
    cin >> Q >> H >> S >> D;
    vector<pair<LL,LL>> vals = {{1, Q}, {2, H}, {4, S}, {8, D}};
    sort(vals.begin(), vals.end(), [](pair<LL,LL> a, pair<LL,LL> b) {
        return b.first * a.second  < a.first*b.second;
    });
    LL N;
    LL res = 0;
    cin >> N;
    N *= 4;
    for (auto val : vals) {
        LL c = N / val.first;
        res += c * val.second;
        N -= c * val.first;
    }
    cout << res << "\n";
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define ld long double
typedef pair<ll,ll> P;
#define boost ios_base::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define  IN (ll)1e5+5
vector<ll> adj[IN];
ll Indegree[IN];
ll Dist[IN];
bool visited[IN];
void DFS(ll start)
{
    if(visited[start])
    return;
    visited[start]=true;
    for(ll i=0;i<adj[start].size();i++){
        Dist[adj[start][i]]=max(Dist[adj[start][i]],Dist[start]+1);
        Indegree[adj[start][i]]--;
        if(Indegree[adj[start][i]]==0)
        DFS(adj[start][i]);
    }
    return;
}
int main()
{
    boost;
    ll n,m,i,a,b;
    cin>>n>>m;
    memset(Dist,0,sizeof(Dist));
    memset(Indegree,0,sizeof(Indegree));
    memset(visited,false,sizeof(visited));
    for(i=0;i<m;i++){
        cin>>a>>b;
        adj[a-1].pb(b-1);
        Indegree[b-1]++;
    }
    for(i=0;i<n;i++){
        if(!visited[i] && Indegree[i]==0){
            DFS(i);
        }
    }
    ll ans=0;
    for(i=0;i<n;i++){
        ans=max(ans,Dist[i]);
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 12032
import qualified Data.Vector.Unboxed as VU

main :: IO ()
main = do
  [n, k] <- map read . words <$> getLine :: IO [Int]
  let
    step :: Char -> [Bool] -> [Bool]
    step 'L' rest = False : rest
    step 'R' rest = True : rest
    step _ _ = []
  ds <- foldr step [] <$> getContents :: IO [Bool]
  let
    s = VU.length . VU.filter id . (VU.zipWith (==) <$> id <*> VU.tail) . VU.fromList $ ds :: Int
  print $ (s + 2 * k) `min` (n - 1)


Measured memory_bytes: 5440
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007

string s;
signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> s;
  int c = 0;
  for (int i=1; i<s.length(); i++) {
    if (s[i] != s[i-1]) c++;
  }
  cout << c << "\n";
  return 0;
}


Measured memory_bytes: 512
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

# 目標700点
D, G = getNM()
query = []
for i in range(D):
    p, c = getNM()
    query.append([i + 1, p, c])

ans_cnt = float('inf')

for bit in range(1 << D):
    sum = 0
    cnt = 0
    for i in range(D):
        if bit & (1 << i):
            sum += query[i][0] * query[i][1] * 100 + query[i][2]
            cnt += query[i][1]

    if sum < G:
        for j in range(D - 1, -1, -1):
            if not bit & (1 << j):
                left = G - sum
                fire = query[j][0] * 100
                opt = min(query[j][1], (left + fire - 1) // fire)
                sum += opt * query[j][0] * 100
                cnt += opt
                break

    if sum >= G:
        ans_cnt = min(ans_cnt, cnt)

print(ans_cnt)

Measured memory_bytes: 63468
N=int(input())
U=list(map(int,input().split()))
D=list(map(int,input().split()))
SU=[U[0]]
for i in range(1,N):
    SU.append(SU[-1]+U[i])
SD=[D[N-1]]
for i in range(N-2,-1,-1):
    SD.append(SD[-1]+D[i])
SD.reverse()

S=[]
for i in range(N):
    S.append(SU[i]+SD[i])

print(max(S))

Measured memory_bytes: 38256
#include <stdio.h>

#define SIZE 2000000

int main() {
  int A[SIZE];
  int H=0;
  int i, key, l, largest, p, tmp;
  char com[20];
  do {
    scanf("%s", com);
    if (com[0] == 'i') {
      scanf("%d", &key);
      A[++H] = key;
      for (i=H; i>1 && A[i/2]<A[i];i/=2) {
        tmp = A[i/2];
        A[i/2] = A[i];
        A[i] = tmp;
      }

    } else if (com[1]=='x') { // extract
      printf("%d\n", A[1]);
      A[1] = A[H];
      i = 1;
      while (1) {
        l = i*2;
        // 左の子、自分、右の子で値が最大のノードを選ぶ
        largest = i;
        if (l < H && A[l] > A[i])        largest = l;
        if (l+1 < H && A[l+1] > A[largest])  largest = l+1;
        if (largest == i) break;  // i の子の方が値が大きい場合
        tmp = A[i];
        A[i] = A[largest];
        A[largest] = tmp;
        i = largest;
      }
      H--;
    }
  } while (com[2]!='d');
  return 0;
}


Measured memory_bytes: 5644
#include <time.h>

#include <stdlib.h>
#include <cstdint>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <limits>
#include <cstdint>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <limits>

using namespace std;

int main() {

	string s;
	cin>>s;
	if(s[s.length()-1]=='1'){
		cout<<-1<<endl;
	}else if(s[0]=='0'){
		cout<<-1<<endl;
	}else{
		string s_copy=s.substr(0,s.length()-1);
		reverse(s.begin(),s.end()-1);
		if(s.substr(0,s.length()-1)==s_copy){
			int last=1;
			for(string::size_type i=2;i<=(s.length()/2);i++){
				if(s[i-1]=='1'){
					for(string::size_type k=last;k<i;k++){
						cout<<k<<" "<<i<<endl;
					}
					last=i;
				}
			}
			for(string::size_type k=last;k<s.length();k++){
				cout<<k<<" "<<s.length()<<endl;
			}
		}else{
			cout<<-1<<endl;
		}

	}



	return 0;

}


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

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>
#include<iomanip>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, double> pid;
typedef pair<double, int> pdi;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

const int MAX = 510000;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

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

	COMinit();

	int H, W, A, B;
	cin >> H >> W >> A >> B;
	int ans = COM(H - 1 + W - 1, H - 1);
	rep(i, H - A, H)
	{
		ans = (ans - (COM(i + B - 1, i)*COM(H - i - 1 + W - B - 1, H - i - 1)) % MOD + MOD) % MOD;
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 12160
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <deque>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

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

    int n = h * w;
    int t = n - 1;

    char c[50 * 50 + 1];
    for (int i = 0; i < h; i++) {
        cin >> c + w * i;
    }

    int r = 0;
    for (int i = 0; i < n; i++) {
        r += c[i] == '.';
    }

    vector<int> v(n, -1);
    v[0] = 0;

    deque<int> q;
    q.push_back(0);

    while (!q.empty()) {
        int i = q.front(); q.pop_front();
        for (int d : { -w, -1, 1, w }) {
            int j = i + d;
            if (j < 0 || j >= n || (abs(d) <= 1 && j / w != i / w)) continue;
            if (c[j] == '.' && v[j] < 0) {
                v[j] = v[i] + 1;
                q.push_back(j);
            }
        }
    }

    if (v[t] < 0) {
        cout << -1 << endl;
    } else {
        cout << r - (v[t] + 1) << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <deque>
#include <algorithm>
#include <iomanip>
#include <functional>
#include <numeric>
#include <sstream>

#define REP(i, n) for(int i = 0;i < (n); i++)
#define REP2(i, x, n) for(int i = (x); i < (n); i++)
#define RREP(i, n) for (int i = (n) - 1;i >= 0; i--)

#define ALL(a) (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define DESCSORT(c) sort(c.begin(), c.end(), greater<int>())

#define LL long long int
#define LD long double

#define PI 3.14159265358979

using namespace std;

//================================================

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

	int A, B, N, ans;
	while (cin >> A >> B >> N) {
		ans = 0;
		REP(i, N) {
			A *= 10;
			ans += (A / B) % 10;
			A %= B;
		}
		cout << ans << "\n";
	}
	return 0;
}

Measured memory_bytes: 3128
s = [list(map(int,input().split())) for _ in range(3)]
a1_max = max(s[0])

for i in range(0,a1_max+1):
    a1 = i
    b1 = s[0][0] - a1
    b2 = s[0][1] - a1
    b3 = s[0][2] - a1
    a2 = s[1][0] - b1
    a3 = s[2][0] - b1
    if b1 >= 0 and b2 >= 0 and b3 >= 0 and a2 >= 0 and a3 >= 0:
        if s[1][1] == a2 + b2 and s[1][2] == a2 + b3 and s[2][1] == a3 + b2 and s[2][2] == a3 + b3:
            print("Yes")
            exit()
        
print("No")
 
        

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vb = vector<bool>;

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

int v, e;
vvi g(v);
vi prenum, parent, lowest;
vb visited;

void dfs(int c, int prev, int timer = 1) {
  prenum[c] = lowest[c] = timer++; 
  visited[c] = true;

  for (auto nx: g[c]) {
    if (!visited[nx]) {
      parent[nx] = c;
      dfs(nx, c, timer);
      lowest[c] = min(lowest[c], lowest[nx]);
    } else if (nx != prev) {
      lowest[c] = min(lowest[c], prenum[nx]);
    }
  }
}

void art_point() {
  set<int> ap;
  int np = 0;
  for (int i = 1; i < v; i++) {
    int p = parent[i];
    if (p == 0) np++;
    else if (prenum[p] <= lowest[i]) ap.insert(p);
  }

  if (np > 1) ap.insert(0);
  for (auto it: ap) {
    cout << it << endl;
  }
}

int main() {
  cin >> v >> e;

  g.resize(v);
  prenum.resize(v);
  parent.resize(v);
  lowest.resize(v);
  visited.resize(v);
  
  int s, t;
  rep(i, e) {
    cin >> s >> t;
    g[s].push_back(t);
    g[t].push_back(s);
  }
  
  dfs(0, -1);
  art_point();
}



Measured memory_bytes: 4568
#include <iostream>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <functional>
#include <string>
#include <cstring>
#include <sstream>
#include <deque>
#define fir first
#define sec second
using namespace std;

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

const int inf1=1e9+9;
const ll inf2=8e18+9;
const ll mol=1e9+7;
const int maxn=2e6+9;
const ll maxx=1e5+9;

int n,len;
string s;
ll fac[maxn]={1};

inline ll qpow(ll x,ll t)
{
    ll res=1;
    while(t)
    {
        if(t&1) res=(res*x)%mol;
        t>>=1; x=(x*x)%mol;
    }
    return res;
}
void init()
{
    cin>>n>>s; len=s.size();
    for(int i=1;i<maxn;i++)
        fac[i]=fac[i-1]*i%mol;
}
inline ll inv(ll t)
{
    return qpow(t,mol-2);
}
inline ll c(ll n,ll r)
{
    if(!n||!r) return 1;
    return fac[n]*inv(fac[r])%mol*inv(fac[n-r])%mol;
}
int main()
{
    init();
    ll ans=0;
    for(int i=len;i<=len+n;i++)
    {
        ll tmp=c(i-1,len-1);
        tmp=(tmp*qpow(25,i-len))%mol;
        tmp=(tmp*qpow(26,len+n-i))%mol;
        ans=(ans+tmp)%mol;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 19396
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n,a[200010],b[200010],maxn=-1,pos,p[200010];
int main()
{
	scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+1+n);
	for (int i=1;i<n;i++)
	{
		if (a[i]>a[n]/2) a[i]=a[n]-a[i],p[i]=1;
		if (a[i]>maxn) pos=i,maxn=a[i];
	}
	if (p[pos]) a[pos]=a[n]-a[pos];
	printf("%d %d",a[n],a[pos]);
}

Measured memory_bytes: 896
use std::str::FromStr;
use std::fmt::Debug;
use std::cmp;
#[allow(dead_code)]
fn read_as_vec<T>() -> Vec<T>
where T: FromStr, <T as FromStr>::Err : Debug{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().split_whitespace().map(|c| T::from_str(c).unwrap()).collect()

}

#[allow(dead_code)]
fn read_as_string() -> String{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

fn main(){
    let line = read_as_vec::<usize>();
    let (n, m) = (line[0], line[1]);
    let mut reds = vec![0;n];
    reds[0] = 1;
    let mut balls = vec![1;n];

    for _ in 0..m{
        let line = read_as_vec::<usize>();
        let (x, y) = (line[0]-1, line[1]-1);

        if balls[x] == 1 && reds[x] > 0{
            reds[x] = 0;
            reds[y] = 1;
            balls[x] -= 1;
            balls[y] += 1;
        }else if reds[x] == 0{
            balls[x] -= 1;
            balls[y] += 1;
        }else{
            balls[x] -= 1;
            balls[y] += 1;
            reds[y] += 1;
        }
    }

    println!("{}", reds.iter().filter(|x| **x > 0).count());
}


Measured memory_bytes: 4352
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1000000000LL;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
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; }


int main() {
    int w, a, b;
    cin >> w >> a >> b;

    int res = max(0, max(a,b)-(w+min(a,b)));
    cout << res << ln;
}




Measured memory_bytes: 256
h,w = map(int,input().split())
c = [list(map(int,input().split())) for _ in range(10)]

for i in range(10):
    for j in range(10):
        for k in range(10):
            c[j][k] = min(c[j][k], c[j][i] + c[i][k])

ans = 0
for i in range(h):
    a = list(map(int,input().split()))
    for j in range(w):
        if a[j] != -1:
            ans += c[a[j]][1]
print(ans)

Measured memory_bytes: 40556
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define RFOR(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define rep(i,n) FOR(i,0,(n))
#define REPS(i,n) FOR(i,1,(n)+1)
#define RREP(i,n) RFOR(i,0,(n))
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define debug(x) cout << #x << " = " << (x) << endl;
#define SORT(x) sort(ALL(x))
#define RSORT(x) sort(RALL(x))
#define SUM(x) accumulate(ALL(x),0)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
const ll mod = 1e9+7;
const int INF = (1<<30)-1;
const ll INFLL = (1LL<<62)-1;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//cout << fixed << setprecision(10);

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

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

vector<pair<ll,int>> factorize(ll n) {
  vector<pair<ll,int>> res;
  for (ll i = 2; i*i < n; ++i) {
    if (n%i) continue;
    res.emplace_back(i,0);
    while (n%i == 0) {
      n /= i;
      res.back().se++;
    }
  }
  if (n != 1) res.emplace_back(n,1);
  return res;
}

int main () {
  ll a, b;
  cin >> a >> b;

  ll g = gcd(a,b);

  vector<pair<ll,int>> f;
  f = factorize(g);

  cout << f.size() + 1 << endl;
}

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

int main()
{
	int n, m, x;
	cin >> n >> m >> x;
	int a[200];
	int L = 0;
	int R = 0;
	for (int i = 0; i < m; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < m; i++){
		if (a[i] > x)++R;
		else ++L;
	}
	cout << min(L, R);
}

Measured memory_bytes: 256
#include<iostream>
#include <iomanip>
using namespace std;
int main()
{
	int a,b,d,r;
	double f;
	while(cin>>a>>b)
	{
		d=a/b;
		r=a%b;
		f=double(a)/double(b);
		cout<<d<<" "<<r<<" ";
		cout<<setiosflags(ios::fixed)<<setprecision(5);
		cout<<f<<endl;
		}
}

Measured memory_bytes: 3276
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = uint32_t;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;

int main() {
    string s, t;
    cin >> s >> t;
    using P = array<int, 26>;
    P cnt1{}, cnt2{};
    int ans = 0;
    for (int i = 1; i <= min(s.size(), t.size()); ++i) {
        cnt1[s[i-1]-'a']++;
        cnt2[t[i-1]-'a']++;
        auto cnt = cnt1, cntt = cnt2;
        set<P> S;
        S.emplace(cnt);
        for (int j = 0; j+i < s.size(); ++j) {
            cnt[s[j]-'a']--;
            cnt[s[j+i]-'a']++;
            S.emplace(cnt);
        }
        if(S.count(cntt)) {
            ans = max(ans, i);
            continue;
        }
        for (int j = 0; j+i < t.size(); ++j) {
            cntt[t[j]-'a']--;
            cntt[t[j+i]-'a']++;
            if(S.count(cntt)){
                ans = max(ans,i);
                continue;
            }
        }
    }
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 3644
a=split(readline(),"")
b=a[length(a)]
b=parse(Int,b)
if b == 2 || b==4 || b==5 || b==7 || b==9
    println("hon")
elseif b==0 || b==1 || b==6 || b==8
    println("pon")
else
    println("bon")
end

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

using namespace std;

#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define i_i pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< i_i >
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; cin >> x;
#define int2(x, y) Int(x); Int(y);
#define int3(x, y, z) Int(x); int2(y, z);
#define fir first
#define sec second
#define ffir first.first
#define fsec first.second
#define sfir second.first
#define ssec second.second
#define Decimal fixed << setprecision(10)

//int dxy[5] = {0, 1, 0, -1, 0};
// cmd

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

    int2(n, m);
    vector<int> data(n);
    int pos = 0;
    for (int i = 0; i < n; i++) {
        cin >> data[i];
        if (data[i] == 1) pos = i;
    }

    int left = pos, right = n - pos-1;
    int ans = left / (m-1) + right / (m-1);
    //cout << left << " " << pos << " " << right << endl;
    if (left % (m-1) + right % (m-1) == 0) ;
    else if (left % (m-1) + right % (m-1) <= m-1) ans++;
    else ans += 2;
    
    cout << ans << endl;


    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define rep(i,N) for(int i=0;i<(N);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9;
typedef long long ll;
typedef pair<ll,int> P;
typedef set<int> S;

int main(){
    vector<int> ans;
    while(1){
        int n,m;
        cin>>n>>m;
        if(n==0 && m==0){
            for(int i = 0;i < ans.size(); i++){
                cout<<ans[i]<<endl;
            }
            return 0;
        }
        vector<int> h(n,0),w(m,0);
        rep(i,n) cin>>h[i];
        rep(i,m) cin>>w[i];
        vector<int> h2;
        int sum=0;
        int now=0;
        for(int i=0;i<n;i++){
            sum=0;
            for(int j=i;j<n;j++){
                sum+=h[j];
                h2.push_back(sum);
            }
        }
        sort(h2.begin(),h2.end());
        //cout<<"h2"<<endl;
        //rep(i,h2.size()) cout<<h2[i]<<endl;
        now=0;
        for(int i=0;i<m;i++){
            sum=0;
            for(int j=i;j<m;j++){
                sum+=w[j]; //幅
                //cout<<"sum"<<endl;
                //cout<<sum<<endl;
                now+=upper_bound(h2.begin(),h2.end(),sum)-lower_bound(h2.begin(),h2.end(),sum);
            }
        }
        ans.push_back(now);
    }
}


Measured memory_bytes: 15540
using System.Text;
using System.Collections.Generic;
using static System.Math;
using System;

public class Hello
{
    public static void Main()
    {
        var d = new Dictionary<string, int>();
        var n = int.Parse(Console.ReadLine().Trim());
        var dmax = 0;
        for (int i = 0; i < n; i++)
        {
            var s = Console.ReadLine().Trim();
            if (d.ContainsKey(s)) d[s]++;
            else d[s] = 1;
            dmax = Max(dmax, d[s]);
        }
        var ans = new List<string>();
        foreach (var x in d)
            if (dmax == x.Value) ans.Add(x.Key);
        var ans2 = ans.ToArray();
        StringComparer cmp = StringComparer.OrdinalIgnoreCase;
        Array.Sort(ans2, cmp);
        var sb = new StringBuilder();
        foreach (var x in ans2) sb.Append(x + "\n");
        Console.Write(sb);
    }
}


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



ll modpower(ll a, ll r, ll mod){ //a^r
    ll x = 1;
    a %= mod;
    while (r > 0) {
        if (r & 1) x = x * a % mod;
        r >>= 1;
        a = a * a % mod;
    }
    return x;
}

ll modinv(ll a, ll mod){
    return modpower(a, mod-2, mod);
}

vector<ll> fact;
vector<ll> invfact;

void set_fact(ll n, ll mod){
    fact.resize(n+1, 1);
    invfact.resize(n+1, 1);
    for (ll i = 2; i <= n; i++) {
        fact[i] = fact[i-1] * i % mod;
    }
    invfact[n] = modinv(fact[n], mod);
    for (ll i = n-1; i >= 2; i--) {
        invfact[i] = invfact[i+1] * (i+1) % mod;
    }
    return;
}

ll comb(ll n, ll k, ll mod) {
    if (k > n || k < 0) return 0;
    if (k == n || k == 0) return 1;
    return fact[n] * invfact[n-k] % mod * invfact[k] % mod;
}


int main() {
    ll N;
    cin >> N;
    ll mod = 998244353;
    ll all = modpower(3, N, mod);
    ll ex = 0;
    set_fact(N+2, mod);
    
    vector<ll> pow2(N+1, 1);
    for (ll i = 1; i <= N; i++) pow2[i] = pow2[i-1]*2%mod;
    for (ll i = N/2+1; i <= N; i++) {
        ex += 2LL * comb(N, i, mod) * pow2[N-i] % mod;
        ex %= mod;
    }
    cout << (all+mod-ex)%mod << endl;
    return 0;
}

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

int main() {
  int N,K,sum,x,y;
  sum = 1;
  cin >> N >> K ;
  for(int i = 0 ; i<N; i++){
    x = sum + K;
    y = sum * 2;
    
    if(x>y){
     sum = y; 
    }else{
      sum = x;
    }
    
  } 
  
  cout << sum << endl;
    
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
const ll inf = (1 << 30) - 1;
const ll infll = (1LL << 61) - 1;

int N;

int main()
{
    cin >> N;
    vector<int> p(N), A(N), B(N);
    for (int i = 0; i < N; i++)
    {
        cin >> p[i];
        p[i]--;
        B[p[i]] += i + 1;
        A[i] = 30000 * (i + 1);
        B[i] += 30000 * (N - i - 1);
    }
    for (int i = 0; i < N; i++)
        cout << A[i] << (i == N - 1 ? '\n' : ' ');
    for (int i = 0; i < N; i++)
        cout << B[i] << (i == N - 1 ? '\n' : ' ');
}

Measured memory_bytes: 896
/*
	Powered by C++11.
	Author : Alex_Wei.
*/

#include <bits/stdc++.h>
using namespace std;

//#pragma GCC optimize(3)
//#define int long long

#define ll long long
#define pii pair <int,int>
#define fi first
#define se second
#define pb emplace_back
#define all(x) x.begin(),x.end()
#define sor(x) sort(all(x))
#define rev(x) reverse(all(x))
#define mem(x,v) memset(x,v,sizeof(x))

// Templates start.

namespace IO{
	char buf[1<<21],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
	#ifdef __WIN64
		#define gc getchar()
	#else
		#define gc (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
	#endif
	#define pc(x) (*O++=x)
	#define flush() fwrite(obuf,O-obuf,1,stdout)

	inline int read(){
		int x=0,sign=0; char s=getchar();
		while(!isdigit(s))sign|=s=='-',s=getchar();
		while(isdigit(s))x=(x<<1)+(x<<3)+(s-'0'),s=getchar();
		return sign?-x:x;
	}
	void print(int x) {if(x>9)print(x/10); pc(x%10+'0');}
}

namespace math{
	const int mod=998244353;
	const int maxn=1e6+5;

	ll ksm(ll a,ll b){ll s=1,m=a; while(b){if(b&1)s=s*m%mod; m=m*m%mod,b>>=1;} return s;}
	ll inv(ll x){return ksm(x,mod-2);}

	ll fc[maxn],ifc[maxn];
	void init_m(int n){
		fc[0]=1; for(int i=1;i<=n;i++)fc[i]=fc[i-1]*i%mod;
		ifc[n]=inv(fc[n]); for(int i=n-1;i>=0;i--)ifc[i]=ifc[i+1]*(i+1)%mod;
	}
	ll C(ll n,ll m){return fc[n]*ifc[m]%mod*ifc[n-m]%mod;}
}

// Templates end. Please give me more points.

using namespace IO;
//using namespace math;

int n,k,d[150];

int main(){
	cin>>n>>k;
	for(int i=1;i<=k;i++){
		int x; cin>>x;
		for(int j=1;j<=x;j++){
			int v=read();
			d[v]=1;
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)ans+=!d[i];
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using ull = unsigned long long;
//#define int ll
using vb = vector<bool>; using vvb = vector<vb>;
using vi = vector<int>; using vvi = vector<vi>;
using vl = vector<ll>; using vvl = vector<vl>;
template<class T> using V = vector<T>;
template<class T> using VV = vector<V<T>>;
#define fi first
#define se second
#define maxs(x,y) (x=max(x,y))
#define mins(x,y) (x=min(x,y))
using pii = pair<int,int>; using pll = pair<ll,ll>;
#define FOR(i,a,b) for(ll i = (a); i < (ll)(b); ++i)
#define REP(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(ll i = (ll)(b)-1;i >= a;--i)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define eb(val) emplace_back(val)
const double PI = acos(-1), EPS = 1e-10;
const ll MOD = 1e9+7;
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vi w(n);
  REP(i,n) cin >> w[i];
  //sort(ALL(w));
  vi s(n+1,0);
  REP(i,n) s[i+1] = s[i]+w[i];
  int m = INT_MAX;
  REP(i,n){
    if(m>abs(s[n]-s[i]-s[i])){
      m = abs(s[n]-s[i]*2);
    }
  }
  cout << m << endl;
}


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

vector<int> to[200005];
vector<int> ans;

void dfs(int v, int p=-1){
    for(int u: to[v]){
        if(u == p) continue;
        ans[u] += ans[v];
        dfs(u,v);
    }
}
int main(){
    int n, q;
    cin >> n >> q;
    rep(i,n-1){
        int a, b;
        cin >> a >> b;
        a--; b--;
        to[a].push_back(b);
        to[b].push_back(a);
    }
    ans.resize(n);
    rep(i,q){
        int p, x;
        cin >> p >> x;
        p--;
        ans[p] += x;
    }

    dfs(0);

    rep(i, n){
        cout << ans[i] << endl;
    }

    return 0;
}

Measured memory_bytes: 23424
def check_current_posi(s_i_list, h, w):
  _height = len(s_i_list)
  _width = len(s_i_list[0])
  if h == -1 or w == -1 or h >= _height or w >= _width:
    return False

  else:
    if s_i_list[h][w] == "#":
      # bomb
      return True

    else:
      # not bomb
      return False

# hとwは0から
def check_around_bomb_num(s_i_list, h, w):

  check_posi_h = h - 1
  check_posi_w = w - 1

  bomb_counter = 0

  for i in range(3):

    for j in range(3):

      if check_current_posi(s_i_list, check_posi_h, check_posi_w):
        bomb_counter += 1

      check_posi_w += 1

    check_posi_h += 1
    check_posi_w = w - 1
  
  return bomb_counter
      

# _input = [6, 6]
_input = list(map(int, input().split(" ")))

height = _input[0]
width = _input[1]

s_i_list = []

for i in range(height):
  _input_row = list(input())
  s_i_list.append(_input_row)

# s_i_list = [['#', '#', '#', '#', '#', '.'], ['#', '.', '#', '.', '#', '#'], ['#', '#', '#', '#', '.', '#'], ['.', '#', '.', '.', '#', '.'], ['#', '.', '#', '#', '.', '.'], ['#', '.', '#', '.', '.', '.']]

for row in range(height):
  for column in range(width):
    if s_i_list[row][column] == "#":
      continue

    s_i_list[row][column] = check_around_bomb_num(s_i_list, row, column)

for row in s_i_list:
  output_row = "".join(list(map(str,row)))
  print(output_row)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
int main(void)
{
  long long int n, a, b;
  std::cin >> n >> a >> b;
  if(n >= 2 && b >= a)
    std::cout << (b - a) * (n - 2) + 1 << std::endl;
  else if(b < a)
    std::cout << 0 << std::endl;
  else
    std::cout << (b == a) * 1 << std::endl;
  return 0;
}

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

class Program
{
    static void Main(string[] args)
    {
        string []input = Console.ReadLine().Split(' ');
        int N = int.Parse(input[0]);
        int K = int.Parse(input[1]);
        char[] S = Console.ReadLine().ToCharArray();
        if (S[K-1] == 'A') { S[K-1] = 'a'; }
        if (S[K-1] == 'B') { S[K-1] = 'b'; }
        if (S[K-1] == 'C') { S[K-1] = 'c'; }
        string ans = "";
        for (int i = 0; i < N; i++)
        {
            ans += S[i];
        }
        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 11092
from sys import stdin

def main():
    N = int(input())
    XU = [input().split() for _ in [0] * N]

    ans = 0
    for x, u in XU:
        x = float(x)
        if u == 'BTC':
            ans += x * 380000
        else:
            ans += x
    print(ans)

input = lambda: stdin.readline().rstrip()
main()


Measured memory_bytes: 2940
N,K=(int(x) for x in input().split())
P=list(map(int, input().split()))
s=sum(P[0:K])
ans=[s]

for i in range(K,N):
    s=s+P[i]-P[i-K]
    ans.append(s)

S=max(ans)
print((S+K)/2)

Measured memory_bytes: 24556