akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<(n);i++)
int main(){
	ll n,m,x,y; cin>>n>>m;
	ll fs[n+1]={0};
	ll te[n+1]={0};
	bool a=0;
	for(ll i=0;i<m;i++){
		cin>>x>>y;
		if(x==1) fs[y]=1;
		if(y==n) te[x]=1;
		if(fs[x] and te[x]) a=1;
		if(fs[y] and te[y]) a=1;
	}
	if(a) cout<<"POSSIBLE";
	else cout<<"IMPOSSIBLE";
}


Measured memory_bytes: 6652
#include <iostream>
#include <map>


using namespace std;


typedef long long ll;
typedef unsigned long long ull;

const int MOD = 1000000007;
map<ll, ll> CACHE;


ll solve( ull x ) {
    if ( x <= 1 ) { return x; }
    if ( CACHE[ x ] != 0 ) { return CACHE[ x ]; }

    ull res = 2 * solve( x >> 1 ) + solve( ( x >> 1 ) + ( ( x & 1 ) ? 1 : -1 ) );

    return CACHE[ x ] = res % MOD;
}


int main() {
    ull N;
    cin >> N;

    cout << solve( N + 1 ) << endl;
    
    return 0;
}


Measured memory_bytes: 256
N, M, X = map(int, input().split())
a = []
for i in range(N):
    a.append(list(map(int, input().split())))

d = []

for i in range(1 << N):
    s = [0] * M
    c = 0
    for j in range(N):
        if (i >> j) & 1:
            # print(j, "entry")
            for k in range(M):
                s[k] += a[j][k+1]
            c += a[j][0]

    # print(s, c, d)

    b = True
    for ii in s:
        if ii < X:
            b = False
    if b:
        d.append(c)

if len(d) == 0:
    print("-1")
else:
    print(min(d))




Measured memory_bytes: 9220
#include <cstdio>

const int MAXN=311, MAXM=311;

int N, M;
int A[MAXN][MAXM];
bool Vis[MAXM];
int Cnt[MAXM];

int main(){
	
	scanf("%d%d", &N, &M);
	
	for(int i=1;i<=M;++i)	Vis[i]=true;
	
	for(int i=1;i<=N;++i)	for(int j=1;j<=M;++j)	scanf("%d", &A[i][j]);
	
	int Ans=N;
	
	for(int i=1, x;i<=M;++i){
		for(int i=1;i<=M;++i)	Cnt[i]=0;
		for(int i=1;i<=N;++i){
			for(int j=1;j<=M;++j){
				if(Vis[A[i][j]]){
					++Cnt[A[i][j]];
					break;
				}
			}
		}
		x=0;
		for(int i=1;i<=M;++i){
			if(Cnt[i]>Cnt[x])	x=i;
		}
		if(Ans>Cnt[x])	Ans=Cnt[x];
		Vis[x]=false;
	}
	
	printf("%d\n", Ans);
	
	return 0;
}

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

using namespace std;

int main() {
	int n; cin >> n;
	string s; cin >> s;
	
	for (int i = 0; i < s.size(); i++) {
		s[i] += n;
		if (s[i] > 90) s[i] -= 26;
	}
	
	cout << s;
	
	return 0;
}

Measured memory_bytes: 256
def f(k):
    if k==1:return d
    if k==0:return 0
    if k in m:return m[k]
    s=min(k*d,f(k//2)+a+k%2*d,f(-(-k//2))+a+-k%2*d,f(k//3)+b+k%3*d,f(-(-k//3))+b+-k%3*d,f(k//5)+c+k%5*d,f(-(-k//5))+c+-k%5*d)
    m[k]=s
    return s
for _ in range(int(input())):
    m={}
    n,a,b,c,d=map(int,input().split())
    print(f(n))

Measured memory_bytes: 10888
makeString :: Int -> IO ()
makeString counter = do
    line <- getLine
    let num = read line
        newCounter = counter + 1
    if num /= 0
        then do 
            putStrLn $ "Case " ++ show counter ++ ": " ++ show num
            makeString newCounter
        else return ()
         
main = makeString 1



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

int main() {
  vector<int> pri(3);
  rep(i, 3) cin >> pri.at(i);
  sort(pri.begin(), pri.end());
  cout << pri.at(0) + pri.at(1) << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <bitset>
#include <algorithm>

int main(int argc, char *argv[]) {
    std::string s;
    std::cin >> s;
    std::reverse(s.begin(), s.end());
    const auto len = s.length();
    int64_t result{};
    for (size_t pattern = 0; pattern < (1 << len - 1); pattern++) {
        int64_t digit = 1;
        std::bitset<32> bits(pattern);
        for (size_t i = 0; i < len; i++) {
            result += digit * (s[i] - '0');
            digit = (bits[i]) ? 1 : digit * 10;
        }
    }
    std::cout << result << std::endl;
    return 0;
}

Measured memory_bytes: 3576
#include <iostream>

const int N = 200000 + 7, T = N * 100;

int n;
int a[N], b[N], d[N];

int rt[N][2];
int kid[T][2], dat[T], ct;
void insert(int& p, int lp, int l, int r, int x, int y) {
	dat[p = ++ct] = dat[lp];
	kid[p][0] = kid[lp][0];
	kid[p][1] = kid[lp][1];
	if (l == r)
		dat[p] = std::max(dat[p], y);
	else {
		int m = l + r >> 1;
		if (x <= m) insert(kid[p][0], kid[lp][0], l, m, x, y);
		else insert(kid[p][1], kid[lp][1], m + 1, r, x, y);
		dat[p] = std::max(dat[kid[p][0]], dat[kid[p][1]]);
	}
}
int get(int p, int l, int r, int x, int y) {
	if (x > y) return -(1 << 28);
	if (x <= l && r <= y) return dat[p];
	int m = l + r >> 1, t = -(1 << 28);
	if (x <= m) t = std::max(t, get(kid[p][0], l, m, x, y));
	if (y > m) t = std::max(t, get(kid[p][1], m + 1, r, x, y));
	return t;
}

int f0, f1, g0, g1;
int ok(int m) {
	int f;
	f = f1 - f0 + d[m + 1];
	if (0 <= f && f <= get(rt[m + 1][f & 1], 1, n, g0 + 1, n)) return 1;
	f = f0 - f1 + d[m + 1];
	if (0 <= f && f <= get(rt[m + 1][f & 1], 1, n, g1 + 1, n)) return 1;
	return 0;
}

int s[N];

int main() {
//	freopen("code.in", "r", stdin);
//	freopen("code.out", "w", stdout);

	scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
		scanf("%d", a + i), b[i] = std::max(a[i], b[i - 1]);
	for (int i = n; i; --i) {
		d[i] = d[i + 1] + (a[i] == b[i]);
		int f0 = std::max(0, get(rt[i + 1][0], 1, n, a[i] + 1, n)) + 1 + (a[i] == b[i]);
		int f1 = std::max(0, get(rt[i + 1][1], 1, n, a[i] + 1, n)) + 1 + (a[i] == b[i]);
		rt[i][0] = rt[i + 1][0], rt[i][1] = rt[i + 1][1];
		insert(rt[i][f0 & 1], rt[i][f0 & 1], 1, n, a[i], f0);
		insert(rt[i][f1 & 1], rt[i][f1 & 1], 1, n, a[i], f1);
	}

	f0 = 1, g0 = a[1];
	for (int i = 2; i <= n; ++i) {
		int lg0 = g0;
		if (a[i] > g0) g0 = a[i], ++f0;
		if (s[i] = !ok(i)) {
			if (a[i] > lg0) g0 = lg0, --f0;
			if (a[i] > g1) g1 = a[i], ++f1;
		}
	}
	if (f0 != f1)
		printf("-1");
	else
		for (int i = 1; i <= n; ++i) printf("%d", s[i]);
	return 0;
}


Measured memory_bytes: 96096
S = int(input())

X = 0
Y = 0

MAX = 10**9

x1, y1, x2, y2, x3, y3 = (0, 0, MAX, 1, 0, 0)

# S = x2 * y3 - x3 * y2
# S = 10**9 * y3 - x3 * 1

x3 = (MAX - S) % MAX
y3 = (S + x3) // MAX

print("{} {} {} {} {} {}".format(x1, y1, x2, y2, x3, y3))


Measured memory_bytes: 38256
#include <iostream>
#include<string>
using namespace std;
int main(void){
    // Your code here!
    int i,cnt=0;
    string str1,str2;
    cin >>str1;
    cin >>str2;
    for(i=0;i<3;i++){
    if(str1[i] ==  str2[i]){
        cnt++;
    }

    }
    cout << cnt;
}


Measured memory_bytes: 256
# coding: utf-8

# In[20]:

import sys
#input = sys.stdin.readline
S = input()


# In[21]:

if len(S)%2==0:
    a = "01"*(len(S)//2)
    b = "10"*(len(S)//2)
else:
    a = "01"*(len(S)//2)+"0"
    b = "10"*(len(S)//2)+"1"


# In[22]:

ac = 0
bc = 0
for i in range(len(S)):
    if S[i] != a[i]:
        ac += 1
    if S[i] != b[i]:
        bc += 1
print(min(ac, bc))


# In[ ]:





Measured memory_bytes: 3316
L = input()
l = len(L)
dp = [ [0]*2 for _ in range(l+1)]
dp[0][1] = 1
Q = 10**9+7
for i in range(l):
    if L[i] == "1":
        dp[i+1][1] = dp[i][1]*2%Q
        dp[i+1][0] = (dp[i][0]*3 + dp[i][1])%Q
    else:
        dp[i+1][1] = dp[i][1]
        dp[i+1][0] = dp[i][0]*3%Q
print((dp[l][0]+dp[l][1])%Q)

Measured memory_bytes: 19700
#include <bits/stdc++.h>
using namespace std;
int main(){
	int x,i=1,j=1,ans=0;
    cin>>x;
    while(1){
    	while(1){
        	if(x*j==360*i) {
              cout<<ans+1;
              return 0;
            }
            else if(x*j>360*i) i++;
            j++;
            ans++;
        }
    }
}

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


int main() {
  cin.tie(nullptr); ios_base::sync_with_stdio(false);
  int n; cin >> n;
  V<> a(n); for (int i = 0; i < n; ++i) cin >> a[i];
  VV<> g(n);
  for (int i = 0; i < n - 1; ++i) {
    int u, v; cin >> u >> v, --u, --v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  V<> sz(n, 1);
  constexpr lint inf = 1e18;
  V< VV<lint> > dp; assign(dp, n, 2, n, inf);
  auto dfs = [&](const auto& dfs, int v, int p) -> void {
    dp[v][a[v] < 0][0] = a[v];
    for (int w : g[v]) if (w != p) {
      dfs(dfs, w, v);
      VV<lint> dpv; assign(dpv, 2, n, inf);
      for (int f = 0; f < 2; ++f) for (int x = 0; x < sz[v]; ++x) {
        for (int g = 0; g < 2; ++g) for (int y = 0; y < sz[w]; ++y) {
          dpv[f or g][x + y] = min(dpv[f or g][x + y], dp[v][f][x] + dp[w][g][y]);
          if (dp[w][g][y] < (g ? 0 : inf)) dpv[f][x + y + 1] = min(dpv[f][x + y + 1], dp[v][f][x]);
        }
      }
      swap(dp[v], dpv);
      sz[v] += sz[w];
    }
  };
  dfs(dfs, 0, -1);
  for (int x = 0; x < n; ++x) {
    if (dp[0][0][x] != inf or dp[0][1][x] < 0) {
      return cout << x << '\n', 0;
    }
  }
}

Measured memory_bytes: 392320
import java.util.*;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		long x = sc.nextLong();
		long[] a = new long[N];
		long[] ans = new long[N-1];
		for( int i=0; i<N; i++ ){
			a[i]=sc.nextLong();
		}
		long b = 0;
		for( int i=0; i<N-1; i++ ){
			ans[i] = a[i]+a[i+1]-x;
			if( ans[i]>0 ){
				a[i+1] = a[i+1] - ans[i];
				if( a[i+1]<0 ){
					a[i]+=a[i+1];
					a[i+1] = 0;
				}
				b+=ans[i];              
			}
		}
		System.out.println(b);
	}
}


Measured memory_bytes: 65272
#include <iostream>
#include <vector>
#include <string>

using namespace std;

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

    int plus = A+B;
    int minus = A-B;
    int times = A*B;

    if (plus <= minus && times <= minus) {
        cout << minus;
    } else if (minus <= plus && times <= plus) {
        cout << plus;
    } else {
        cout << times;
    }

    return 0;
};


Measured memory_bytes: 256
const lines=readlines(open("/dev/fd/0"))
let
    state=0
    global input
    input()=lines[state+=1]
end
int(s::String)=parse(Int32,s)
intSub(s::SubString{String})=parse(Int32,s)
intLine()=map(intSub,split(input()))
function main()
    x,y=intLine()
    println(x+Int(y/2))
end
main()

Measured memory_bytes: 117632
#include <bits/stdc++.h>
typedef long long lint;
using namespace std;
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
 
int main() {
    lint n; cin >> n;
    vector<lint> a(n);
    rep(i,n) cin >> a[i];
    bool ans = false;
    sort(a.begin(),a.end(), greater<lint>());
    multiset<lint> setA;
    for(int i=1; i<n; i++) setA.insert(a[i]);
    vector<lint> r(n+1);
    r[0] = a[0];
    r[n] = a[0];
    for(int i=1; i<n; i++) {
        setA.erase(setA.find(a[i]));
        lint want = r[0] ^ a[i];
        auto it = setA.find(want);
        if (it != setA.end()) {
            setA.erase(it);
            r[1] = want;
            r[2] = a[i];
            ans = true;
            break;
        }
        setA.insert(a[i]);
    }
    if (ans) {
        for(int i=3; i<n; i++) {
            lint want = r[i-2] ^ r[i-1];
            auto it = setA.find(want);
            if (it != setA.end()) {
                setA.erase(it);
                r[i] = want;
            } else {
                ans = false;
                break;
            }
        }
    }
    auto o = ans ? "Yes" : "No";
    cout << o << endl;
}

Measured memory_bytes: 9540
def main():
	N = int(input())
	sqrt_n = int(N**0.5)
	ans = 0
	for i in range(1, sqrt_n+1):
		mod = N % i
		if mod == 0 and not(i == N//i or i+1 == N//i):
			ans += N//i - 1

	print(ans)


if __name__ == '__main__':
	main()

Measured memory_bytes: 3060
from bisect import bisect_right
n = int(input())
d = {}
for a in map(int, input().split()):
  if a in d:
    d[a] += 1
  else:
    d[a] = 1
alist = list(sorted(d.keys(), reverse = True))
amax = alist[0]
t = 1
power_of_two = []
while t < 2 * amax:
  t *= 2
  power_of_two.append(t)
result = 0
for a in alist:
  if a not in d or d[a] == 0:
    continue
  t = power_of_two[bisect_right(power_of_two, a)] - a
  while True:
    if t not in d or d[t] == 0:
      break
    if a == t and d[a] == 1:
      break
    result += 1
    d[a] -= 1
    d[t] -= 1
    if a not in d or d[a] == 0:
      break
print(result)


Measured memory_bytes: 44592
n = input()
p = list(map(int,input().split()))
res = 0
for i, num in enumerate(p):
	if(1 <= i and i <= (len(p) - 2)):
		li = [p[i-1],p[i],p[i + 1]]
		li.sort()
		if((p[i-1] != p[i + 1]) and (p[i-1] != p[i]) and (p[i] != p[i + 1]) and (li[1] == p[i])):
			res = res + 1
print(res)

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

using namespace std;

int main() {
  string s;
  cin >> s;
  int n = s.size();
  int ans = 0;
  for (int i = 0; i < n / 2; ++i) {
    if (s[i] != s[(n - 1) -i]) ans++;
  }
  cout << ans << endl;
  return 0;
}



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

int cnt(int p, int n, int k, int w[]){
    int wi = 0;
    rep(i, k){
        int ts = 0;
        while(ts + w[wi] <= p){
            ts += w[wi];
            wi++;
            if(wi == n) return n;
        }
    }
    return wi;
}

int main(){
    int n, k; cin >> n >> k;
    int w[n];
    rep(i, n) cin >> w[i];

    int l = 0;
    int r = 20000*n/k;
    while(r - l > 1){
        int p = (l + r)/2;
        int v = cnt(p, n, k, w);
        if(v >= n) r = p;
        else l = p;
    }
    cout << r << endl;
    return 0;
}


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

int solve(const int *a, const int *b, int s)
{
  int c[10] = {0};
  int borrow = 0;
  for (int i = 0; i < 10; i++) {
    if (a[i] - borrow >= b[i]) {
      c[i] = a[i] - borrow - b[i];
      borrow = 0;
    } else {
      c[i] = a[i] - borrow + 10 - b[i];
      if (s & (1<<i)) {
        borrow = 0;
      } else {
        borrow = 1;
      }
    }
  }
  int n = 0;
  for (int i = 9; i >= 0; i--) {
    n = 10*n + c[i];
  }
  return n;
}

int main()
{
  int A, B, K;
  cin >> A >> B >> K;
  int a[10], b[10];
  for (int i = 0; i < 10; i++) {
    a[i] = A%10;
    b[i] = B%10;
    A /= 10;
    B /= 10;
  }

  int ans = 0;
  for (int s = 0; s < (1<<9); s++) {
    if (__builtin_popcount(s) <= K) {
      ans = max(ans, solve(a, b, s));
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(var, begin, end) for (int var = (begin); var <= (end); var++)
#define RFOR(var, begin, end) for (int var = (begin); var >= (end); var--)
#define REP(var, length) FOR(var, 0, length - 1)
#define RREP(var, length) RFOR(var, length - 1, 0)
#define EACH(value, var) for (auto value : var)
#define SORT(var) sort(var.begin(), var.end())
#define REVERSE(var) reverse(var.begin(), var.end())
#define RSORT(var) SORT(var); REVERSE(var)
#define OPTIMIZE_STDIO ios::sync_with_stdio(false);cin.tie(0);cout.precision(10);cout << fixed
#define endl '\n'

const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll LINF = 1e18;
struct mint {
    ll x;
    mint() : x(0) {}
    mint(ll x) : x((x % MOD + MOD) % MOD) {}
    mint& operator+=(const mint& r) { if ((x += r.x) >= MOD) { x -= MOD; } return *this; }
    mint& operator-=(const mint& r) { if ((x -= r.x) < 0) { x += MOD; } return *this; }
    mint& operator*=(const mint& r) { if ((x *= r.x) > MOD) { x %= MOD; } return *this; }
    mint& operator++() { if ((++x) >= MOD) { x -= MOD; } return *this; }
    mint operator++(int) { mint ret = x; if ((++x) >= MOD) { x-= MOD; } return ret; }
    mint& operator--() { if ((--x) < 0) { x += MOD; } return *this; }
    mint operator--(int) { mint ret = x; if ((--x) < 0) { x += MOD; } return ret; }
    mint operator+(const mint& r) { mint ret; return ret = x + r.x; }
    mint operator-(const mint& r) { mint ret; return ret = x - r.x; }
    mint operator*(const mint& r) { mint ret; return ret = x * r.x; }
    mint operator-() { return mint() - *this; }
    bool operator<(const mint& a) { return x < a.x; }
    bool operator>(const mint& a) { return x > a.x; }
    bool operator<=(const mint& a) { return x <= a.x; }
    bool operator>=(const mint& a) { return x >= a.x; }
    bool operator==(const mint& a) { return x == a.x; }
    bool operator!=(const mint& a) { return x != a.x; }
};
ostream& operator<<(ostream& os, const mint& r) { os << r.x; return os; }
ostream& operator>>(ostream& os, const mint& r) { os >> r.x; return os; }

int dp[105][105];

bool is_white(char c) {
  if (c == '.') return true;
  else
    return false;
}

void solve(istream &cin, ostream &cout) {
  int h, w;
  cin >> h >> w;
  vector<string> s(h);
  REP(i, h) cin >> s[i];
  REP(i, h) REP(j, w) dp[i][j] = INF;
  dp[0][0] = 0;
  REP(i, h) {
    REP(j, w) {
      if (i == 0 && j == 0) continue;
      if (i != 0) {
        if (s[i][j] != s[i - 1][j]) {
          dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1);
        } else {
          dp[i][j] = min(dp[i][j], dp[i - 1][j]);
        }
      }
      if (j != 0) {
        if (s[i][j] != s[i][j - 1]) {
          dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1);
        } else {
          dp[i][j] = min(dp[i][j], dp[i][j - 1]);
        }
      }
    }
  }
  int ans;
  char st = s[0][0], gl = s[h - 1][w - 1];
  if (is_white(st) && is_white(gl)) {
    ans = dp[h - 1][w - 1] / 2;
  } else {
    ans = dp[h - 1][w - 1] / 2 + 1;
  }
  cout << ans << endl;
}

#ifndef TEST
int main() {
  OPTIMIZE_STDIO;
  solve(cin, cout);
}
#endif


Measured memory_bytes: 384
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		long N = sc.nextLong();
		long K = sc.nextLong();
		long ans =0;
		for(long b =1;b<=N;b++){
			long q = N/b;
			long r = N%b;
			ans = ans+q*Math.max(0,b-K)+Math.max(0,r-K+1);
		}
		if(K==0){
			ans = ans-N;
		}
		System.out.println(ans);
		sc.close();
	}
}


Measured memory_bytes: 23764
N = int(input())
# {A:数列に0だけ存在しない集合, B:数列に9だけ存在しない集合}
# 全体集合 - (A + B) + A and B 
ans = (10 ** N - 9 ** N * 2 + 8 ** N) % (10 ** 9 + 7) 
print(ans)

Measured memory_bytes: 11100
#include<iostream>
#include<string>
#include<typeinfo>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
	string s;
	cin >> s;

	int cnt_t=0, cnt_s=0;
	for(int i=0; i<s.length(); i++){
		if(s.at(i)=='S'){
			cnt_s++;
		}else if(cnt_s){
			cnt_s--;
		}else{
			cnt_t++;
		}
	}
	cout << cnt_t+cnt_s << endl;
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9+7,MAX = 1e5;

int gcd(int a,int b){return a%b==0 ? b : gcd(b,a%b);}

int main()
{
	int x,y;
	cin >> x >> y;
	cout<<gcd(x,y)<<endl;
	return 0;
}


Measured memory_bytes: 3092
import bisect
def main():

    N = int(input())
    A = []
    for _ in range(N):
        A.append(int(input()))
    B = [A[-1]]
    for i in range(N-2, -1, -1):
        if B[-1] <= A[i]:
            B.append(A[i])
        else:
            j = bisect.bisect_right(B, A[i])
            B[j] = A[i]
    return len(B)

if __name__ == '__main__':
    print(main())

Measured memory_bytes: 7832
#include <iostream>
#define LL long long
using namespace std;

LL N,K,a[100010];

int main(){
    cin >> N >> K;

    LL i,res=0,sum=0,sump=0,crsump=0;
    for (i=1; i<=N; i++) cin >> a[i];
    for (i=1; i<=N; i++)
        if (a[i]>0) sump+=a[i];

    for (i=1; i<=K; i++){
        sum+=a[i];
        if (a[i]>0) crsump+=a[i];
    }

    res=max(res,sump-crsump+max(sum,0LL));
    for (i=2; i<=N-K+1; i++){
        sum-=a[i-1];
        if (a[i-1]>0) crsump-=a[i-1];
        sum+=a[i+K-1];
        if (a[i+K-1]>0) crsump+=a[i+K-1];
        res=max(res,sump-crsump+max(sum,0LL));
    }


    cout << res << "\n";

    return 0;
}


Measured memory_bytes: 1152
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <queue>
 
using namespace std;
 
#define pb(n)	push_back(n)
#define mp(n,m) make_pair(n,m)
#define fi 	first
#define se 	second
#define all(r) (r).begin(),(r).end()

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const int IMAX=((1<<30)-1)*2+1;
const double EPS=1e-10;
//int mod=1000000007;

string s[3]={"HIT","HOMERUN","OUT"};


int main(){
	map<string,vi> m;
	string s;
	int a;
	while(cin>>s>>a){
		m[s].pb(a);
	}
	for(map<string,vi>::iterator it=m.begin(); it!=m.end(); it++){
		bool f=false;
		cout<<it->fi<<endl;
		sort(all(it->se));
		for(int i=0; i<it->se.size(); i++){
			if(f)cout<<" ";
			cout<<it->se[i];
			f=true;
		}
		cout<<endl;
	}
}

Measured memory_bytes: 1248
from operator import itemgetter


def main():
    N = int(input())
    ab = [tuple(int(j) for j in input().split()) for i in range(N)]
    cd = [tuple(int(j) for j in input().split()) for i in range(N)]
    # y 降順
    ab.sort(key=itemgetter(1), reverse=True)
    # x 昇順
    cd.sort()
    # ペアになった赤
    done = [False] * N
    for bx, by in cd:
        for k, ((rx, ry), d) in enumerate(zip(ab, done)):
            if not d and rx < bx and ry < by:
                done[k] = True
                break
    print(sum(done))
    return


main()


Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <string>
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 10010;
  
int main() {
    ll n, k, c;
    cin >> n >> k >> c;

    string s;
    cin >> s;

    vl v1(n);
    ll i = 0;
    ll num = 1;
    while(i < n && num <= k) {
        if(s[i] == 'o') {
            v1[i] = num;
            i += c;
            num++;
        }
        i++;
    }

    vl v2(n);
    i = n-1;
    num = k;
    while(i >= 0 && num >= 1) {
        if(s[i] == 'o') {
            v2[i] = num;
            i -= c;
            num--;
        }
        i--;
    }

    rep(i, n) {
        if(v1[i] > 0 && v1[i] == v2[i]) {
            out(i+1);
        }
    }
    
    re0;
}

Measured memory_bytes: 4996
#!/usr/bin/env python3
import sys
from math import factorial
from functools import lru_cache

def fact(x: int):
    if(x == 0 or x == 1):
        return 1
    if(dp[x] != 0):
        return dp[x]
    else:
        dp[x] = x * fact(x-1)
        
    return dp[x]

# @lru_cache(maxsize=1000000000)
def comb(n: int, r: int):
    # return fact(n) // (fact(r)*fact(n-r))
    return factorial(n) // (factorial(r)*factorial(n-r))


# dp = [0] * 1000000000

def solve(n: int, a: "List[int]"):
    a.sort()

    m = a[-1]
    print(m, min(a, key=lambda x:abs(m/2-x)))
    
    return


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

if __name__ == '__main__':
    main()


Measured memory_bytes: 16084
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

ll a[22],b[22],c[22];

int main() {
	ll n;
	cin>>n;
	ll ans=0;
	for(int i=100;i<=999;i++){
		ll now=i;
		ll ai=false;
		while(now!=0){
			ll ch=now%10;
			if(ch>n||ch==0){
				ai=true;
				break;
			}
			now/=10;
		}
		if(ai!=true){
			ans++;
		}
	}
	cout <<ans;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
using namespace std;
int n;
int a[200000];

int main()
{
    scanf("%d",&n);
    int maxNum=0;
    int idx1=0;
    int idx2=0;
    for (int i=1; i<=n; ++i)
    {
        scanf("%d",&a[i]);
        if (a[i]>maxNum)
        {
            maxNum=a[i];
            idx1=i;
        }
    }
    int maxDiff=0;
    for (int i=1; i<=n; ++i)
        if (min(a[i],maxNum-a[i])>maxDiff)
        {
            maxDiff=min(a[i],maxNum-a[i]);
            idx2=i;
        }
    cout<<a[idx1]<<' '<<a[idx2]<<endl;
    return 0;
}


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

const int64_t MOD = 1000000007;
typedef int64_t ll;
typedef uint64_t ull;

#define FOR(i, start, end) for(uint64_t i=start; i<end; i++)
#define REP(i, n) FOR(i, 0, n)

// 最大公約数gcd
// 最小公倍数lcm=m*n/gcd
uint64_t gcd(uint64_t m, uint64_t n) {
  uint64_t temp;
  while (m % n != 0){
    temp = n;
    n = m % n;
    m = temp;
  }
  return n;
}

uint64_t lcm(uint64_t m, uint64_t n) {
  uint64_t g = gcd(m,n);
  if(m%g==0) return (m/g)*n;
  if(n%g==0) return (n/g)*m;
  return (m*n)/gcd(m,n);
}

// vector<vector<uint64_t> > v(n+1, vector<uint64_t>(n+1, 0))
// v[n][k]に組み合わせ数が入る。
void comb(vector<vector <uint64_t> > &v){
  for(uint64_t i = 0;i <v.size(); i++){
    v[i][0]=1;
    v[i][i]=1;
  }
  for(uint64_t k = 1;k <v.size();k++){
    for(uint64_t j = 1;j<k;j++){
      v[k][j]=(v[k-1][j-1]+v[k-1][j]);
    }
  }
}

// 掛け算オーバーフロー判定
bool is_product_overflow(uint64_t a, uint64_t b) {

	uint64_t prod = a * b;
	
	return (prod / b != a);
}

//素因数分解
void primeFactorization(uint64_t a, list<uint64_t> &factors){ //素因数分解を出力するプログラム
  long i,sq;
  if(a%2==0){ //偶数の場合
    factors.push_back(2);
    primeFactorization(a/2,factors); //2で割った値で再帰
    return;
  }
  sq = sqrt(a);
  for(i=3;i<=sq;i+=2){ //3以上√a以下の奇数の場合
	if(a%i==0){
	  factors.push_back(i);
      primeFactorization(a/i,factors); //割れた値で再帰
      return;
	}
  }
  //偶数でも3以上√a以下の奇数の場合でも割り切れない場合
  if(a!=1){ //aが1でないなら、a自身は素数
    factors.push_back(a);
  }
}

// フェルマーの小定理
// mod. m での a の逆元 a^{-1} を計算する
// (a/b)%m = a*movinv(b,m)%m  
int64_t modinv(int64_t a, int64_t m) {
    int64_t b = m, u = 1, v = 0;
    while (b) {
        int64_t t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

/* 
  //エラトステネスのふるい
  int maxNum = 100000;
  char isNotPrime[maxNum+1] = {};
  isNotPrime[0]=isNotPrime[1]=1;
  for(int i=2;i<maxNum;i++){
    if(isNotPrime[i]==1) continue;
    int num = i+i;
    while(num<=maxNum){
      isNotPrime[num]=1;
      num += i;
    }
  }
*/
// 円周率
// M_PI

// #include <iomanip> // setprecisionを使用するのに必要
// cout << std::fixed << std::setprecision(15) << y << endl;

// 昇順
// priority_queue<int, vector<int>, greater<int> > queue;

// 降順ソート vector<int> v;
// sort(v.begin(),v.end(),greater<int>());

// keyが降順ソートされるmap
// map<int, int, std::greater<int>> edges;

signed main() {
  int n,m;
  cin >> n >> m;

  vector< vector<int> > ship(n);
  int a,b;
  for(int i=0;i<m;i++){
    cin >> a >> b; a--; b--;
    ship[a].push_back(b);
    ship[b].push_back(a);
  }
  
  for(auto nI:ship[0]){
    for(auto nnI:ship[nI]){
      if(nnI==n-1){
        cout << "POSSIBLE" << endl;
        return 0;
      }
    }
  }
  cout << "IMPOSSIBLE" << endl;
  
  return 0;
}



Measured memory_bytes: 14932
N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]
ans = 0

for i in range(N):
    ans += B[A[i]-1]
    if i > 0:
        if A[i] - A[i-1] == 1:  ans += C[A[i-1]-1]

print(ans)

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

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

Measured memory_bytes: 256
import fractions

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

A, B, C, D = map(int, input().split())

lcm_CD = lcm(C, D)
count = (B // C - (A-1) // C) + (B // D - (A-1) // D) - (B // lcm_CD - (A-1) // lcm_CD)
    
print((B - A + 1) - count)

Measured memory_bytes: 5048
#include<iostream>
using namespace std;
#define MAX 500000
#define SENTINEL 2000000000

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

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

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

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

  cin >> n;
  for ( i = 0; i < n; i++ ) cin >> A[i];

  mergeSort(A, n, 0, n);

  for ( i = 0; i < n; i++ ) {
    if ( i ) cout << " ";
    cout << A[i];
  }
  cout << endl;

  cout << cnt << endl;

  return 0;
}


Measured memory_bytes: 6976
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,x;
	cin>>n>>x;
	int a[n];
	for(int i=0;i<n;i++)
		cin>>a[i];
	int sum=0;
	sort(a,a+n);
	for(int i=0;i<n;i++)
	{
		sum+=a[i];
		if(sum>x)
		{
			cout<<i;
			return 0;
		}
		else if(sum==x)
		{
			cout<<i+1;
			return 0;
		}
	}
	cout<<n-1;
	
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#define df 0
typedef struct{
  int a;
  int b;
}data;

int n;

int c(const void *x,const void *y){
  data p=*(data*)(x);
  data q=*(data*)(y);
  return(q.b-p.b);
}

void print(data* d){
  int i;
  for(i=0;i<n;i++){
    printf("(%d,%d) ",d[i].a,d[i].b);
  }
  printf("\n");
}

int main(){
  scanf("%d",&n);
  int i;
  data d[n];
  for(i=0;i<n;i++){
    scanf("%d%d",&(d[i].a),&(d[i].b));
  }
  qsort(d,n,sizeof(data),c);
  if(df)print(d);
  int time=d[0].b,ans=1;
  for(i=0;i<n;i++){
    if(time>d[i].b)time=d[i].b;
    if(time<d[i].a){
      ans=0;break;
    }
    if(df)printf("[%d,%d]  (%d,%d)\n",time-d[i].a,time,d[i].a,d[i].b);
    time-=d[i].a;
  }

  printf("%s",ans?"Yes":"No");
}


Measured memory_bytes: 3324
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IOS; ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define MX  1002
#define FF freopen("input.in","r",stdin); freopen("output.txt","w",stdout);
int n,m;
int dp[MX][MX];
char a[MX][MX];
int f(int i,int j)
{
    if(i==n&&j==m)
        return 1;
    else if(i==n+1||j==m+1)return 0;
    if(a[i][j]=='#')return 0;
    if(dp[i][j]!=-1)return dp[i][j];
    return dp[i][j]=(f(i+1,j)%1000000007+f(i,j+1)%1000000007)%1000000007;
}
int main()
{
    //FF;
    IOS;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
        }
    }
    memset(dp,-1,sizeof dp);
    //bfs();
    cout<<f(1,1);

}



Measured memory_bytes: 5248
#include <iostream>
//#include <fstream>
#include <unordered_map>

using namespace std;

int main(int argc, const char * argv[]) {
//    ifstream in("input.txt");
//    cin.rdbuf(in.rdbuf());
    
    string S;
    cin >> S;
    
    unordered_map<char, int> um;
    
    
    for (int i=0; i<4; i++)
    {
        if (um.count(S[i]) == 0)
        {
            um[S[i]] = 1;
        }
        else
        {
            ++um[S[i]];
        }
    }
    
    if (um.size()==2)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    
    return 0;
}

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

int main(){
    string S;
    cin >> S;

    vector<char> s = {'a', 'b', 'c', 'd', 'e', 
                      'f', 'g', 'h', 'i', 'j',
                      'k', 'l', 'm', 'n', 'o',
                      'p', 'q', 'r', 's', 't',
                      'u', 'v', 'w', 'x', 'y', 'z'};

    vector<bool> charFlag(26);

    for(int i = 0; i < S.size(); i++){
        for(int j = 0; j < s.size(); j++){
            if(S.at(i) == s.at(j)){
                charFlag.at(j) = true;
                break;
            }
        }
    }

    bool ansFlag = false;
    for(int i = 0; i < s.size(); i++){
        if(charFlag.at(i) == false){
            cout << s.at(i) << endl;
            ansFlag = true;
            break;
        }
    }

    if(ansFlag == true){

    }else{
        cout << "None" << endl;
    }

}

Measured memory_bytes: 3760
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cassert>
#include <cstdint>
#include <numeric>
#include <bitset>
#include <functional>

using namespace std;

using ll =  long long;
using Pll = pair<ll, ll>;
using Pii = pair<int, int>;

constexpr ll MOD = 1000000007;
constexpr long double EPS = 1e-10;
constexpr int dyx[4][2] = {
    { 0, 1}, {-1, 0}, {0,-1}, {1, 0}
};
constexpr ll INF = 1LL << 50;

int H, W;
vector<vector<ll>> x(80, vector<ll>(80, 0));
vector<vector<ll>> y(80, vector<ll>(80, 0));

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> H >> W;
    for(int i=0;i<H;++i){
        for(int j=0;j<W;++j) cin >> x[i][j];
    }
    for(int i=0;i<H;++i){
        for(int j=0;j<W;++j) cin >> y[i][j];
    }

    vector<vector<vector<bool>>> dp(H, vector<vector<bool>>(W, vector<bool>(12801, false)));
    dp[0][0][abs(x[0][0]-y[0][0])] = true;
    for(int i=0;i<H;++i) {
        for(int j=0;j<W;++j) {
            for(int k=0;k<=12800;++k) {
                if(!dp[i][j][k]) continue;
                if(i != H-1) {
                    dp[i+1][j][abs(k+x[i+1][j]-y[i+1][j])] = true;
                    dp[i+1][j][abs(k-x[i+1][j]+y[i+1][j])] = true;
                }
                if(j != W-1) {
                    dp[i][j+1][abs(k+x[i][j+1]-y[i][j+1])] = true;
                    dp[i][j+1][abs(k-x[i][j+1]+y[i][j+1])] = true;
                }
            }
        }
    }

    ll ans = INF;
    for(int k=0;k<=12800;++k) {
        if(dp[H-1][W-1][k]) {
            ans = k;
            break;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 10880
#include <iostream>
#include <vector>
#include <unordered_set>
#include <cstring>

using namespace std;


const int INF = 1e9 + 5;

int main() {
    int n;
    scanf("%d", &n);
    int k;
    scanf("%d", &k);
    vector<int> h(n);
    for(int& x : h) {
        scanf("%d", &x);
    }
    vector<int> dp(n, INF);
    dp[0] = 0;
    for(int i = 0; i < n; ++i) {
        for(int j = i + 1; j <= i + k; ++j) {
            if(j < n) {
                dp[j] = min(dp[j], dp[i] + abs(h[i] - h[j]));
            }
        }
    }
    printf("%d\n", dp[n-1]);
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb(a) push_back(a)
#define pbp(a,b) push_back({a,b})
#define rep(p,a,b)    for(int p=a;p<b;p++)
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define INF 0x3f3f3f3f

ll nextPowerOf2(ll n)   
{ 
	n--; 
	n |= n >> 1ll; 
	n |= n >> 2ll; 
	n |= n >> 4ll; 
	n |= n >> 8ll; 
	n |= n >> 16ll; 
	n++; 
	return n; 
}


int main() {
	
	#ifndef ONLINE_JUDGE
	// for getting input from input.txt
	freopen("input.txt", "r", stdin);
	// for writing output to output.txt
	freopen("output.txt", "w", stdout);
	#endif

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	ll n,t,i,k,sum=0ll,x,y;
	map<ll,ll> m;

	cin>>n;
	while(n--)
	{
		cin>>x;
		m[x]++;
		sum+=x;
	}

	cin>>t;
	while(t--)
	{

		cin>>x>>y;
		sum += ((y-x)*m[x]);
		cout<<sum<<"\n";
		m[y] += m[x];
		m[x] = 0;
	}
	

	return 0;
}

Measured memory_bytes: 9564
n, y = gets.strip.split.map(&:to_i)

_i, _j, _k = -1, -1, -1

(0..n).each do |i|
    (0..n-i).each do |j|
    	if i * 10000 + j * 5000 + (n-i-j) * 1000 == y
    		_i, _j, _k = i, j, n-i-j
    	end
    end
end

puts "#{_i} #{_j} #{_k}"

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

using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

const int MM = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e6 + 10;

int n, m;
char s[MAXN]; 

void read(){
	scanf("%s", s);
}

int cnt[10];

void solve(){
	int l =strlen(s);
	for(int i = 0 ; i< 4; i++)
		cnt[i] = 0;
	for(int i = 0; i < l; i++){
		if (s[i] == 'S') cnt[0]=1;
		if (s[i] == 'N') cnt[1]=1;
		if (s[i] == 'E') cnt[2]=1;
		if (s[i] == 'W') cnt[3]=1;
	}
	if ((cnt[0]^cnt[1]) == 0 && (cnt[2]^cnt[3]) == 0)
		puts("Yes");
	else
		puts("No");
}

void printans(){
	
}
	

int main(){
	int T = 1;
//	cin>>T;
	while(T--){
		read();
		solve();
		printans();
	}
	return 0;
} 


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
 
const double EPS = 1e-10;
const ll INF = 100000000;
const ll MOD = 1000000007;

ll n;
ll a[100001];
ll ans = 0;
ll sum[100001];
ll kai[100001];

inline ll add (ll x, ll y) {
    return (x+y)%MOD;
}

ll mod_pow (ll x, ll y) {
    ll ret = 1;
    while (y) {
        if (y&1) ret = ret * x % MOD;
        x = x * x % MOD;
        y /= 2;
    }
    return ret;
}

int main() {
    cin >> n;
    rep(i,n) cin >> a[i];
    kai[0] = 1;
    for (ll i = 1; i <= n; i++) kai[i] = kai[i-1] * i % MOD;
    rep(i,n) {
        if (i == 0) sum[i] = a[i];
        else sum[i] = add(sum[i-1], a[i]);
    }
    ans = add(ans, sum[n-1]);
    ans = ans*kai[n]%MOD;
    {
        ll acc = 0;
        rep(i,n-1) {
            acc = add(acc, a[i]);
            ll tmp = acc * kai[n] % MOD;
            tmp = tmp * mod_pow(i+2, MOD-2) % MOD;
            ans = add(ans, tmp);
        }
    }
    {
        ll acc = 0;
        for (int i = n-1; i >= 1; i--) {
            acc = add(acc, a[i]);
            ll tmp = acc * kai[n] % MOD;
            tmp = tmp * mod_pow(n-i+1, MOD-2) % MOD;
            ans = add(ans, tmp);
        }
    }
    {
        ll acc = 0;
        ll l = 0, r = n-2;
        for (int i = 1; i <= n-2; i++) {
            acc = (acc + sum[r] - sum[l] + MOD) % MOD;
            ll tmp = acc * kai[n] * 2LL % MOD;
            tmp = tmp * mod_pow(i+2, MOD-2) % MOD;
            tmp = tmp * mod_pow(i+1, MOD-2) % MOD;
            ans = add(ans, tmp);

            l++; r--;
        }
    }
    cout << ans << endl;
}



Measured memory_bytes: 2560
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>

using namespace std;

#define int long long

int pos[26][100001];

signed main()
{
	string s, t;
	int sCnt[26] = { 0 }, tCnt[26] = { 0 };

	cin >> s >> t;

	for(int i = 0; i < s.size(); ++i)
	{
		++sCnt[s[i] - 'a'];
	}

	for(int i = 0; i < t.size(); ++i)
	{
		++tCnt[t[i] - 'a'];
	}

	for(int i = 0; i < 26; ++i)
	{
		pos[i][s.size()] = -1;
		for(int j = s.size() - 1; j >= 0; --j)
		{
			pos[i][j] = (s[j] == ('a' + i) ? j : pos[i][j + 1]);
		}
	}

	for(int i = 0; i < 26; ++i)
	{
		if(sCnt[i] == 0 && tCnt[i] > 0)
		{
			cout << -1 << endl;
			return 0;
		}
	}

	int ans = 0;
	for(int i = 0; i < t.size(); ++i)
	{
		int c = t[i] - 'a';
		int p = ans % s.size();
		
		if(pos[c][p] == -1)
		{
			ans += (s.size() - p) + pos[c][0] + 1;
		}
		else
		{
			ans += pos[c][p] - p + 1;
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 20864
import java.util.Scanner;

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

		int n = sc.nextInt();
		int m = sc.nextInt();
		String[] a = new String[n];
		String[] b = new String[m];

		for (int i = 0; i < a.length; i++) {
			a[i] = sc.next();
		}
		for (int i = 0; i < b.length; i++) {
			b[i] = sc.next();
		}

		for (int i = 0; i <= n - m; i++) {
			outer:
			for (int j = 0; j <= n - m; j++) {
				for (int k = 0; k < m; k++) {
					for (int l = 0; l < m; l++) {
						if (a[i + k].charAt(j + l) != b[k].charAt(l)) {
							continue outer;
						}
					}
				}
				System.out.println("Yes");
				return;
			}
		}
		System.out.println("No");

		sc.close();
	}
}

Measured memory_bytes: 23892
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	N, Q, str := ReadInt(), ReadInt(), ReadString()

	sum := make([]int, N+1)
	for i := 1; i < N; i++ {
		incr := 0
		if str[i-1:i+1] == "AC" {
			incr++
		}
		sum[i+1] = sum[i] + incr
	}

	for q := 0; q < Q; q++ {
		l, r := ReadInt(), ReadInt()
		fmt.Println(sum[r] - sum[l])
	}
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int)       { Scan(&i); return }
func ReadString() (s string) { Scan(&s); return }


Measured memory_bytes: 6296
n=int(input())
a=list(map(int,input().split()))
amin=min(a)
amax=max(a)
imin=a.index(min(a))+1
imax=a.index(max(a))+1
if amin>=0:
  print(n-1)
  for i in range(1,n):
    print("{} {}".format(i,i+1))
  exit()
if amax<=0:
  print(n-1)
  for i in range(1,n):
    print("{} {}".format(n-i+1,n-i))
  exit()
print(2*n-1)
if abs(amin)<=abs(amax):
  for i in range(1,n+1):
    print("{} {}".format(imax,i))
  for i in range(1,n):
    print("{} {}".format(i,i+1))
  exit()
if abs(amin)>=abs(amax):
  for i in range(1,n+1):
    print("{} {}".format(imin,i))
  for i in range(1,n):
    print("{} {}".format(n-i+1,n-i))

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

// clang-format off
template <typename T> T gcd(T a, T b) { return b == 0 ? a : gcd(b, a % b); }
template <typename T> T lcm(T a, T b) { return a * b / gcd(a, b); }
template <typename T> T clamp(T val, T min, T max) { return val < min ? min : (max < val ? max : val); }
char capitalize(char c) { return static_cast<char>(std::toupper(static_cast<unsigned char>(c))); }
// template <typename T> size_t max_index(T begin, T end) { return distance(begin, max_element(begin, end)); }
// template <typename T> size_t min_index(T begin, T end) { return distance(begin, min_element(begin, end)); }
// clang-format on

// #define int long long
#define YES "Yes"
#define NO  "No"

using namespace std;

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

  int num = 0;
  // num = numeric_limits<int>::max();
  // num = numeric_limits<int>::min();
  bool flag = false;
  // flag = true;

  int a, b, c; cin >> a >> b >> c;
  if (a + b == c) flag = true;
  if (a + c == b) flag = true;
  if (b + c == a) flag = true;

  // cout << num << endl;
  cout << (flag ? YES : NO) << endl;
  
  return 0;
}


Measured memory_bytes: 256
import math
l , h , V = map(int,input().split())

h_0 = V / (l * l)

if h_0 >= h/2:
  theta_r = math.atan((h-h_0)/(0.5 * l))
  theta = 180 * theta_r / math.pi
  print(theta)
else:
  x = 2 * V / (l * h)
  theta_r = math.atan(x / h)
  theta = 90- (180 * theta_r / math.pi)
  print(theta)
  



Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define mo 998244353
#define ll long long
using namespace std;
ll n,k,f[5010][5010];
ll po(ll x,ll y){ll z=1;while (y){if (y%2==1) z=(x*z)%mo;x=(x*x)%mo;y/=2;}return z;}
ll work(ll x,ll y,ll z){
	ll sum=0;
	for (ll i=1;i<=y&&i<=x;i++){
		sum=sum+(f[y+z-1][i+z-1]*f[x][i]%mo)*po(2,i);
		sum=sum%mo;
	}
	if (z!=0){sum=sum+f[y+z-1][z-1];sum%=mo;}
	return sum;
}
int main(){
	cin>>k>>n;
	f[0][0]=1;
	for (ll i=1;i<=n+k;i++){
		for (ll j=0;j<=i;j++){
			f[i][j]=f[i-1][j];
			if (j!=0) f[i][j]+=f[i-1][j-1];
			f[i][j]%=mo;
		}
	}
	for (ll i=2;i<=k+k;i++){
		ll j=min(i,k+k+2-i);
		if (j%2==1)cout<<work(j/2,n,k-j+1)<<endl;
		else cout<<(work(j/2-1,n-1,k-j+1)+work(j/2-1,n,k-j+1))%mo<<endl;
	}
	return 0;
}

Measured memory_bytes: 156160
#include <iostream>
#include <utility>
#include <map>
#include <algorithm>
using namespace std;

int main(){
  int n;
  cin >> n;
  map<int, int>even, odd;
  even[0]=0;
  odd[0]=0;
  for(int i=0; i<n; i++){
    int tmp;
    cin >> tmp;
    if(i%2==0)even[tmp]++;
    else odd[tmp]++;
  }
  int m=0, mne1, mne2, mno1, mno2;
  for(pair<int, int>p: even){
    if(p.second>=m){
      m=p.second;
      mne1=p.first;
    }
  }
  m=0;
  for(pair<int, int>p: even){
    if(p.second>=m && p.first!=mne1){
      m=p.second;
      mne2=p.first;
    }
  }
  m=0;
  for(pair<int, int>p: odd){
    if(p.second>=m){
      m=p.second;
      mno1=p.first;
    }
  }
  m=0;
  for(pair<int, int>p: odd){
    if(p.second>=m && p.first!=mno1){
      m=p.second;
      mno2=p.first;
    }
  }
  if(mne1!=mno1)cout << n-even[mne1]-odd[mno1];
  else {
    cout << min(n-even[mne1]-odd[mno2], n-even[mne2]-odd[mno1]);
  }
  return 0;
}

Measured memory_bytes: 4992
n = int(raw_input())
sec = map(int,raw_input().split())

count = 0
for i in range(0,n):
    mini = i
    for j in range(i,n):
        if sec[j]<sec[mini]:
            mini = j
    if mini != i:
        count += 1
        sec[mini],sec[i] = sec[i],sec[mini]
print " ".join(map(str,sec))
print count

Measured memory_bytes: 4224
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define vll vector<ll>
#define endl "\n"
#define pll pair<ll,ll>
#define all(x) (x).begin() , (x).end()
#define in insert
#define REP(i,n) for (int i = 1; i <= n; i++)
#define matrix vector<vector<ll> > 
using namespace std;
 
const ll N = 1e5+2;
const ll MOD = 1e9+7;
const ll INF = 1e16;
const ll LOG = 25;
 
long long binpow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	// ifstream fin ("sound.in");
	// ofstream fout("sound.out");
	string s;
	cin >> s;
	ll n = 1ll*s.size();
	string t;t+= '@';
	t+=s;
	s =t;
	if(s[1] == '0' || s[n] == '1'){
		return cout<<"-1\n",0;
	}
	for(int i =1;i<=n-1;i++){
		if(s[i] != s[n-i]){
			//cout<<i<<' '<<n-i<<endl;
			return cout<<"-1\n",0;
		}
	}
	s[n]='1';	
	//cout<<1ll*v.size()<<endl;
	vector<pll> ans;
	ll nxt = 0;
	for(int i =1;i<n;i++){
		while(nxt <= i || s[nxt] == '0')
			nxt++;
		cout<<nxt<<" "<<i<<endl;
	}

	
	return 0;
}

Measured memory_bytes: 1664
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <iterator>
#include <cmath>
#include <set>
#include <deque> 
#include <string>


using namespace std;


int main()
{
	int l, r, d;
	scanf("%d%d%d", &l, &r, &d);
	
	int count = 0;
	for (int i = l ; i <= r ; i++) {
		if (i % d == 0)
			count++;
	}
	
	printf("%d\n", count);
	
	return 0;
}


Measured memory_bytes: 1728
def primes():
    D = {}
    q = 2
    while True:
        if q not in D:
            yield q
            D[q * q] = [q]
        else:
            for p in D[q]:
                D.setdefault(p + q, []).append(p)
            del D[q]
        q += 1


N = int(input())
ans = list()
for p in primes():
    if len(ans) >= N:
        break
    if p % 5 == 1:
        ans.append(p)

print(' '.join([str(p) for p in ans]))


Measured memory_bytes: 3064
#include<stdio.h>

int main()
{
  char b,n;


while(1){
  scanf("%s",&b);
  if(b=='A'||b=='T'||b=='C'||b=='G')
    break;
}
  
if(b=='A')  
  printf("T");
else if(b=='T')
  printf("A");
else if(b=='C')
  printf("G");
else if(b=='G')
  printf("C");
  
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
 
using namespace std;
using namespace __gnu_pbds;
using lli = long long int;
 
template<typename key> using ordered_set = tree <key, null_type, less<key>, rb_tree_tag, tree_order_statistics_node_update>;
 
int main () {
   IO;
   string s, t;
   cin >> s >> t;
   cout << t << s;
   return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1000000000000000000;
const int mod = 1000000007;
int test[12345678], res[12345678];
signed main() {
	vector<char> v; map<int, int> cost;
	int n, m, a, b, c, cnt = 0, ans = 0; string s, t;
	cin >> s >> t;
	for (int h = 0; h < s.size(); h++) {
		if (s[h] != t[h]) { cout << "No\n"; return 0; }
	}
	cout << "Yes\n";
	return 0;
}

Measured memory_bytes: 3620