akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#include<string>
#include<math.h>
using namespace std;

const long long MAX = 1000000000000LL;

bool isPrime(long long n){
    for(int i = 2;i <= sqrt(n);i++){
        if(n % i == 0)return false;
    }
    return true;
}

int main(){
    long long N;
    long long x = 2;
    int ans = 0;

    cin >> N;

    while(N != 1){
        int cnt = 0;
        
        while(N % x == 0){
            N /= x;
            cnt++;
        }

        int n = 1;
        while(cnt - n >= 0){
            cnt -= n;
            n++;
            ans++;
        }

        x++;

        while(!isPrime(x)){
            x++;
            if(x > sqrt(MAX)){
                ans += 1;
                N = 1;
                break;
            }
        }
    }

    cout << ans << endl;

    return 0;
}


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

int main() {
  int n;
  unsigned long long ans = 1;
  cin >> n;
  bool z = false;
  vector<long long> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    if (a[i] == 0) {
      z = true;
    }
  }

  if (z) {
    cout << "0" << endl;
    return 0;
  }

  sort(a.begin(), a.end());
  reverse(a.begin(), a.end());

  for (int i = 0; i < n; i++) {
    if (ans > 1000000000000000000 / a[i]) {
      cout << "-1" << endl;
      return 0;
    }
    ans *= a[i];
  }

  cout << ans << endl;
}


Measured memory_bytes: 3988
#include<bits/stdc++.h>
#define rep(i, l, r) for(int i = (l), i##end = (r);i <= i##end;++i)
using std::cin; using std::cout;
const int maxn = 3030;
typedef long long ll;
const int mod = 1e9 + 7;
inline void reduce(int & x) {
	x += x >> 31 & mod;
}
int n, m;
int f[maxn][maxn][2];
int main() {
	std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	rep(i, 0, n) f[0][i][!i] = 1;
	rep(i, 1, m) {
		rep(j, 0, n) {
			rep(k, 0, 1) {
				if(j != 0) {
					reduce(f[i][j][k || j == 1] += f[i - 1][j][k] - mod);
					reduce(f[i][j - 1][k || j == 1] += f[i - 1][j][k] - mod);
				}
				if(j != n) {
					reduce(f[i][j][k] += f[i - 1][j][k] - mod);
					reduce(f[i][j + 1][k] += f[i - 1][j][k] - mod);
				}
			}
		}
	}
	int ans = 0;
	rep(i, 0, n) reduce(ans += f[m][i][1] - mod);
	cout << ans << '\n';
}


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

using namespace std;
typedef long long ll;

#define MOD (long long)(1e9+7)
#define INF (1LL<<60)
#define rep(i,n) for(ll i = 0; i < (n); i++)
#define rep1(i,n) for(ll i = 1; i <= (n); i++)

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


// 最大公約数
ll gcd(ll a, ll b)
{
  if(b == 0) return a;
  return gcd(b, a % b);
}

// mod m におけるa の逆元
ll modinv(ll a, ll m) {
  ll b = m, u = 1, v = 0;
  while (b) {
    ll t = a / b;
    a -= t * b; swap(a, b);
    u -= t * v; swap(u, v);
  }
  u %= m;
  if (u < 0) u += m;
  return u;
}

// 素因数分解
vector<pair<ll, ll>> prim;
void pf(ll n)
{
  ll s = sqrt(n);
  ll r = 0;
  for(ll i = 2; i <= s; i++) {
    if((n % i) == 0) {
      r = 0;
      do {
	r++;
	n = n / i;
      } while((n % i) == 0);
      prim.push_back({i, r});
    }
  }
  if(n > s) {
    prim.push_back({n, 1});
  }
}

void solve()
{
  ll N; cin >> N;
  string w[] = {"AC", "WA", "TLE", "RE"};

  // ll N, K; cin >> N >> K;
  // ll x, y, z; cin >> x >> y >> z;
  // ll a, b, c; cin >> a >> b >> c;
  vector<ll> cnt(5,0);
  rep(i, N){
    string s; cin >> s;
    rep(j,4) {
      if(s==w[j]) cnt[j] ++;
    }
  }
  rep(i, 4) {
    cout << w[i] << " x " << cnt[i] << endl;
  }
}


int main(void)
{
  // ll t; cin >> t; rep(i, t)
  solve();
}


Measured memory_bytes: 3716
n=int(input())
l=[]
r=[]
ans=0
for i in range(n):
    a,b=map(int,input().split())
    l.append(a)
    r.append(b)
l.sort()
r.sort()
if n%2==0:
    ans=int(((r[n//2]+r[n//2-1])/2-(l[n//2]+l[n//2-1])/2)*2+1)
else:
    ans=r[n//2]-l[n//2]+1
print(ans)

Measured memory_bytes: 25540
#include <iostream>
#include <type_traits>
#include <iomanip>
#include <cstdint>
#include <string>
#include <set>
#include <map>
#include <algorithm>

using int64 = long long;

int n;
int A[100010], C[100010];

int main() {
    std::cin >> n;
    
    int tmp;
    for(int i = 0; i < n; ++i) {
        std::cin >> tmp;
        C[i] = tmp;
        A[i] = tmp;
    }
    
    std::sort(C, C + n);
    
    int64 cnt = 0;
    for(int i = 0; i < n; ++i) {
        cnt += std::abs(i - (std::lower_bound(C, C + n, A[i]) - C)) % 2;
    }
    
    std::cout << cnt / 2 << std::endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   // 0-indexed昇順
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

int main() {
    ll N, L;
    cin >> N >> L;
    vector<ll> W(N);
    vector<ll> V(N);
    rep(i,N) cin >> W.at(i) >> V.at(i);
    ll MV = 100001;
    ll DP[N+1][MV];
    for (ll i = 0; i <= N; i++) for (ll j = 0; j < MV; j++) DP[i][j] = 1L<<62;
    DP[0][0] = 0;
    for (ll i = 0; i < N; i++) {
        for (ll j = 0; j < MV; j++) {
            if (j - V[i] >= 0) {
                chmin(DP[i+1][j], DP[i][j - V[i]] + W[i]);
            }
            chmin(DP[i+1][j], DP[i][j]);
        }
    }
    /*
    rep (i,N+1) {
        rep(j,142) {
            ll w = DP[i][j];
            if (w == 1L<<62) printf(" F");
            else printf(" %3ld", DP[i][j]);
        }
        printf("\n");
    }
    */
   ll ma = 0;
   for (ll i = 0; i < MV; i++) {
       if (DP[N][i] <= L) {
           // printf("%ld : %ld\n", i, DP[N][i]);
           chmax(ma, i);
       }
   }
   cout << ma << endl;
}

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

// 総数を1000000007（素数）で割った余り
const long long mod = 1e9 + 7;

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

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

int main(){
    int n, a, b;
    cin >> n >> a >> b;
    cout << min(a * n, b) << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
typedef long long LL;
const int LEN = 2e5 + 10;
int A[LEN], P[LEN];

int main() {
    LL N, K;
    cin >> N >> K;
    for (int i = 1; i <= N; i++) {
        cin >> A[i];
    }
    int old_index = 1, new_index = 1, cnt = 1;
    P[new_index] = cnt;
    while (K--) {
        old_index = new_index;
        new_index = A[old_index];
        cnt++;
        if (P[new_index]) {
            K %= cnt - P[new_index];
        } else {
            P[new_index] = cnt;
        }
    }
    cout << new_index << endl;
    return 0;
}

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

const int INF = 1e+9;
typedef pair<int, int> P;

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, -1, 1};
int h, w;
int maze[256][128];

bool check(int x, int y){
	return x >= 0 && x < w && y >= 0 && y < h * 2 - 1 && maze[y][x] == 0;
}
int main() {
	
	while(cin >> w >> h && (w || h)){
		for(int i = 0; i < 256; ++i)
			for(int j = 0; j < 128; ++j)
				maze[i][j] = 0;
			
		for(int i = 0; i < h * 2 - 1; ++i){
			if(i % 2){
				for(int j = 0; j < w; ++j){
					scanf("%d", &maze[i][j]);
				}
			}
			else{
				for(int j = 0; j < w - 1; ++j){
					scanf("%d", &maze[i][j]);
				}		
			}
		}
		int d[128][128];
		for(int i = 0; i < 128; ++i)
			for(int j = 0; j < 128; ++j)
				d[i][j] = INF;
		
		int ans = 0;
		queue<P> que;
		que.push(P(0, 0));
		d[0][0] = 0;
		while(!que.empty()){
			P p = que.front();
			que.pop();
			if(p.first == w - 1 && p.second == h - 1){
				ans = d[h - 1][w - 1] + 1;
				break;
			}
			for(int i = 0; i < 2; ++i){
				int nx = p.first + dx[i];
				int ny = p.second + dy[i];
				if(i == 0 && check(nx - 1, ny * 2) && d[ny][nx] == INF){
					d[ny][nx] = d[p.second][p.first] + 1;
					que.push(P(nx, ny));
				}
				if(i == 1 && check(nx, ny * 2) && d[ny][nx] == INF){
					d[ny][nx] = d[p.second][p.first] + 1;
					que.push(P(nx, ny));
				}
			}
			for(int i = 2; i < 4; ++i){
				int nx = p.first + dx[i];
				int ny = p.second + dy[i];
				if(i == 2 && check(nx, ny * 2 + 1) && d[ny][nx] == INF){
					d[ny][nx] = d[p.second][p.first] + 1;
					que.push(P(nx, ny));
				}
				else if(i == 3 && check(nx, ny * 2 - 1) && d[ny][nx] == INF){
					d[ny][nx] = d[p.second][p.first] + 1;
					que.push(P(nx, ny));
				}
			}
		}
		cout << ans << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1448
#include<bits/stdc++.h>
using namespace std;
void qmax(int &x,int y) {if (x<y) x=y;}
void qmin(int &x,int y) {if (x>y) x=y;}
int read()
{
    char s;
    int k=0,base=1;
    while((s=getchar())!='-'&&s!=EOF&&!(isdigit(s)));
    if(s==EOF)exit(0);if(s=='-')base=-1,s=getchar();
    while(isdigit(s)){k=k*10+(s^'0');s=getchar();}
    return k*base;
}
void write(int x)
{
    if(x<0){putchar('-');write(-x);}
    else{if(x/10)write(x/10);putchar(x%10+'0');}
}
int n,x; 
int a[5000000],p;
bitset<4111111> k;
int main()
{
	n=read();
	k[0]=1;
	for (int i=1;i<=n;i++)
	{
		x=read();
		k|=k<<x;
	} 
	for (int i=1;i<=4000000;i++)
	{
		if (k[i]) a[++p]=i;
	} 
	cout<<a[(p+1)/2];
} 

Measured memory_bytes: 11520
import           Control.Applicative
import           Control.Monad
import           Data.List

main :: IO ()
main = do
  n <- getLine
  a <- map read . words <$> getLine
  putStr $ unlines $ map (unwords . map show) $ insertSort [] a []
    where
      insertSort::[Int]->[Int]->[[Int]]->[[Int]]
      insertSort _ [] steps = steps
      insertSort sorted (x:xs) steps = insertSort inserted xs (steps ++ [inserted ++ xs])
        where
          insert [] = [x]
          insert (y:ys)
            | x < y = x : y : ys
            | otherwise = y : insert ys
          inserted = insert sorted


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

class Program
{
    static void Main(string[] args) {
        int[] s = Console.ReadLine().Split().Select(int.Parse).ToArray();
        var list = new SortedSet<int>();
        for (int i = 0; i < s[2]; i ++) {
            list.Add(s[0]+i);
            list.Add(s[1]-i);
            if (s[0]+i >= s[1]-i) break;
        }
        foreach (int i in list) Console.WriteLine(i);
    }
}

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

template<typename T_char>
T_char ToUpper(T_char cX){return toupper(cX);}

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

  int s1, s2;

  s1 = stoi(s.substr(0,2));
  s2 = stoi(s.substr(2,2));
  if(1<=s1 && s1<=12){
    if(1<=s2 && s2<=12) cout << "AMBIGUOUS" << endl;
    else cout << "MMYY" << endl;
  }
  else{
    if(1<=s2 && s2<=12) cout << "YYMM" << endl;
    else cout << "NA" << endl;
  }

}

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

int main()
{ char a[100];

int i, j, count=0,n;
cin>>a; 
n=strlen(a);
for(i=0,j=n-1;i<j;j--,i++)
{
if(a[i]!=a[j]){
count++;
}
}cout<<count; 

return 0;
}

Measured memory_bytes: 256
using System;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');

            int A = int.Parse(input[0]);
            int B = int.Parse(input[1]);
            int C = int.Parse(input[2]);
            int K = int.Parse(input[3]);

            int ans = 0;
            int sum = K;
            if (A > sum)
            {
                ans += sum;
                Console.WriteLine(ans);
                return;
            }

            ans += A;
            sum -= A;

            if (B > sum)
            {
                Console.WriteLine(ans);
                return;
            }
            
            sum -= B;
            
            ans -= sum;
            Console.WriteLine(ans);

        }
    }
}

Measured memory_bytes: 27516
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main {

  public static void main(String[] args) {
    FastScanner sc = new FastScanner();

    String S = sc.next();
    String T = sc.next();

    String ans = "No";
    if (T.startsWith(S)) {
      ans = "Yes";
    }

    System.out.println(ans);

  }
}

class FastScanner {
  private final InputStream in = System.in;
  private final byte[] buffer = new byte[1024];
  private int ptr = 0;
  private int buflen = 0;

  private boolean hasNextByte() {
    if (ptr < buflen) {
      return true;
    } else {
      ptr = 0;
      try {
        buflen = in.read(buffer);
      } catch (IOException e) {
        e.printStackTrace();
      }
      if (buflen <= 0) {
        return false;
      }
    }
    return true;
  }

  private int readByte() {
    if (hasNextByte()) {
      return buffer[ptr++];
    } else {
      return -1;
    }
  }

  private static boolean isPrintableChar(int c) {
    return 33 <= c && c <= 126;
  }

  private void skipUnprintable() {
    while (hasNextByte() && !isPrintableChar(buffer[ptr])) {
      ptr++;
    }
  }

  public boolean hasNext() {
    skipUnprintable();
    return hasNextByte();
  }

  public String next() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    StringBuilder sb = new StringBuilder();
    int b = readByte();
    while (isPrintableChar(b)) {
      sb.appendCodePoint(b);
      b = readByte();
    }
    return sb.toString();
  }

  public int nextInt() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    int n = 0;
    boolean minus = false;
    int b = readByte();
    if (b == '-') {
      minus = true;
      b = readByte();
    }
    if (b < '0' || '9' < b) {
      throw new NumberFormatException();
    }
    while (true) {
      if ('0' <= b && b <= '9') {
        n *= 10;
        n += b - '0';
      } else if (b == -1 || !isPrintableChar(b)) {
        return minus ? -n : n;
      } else {
        throw new NumberFormatException();
      }
      b = readByte();
    }
  }

  public long nextLong() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    long n = 0;
    boolean minus = false;
    int b = readByte();
    if (b == '-') {
      minus = true;
      b = readByte();
    }
    if (b < '0' || '9' < b) {
      throw new NumberFormatException();
    }
    while (true) {
      if ('0' <= b && b <= '9') {
        n *= 10;
        n += b - '0';
      } else if (b == -1 || !isPrintableChar(b)) {
        return minus ? -n : n;
      } else {
        throw new NumberFormatException();
      }
      b = readByte();
    }
  }
}

Measured memory_bytes: 25344
#include <stdio.h>
#include <stdlib.h>

#include <iostream>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <stdint.h>
#include <string.h>

//#define _USE_MATH_DEFINES
//#include <math.h>

#include <vector>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <deque>
#include <string>

#include <algorithm>
#include <functional>
#include <bitset>
#include <functional>
#include <chrono>
#include <random>
#define sqr(x) (x) * (x)

typedef unsigned int u32;
typedef int i32;
typedef unsigned long long int u64;
typedef int long long i64;
typedef uint16_t u16;
typedef int16_t i16;
typedef uint8_t u8;
typedef int8_t i8;

using namespace std;
using namespace std::chrono;

const i64 mod = 1000000007ll;
const i64 smod = 998244353ll;
const i64 inf = 1000000007; // 10000000000000007ll;

const double eps = 1e-8;

const i64 MAXN = 1'000'000 + 6;

i64 n;
i64 a[MAXN] = { 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51 };

int main(int argc, char* argv[]) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout.precision(15); cout.setf(ios::fixed);

    i64 a, b, c;
    cin >> a >> b >> c;

    i64 q = 4ll * a * b;
    cerr << q << endl;
    bool R = 4ll * a * b < sqr(c - a - b) && (c - a - b) > 0;
    
    if (R) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }

    return 0;
}

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

int main() {
  int a, b, c, k;
  cin >> a >> b >> c >> k;
  if(k - a <= 0) cout << k << endl;
  else if(k - a - b <= 0) cout << a << endl;
  else cout << 2 * a + b - k << endl;  
}

Measured memory_bytes: 3628
#include<iostream>
#include<cstring>
#include<cstdio>
#define N 100010
using namespace std;
int a[N],b[N];
int main()
{
	int n;scanf("%d",&n);int ans=0;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	for(int i=1;i<=n;i++) a[i]+=a[i-1];
	for(int i=n;i>=1;i--) b[i]+=b[i+1];
	for(int i=1;i<=n;i++) ans=max(ans,a[i]+b[i]);
	printf("%d\n",ans);return 0;
}

Measured memory_bytes: 256
N = int(input())
m, a, r, c, h = 0, 0, 0, 0, 0
for _ in range(N):
	S = input()
	if S[0] == "M":
		m += 1
	elif S[0] == "A":
		a += 1
	elif S[0] == "R":
		r += 1
	elif S[0] == "C":
		c += 1
	elif S[0] == "H":
		h += 1
print(m * a * r + m * a * c + m * a * h + m * r * c + m * r * h + m * c * h + a * r * c + a * r * h + a * c * h + r * c * h)


Measured memory_bytes: 3064
#include<stdio.h>

static const int MAX=500;
static const int INFTY=(1<<21);

int main(){
  int n,i,j,e,sum;
  int M[MAX][MAX];
  int u,v;
  int minv;
  int d[MAX];
  int p[MAX];
  int vis[MAX];

  scanf("%d",&n);

  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      scanf("%d",&e);
      M[i][j]=(e==-1)?INFTY:e;
    }
  }

  for(i=0;i<n;i++){
    d[i]=INFTY;
    p[i]=-1;
    vis[i]=0;
  }

  d[0]=0;

  while(1){
    minv=INFTY;
    u=-1;
    for(i=0;i<n;i++){
      if(minv>d[i] && !vis[i]){
	u=i;
	minv=d[i];
      }
    }
    if(u==-1)break;
    vis[u]=1;
    for(v=0;v<n;v++){
      if(!vis[v] && M[u][v] != INFTY){
	if(d[v]>M[u][v]){
	  d[v]=M[u][v];
	  p[v]=u;
	}
      }
    }
  }
  sum=0;

  for(i=0;i<n;i++){
    if(p[i]!=-1)sum+=M[i][p[i]];
  }

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

  return 0;
}



Measured memory_bytes: 2032
import sys
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n,m=MAP()
h=LIST()
g=[[] for i in range(n)]
for i in range(m):
    a,b=MAP()
    g[a-1].append(b-1)
    g[b-1].append(a-1)

ans=0

for i in range(n):
    my_bool=True
    for j in g[i]:
        if h[i]<=h[j]:
            my_bool=False
    if my_bool:
        ans+=1
print(ans)

Measured memory_bytes: 89896
#include <algorithm>
#include <array>
#include <bitset>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stdio.h>
#include <string>
#include <vector>

#define rep(i,n) for (int i = 0; i < (n); ++i)
#define M_PI 3.14159265358979
#define deg_to_rad(deg) (((deg)/360)*2*M_PI)
#define rad_to_deg(rad) (((rad)/2/M_PI)*360)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using LP = pair<ll, ll>;
const double PI = 3.1415926535897932;

/* a と b の最大公約数を返す関数 */
long long GCD(long long a, long long b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}


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

	int ans = 1;
	for (int i = 1; i < N; ++i) {
		if (S[i] != S[i - 1]) {
			ans += 1;
		}
	}

	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3736
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i, a, b) for (int i = (a); i < int(b); ++i)
#define RFOR(i, a, b) for (int i = (b)-1; i >= int(a); --i)
#define rep(i, n) FOR(i, 0, n)
#define rep1(i, n) FOR(i, 1, int(n) + 1)
#define rrep(i, n) RFOR(i, 0, n)
#define rrep1(i, n) RFOR(i, 1, int(n) + 1)
#define all(c) begin(c), end(c)
const int MOD = 1000000007;

template <typename T>
void __dump__(std::ostream &os, const T &first) {
    os << first;
}
template <typename First, typename... Rest>
void __dump__(std::ostream &os, const First &first, const Rest &... rest) {
    os << first << ", ";
    __dump__(os, rest...);
}
#define dump(...)                                         \
    do {                                                  \
        std::ostringstream os;                            \
        os << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; \
        __dump__(os, __VA_ARGS__);                        \
        std::cerr << os.str() << std::endl;               \
    } while (0)

int main() {
    ll n, a, b;
    while (cin >> n >> a >> b && a != -1) {
        ll x = (n-1) * a + b;
        ll y = a + (n-1) * b;
        cout << max(0LL, y - x + 1) << endl;
    }
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = sc.nextInt();
        }
        
        long count = 0;
        for (int i = 0; i < n; i++) {
            if (array[i] > 1) {
                count += array[i] / 2;
                array[i] -= array[i] / 2 * 2;
                i--;
            } else if (array[i] == 1) {
                if (i == n - 1) break;
                if (array[i + 1] > 0) {
                    array[i]--;
                    array[i + 1]--;
                    count++;
                }
            }
        }
        
        System.out.println(count);
    }
}


Measured memory_bytes: 50428
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
class Program
{
    static void Main(string[] args)
    {
            // 入力
            string[] sS = Console.ReadLine().Trim().Split(' ');

            System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
            sw.Start();

            // 解析
            string sOut = "ABC" + sS[0];

            //出力
            Console.WriteLine("{0}", sOut.ToString().Trim());

            sw.Stop();
#if DEBUG
            Console.WriteLine();
            Console.WriteLine("{0}", sw.Elapsed.ToString());
            Console.WriteLine("続行するには何かキーを押してください．．．");
            Console.ReadKey();
#endif
    }
}


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

int main()
{
	ll n;
	cin>>n;
	ll arr[n];
	//ll b[n];
	ll sum=0;
	ll minsofar = INT_MAX;
	for(ll i=0;i<n;i++)
	{
		cin>>arr[i];
		if(arr[i]<=minsofar)
		{
			sum ++;
			minsofar = arr[i];
		}
		
	}
	
	
	
	cout<<sum;
}


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

using namespace std;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
constexpr int MOD = 1000000007;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
constexpr int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
constexpr int dy[] = {0, -1, 0, 1, 1, -1, -1, 1};

void solve() {
    int R;
    cin >> R;
    if (R < 1200) {
        cout << "ABC" << endl;
    } else if (R < 2800) {
        cout << "ARC" << endl;
    } else {
        cout << "AGC" << endl;
    }
}

int main() {
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    solve();
    return 0;
}

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

using namespace std;
typedef long long LL;

LL p = 998244353;

LL pow3(int n) { return n ? (pow3(n-1)*3)%p : 1ll; }

int main(void) {
  int n;
  cin >> n;
  vector<int> a(n);
  for(int &x: a) cin >> x;
  int sum = 0;
  for(int x: a) sum += x;
  vector<LL> pat(sum+1,0),pat2(sum+1,0);
  pat[0]=1ll;
  pat2[0]=1ll;
  for(int x: a) for(int i=sum-x;i>=0;--i) {
    pat[i+x] = (pat[i]+pat[i+x])%p;
    pat[i] = (pat[i]+pat[i])%p;
    pat2[i+x] = (pat2[i]+pat2[i+x])%p;
  }
  LL answer = pow3(n);
  for(int i=0;i<=sum;++i) if(i*2>=sum)answer -= pat[i]*3;
  for(int i=0;i<=sum;++i) if(i*2==sum)answer += pat2[i]*3;
  answer = (answer%p+p)%p;
  cout << answer << endl;
  return 0;
}


Measured memory_bytes: 1664
import java.io.*;
import java.util.*;
import static java.lang.System.*;
import static java.lang.Math.*;

public class Main
{
	public static void main(String []args)throws IOException
	{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		String []s=br.readLine().split(" ");
		long A = Long.parseLong(s[0]);
		long B = Long.parseLong(s[1]);
		long K = Long.parseLong(s[2]);
		long aoki=B,taka=A;
		
		if(K<=A)
			taka=A-K;
		else if(K<A+B) //Atcoder Editorial's solution
		{
			taka=0;
			aoki=B-(K-A);
		}
		else
		{
			aoki=0;
			taka=0;
		}
		
		out.println(taka+" "+aoki);
	
	}
}




Measured memory_bytes: 22484
import sys
import math
input = lambda: sys.stdin.readline().rstrip()

INF = 100100100100100


def solve():
    N = int(input())
    n_m = int(math.sqrt(N) + 1)

    r = INF
    for i in range(1, n_m + 1):
        if N % i == 0:
            r = min(r, i + N // i)

    print(r - 2)


if __name__ == '__main__':
    solve()


Measured memory_bytes: 38640
use std::fmt::Debug;
use std::io::stdin;
use std::iter::Iterator;
use std::str::FromStr;

fn readln<T>() -> Vec<T>
where
	T: FromStr,
	<T as FromStr>::Err: Debug,
{
	let mut s = String::new();
	stdin().read_line(&mut s).unwrap();
	s.trim()
		.split_whitespace()
		.map(|c| T::from_str(c).unwrap())
		.collect()
}

fn main() {
	let _n: Vec<u32> = readln();
	let a: Vec<u32> = readln();
	println!(
		"{:?}",
		a.into_iter().fold(0, |mut sum, mut v| {
			while v & 0x1 == 0 {
				v >>= 1;
				sum += 1
			}
			sum
		})
	);
}


Measured memory_bytes: 4352
import sys
input = sys.stdin.readline

def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def unite(x,y):
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True
    
def same(x,y):
    return find(x) == find(y)

def size(x):
    return -par[find(x)]

n,m,k = map(int,input().split())
ab = [list(map(int,input().split()))for i in range(m)]
cd = [list(map(int,input().split()))for i in range(k)]

friend = [0]*(n+1)
for i in range(m):
    friend[ab[i][1]] += 1
    friend[ab[i][0]] += 1

par = [-1]*(n+1)
for i in range(m):
    unite(ab[i][0],ab[i][1])

block = [0]*(n+1)
for i in range(k):
    if same(cd[i][0],cd[i][1]):
        block[cd[i][0]] += 1
        block[cd[i][1]] += 1
    #block[cd[i][0]].append(cd[i][1])
    #block[cd[i][1]].append(cd[i][0])



for i in range(1,n+1):
    print(size(i)-friend[i]-block[i]-1,end = " ")


Measured memory_bytes: 111708
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <queue>
#include <functional>

#define mp make_pair
#define pb push_back


typedef long long ll;
typedef long long llong;
typedef long double ld;

using namespace std;

#ifndef LOCAL
#define cerr _cer
struct _cert
{
    template <typename T> _cert& operator << (T) { return *this; }
};
_cert _cer;
#endif

template <typename T> void dprint(T begin, T end) {
    for (auto i = begin; i != end; i++) {
		cerr << (*i) << " ";
    }
    cerr << "\n";
}
int n;
int a[120000];

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    int cnt = 1;
    int fl = 0;
    for (int i = 1; i < n; ++i) {
        int nw = 0;
        if (a[i] < a[i - 1])
            nw = -1;
        else if (a[i] > a[i - 1])
            nw = 1;
        if (fl == 0) {
            fl = nw;
            continue;
        }
        if (nw == 0 || nw == fl)
            continue;
        fl = 0;
        ++cnt;
    }
    cout << cnt << "\n";
	return 0;
}




Measured memory_bytes: 640
import java.util.*;

class Main{
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] p = new int[n];
        for(int i=0;i<n;i++){
            p[i] = sc.nextInt();
        }

        long[] sum = new long[n-k+1];
        for(int i=0;i<k;i++){
            sum[0]+=p[i];
        }

        for(int i=1;i<n-k+1;i++){
            sum[i] = sum[i-1]-p[i-1]+p[i+k-1];
        }

        float mx = sum[0];
        for(int i=0;i<n-k+1;i++){
            mx = Math.max(mx, sum[i]);
        }

        System.out.println(mx/2f + 0.5f*k);
    }
}


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

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

#define INF LLONG_MAX

#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) {
  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;
}

// 円周率
// M_PI

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

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

// 

signed main() {
  int n, h;
  cin >> n >> h;
  
  vector<int> a(n);
  vector<int> b(n);

  int aMax = 0;
  for(int i=0;i<n;i++){
    cin >> a[i] >> b[i];
    aMax = max(aMax,a[i]);
  }
  sort(b.begin(),b.end(),greater<int>());
  
  int count = 0;
  for(int i=0;i<n;i++){
    if(h<=0) break;
    if(b[i]>aMax){
      h -= b[i];
      count++;
    }
    if(i==n-1 || aMax>=b[i]){
      count += (h+aMax-1)/aMax;
      h = 0;
    }
  }

  cout << count << endl;
  
  return 0;
}



Measured memory_bytes: 3948
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.Scanner;

/**
 * Created 2017/06/11.
 */
public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    
    
    //?????¶????????¨??????????????????
    LinkedHashMap<String,LinkedHashSet<Integer>> dr = new LinkedHashMap<>();
    String s = "S";
    String h = "H";
    String c = "C";
    String d = "D";
    
    dr.put(s,rankmake());
    dr.put(h,rankmake());
    dr.put(c,rankmake());
    dr.put(d,rankmake());
    
    //System.out.println(dr); 
    //??\????????\?????¨????????????

    int n = sc.nextInt();
    for(int i = 0; i < n; i++) {
      String d_input = sc.next();
      int r_input = sc.nextInt();
      dr.get(d_input).remove(r_input);
    }
    //??¨?????????????????????
    //System.out.println(dr); //????????????
    
    //?????????????????¨??????hashset??????????¨??????????????????????for?????§??¨??¨??¨????????????????????§
    for(String key : dr.keySet()){
      LinkedHashSet<Integer> r_end =dr.get(key);
      for(int i : r_end){
        System.out.println(key + " " + i);
      }
    }

  }
  public static LinkedHashSet<Integer> rankmake() {
    LinkedHashSet<Integer> rank = new LinkedHashSet<>();
    for(int i = 1;i <=13;i++){
      rank.add(i);
    }
    return rank;
  }
}

Measured memory_bytes: 26292
#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
struct tk
{
	ll l,r;
	bool operator<(const tk&y)const{return r<y.r||(r==y.r&&l<y.l);}
}h;
ll rev,n,i,x[300005],j,seq[300005],tot=0,y[300005],p,fac[300005],invfac[300005],cnt=0,l[300005],r[300005],vis[300005],pos,ans;
const ll mod=998244353;
map<tk,ll> mp;
map<tk,ll>::iterator it;
ll pow(ll a,ll b)
{
	ll ans=1;
	while(b)
	{
		if(b&1)ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
int main()
{
	scanf("%lld",&n);
	fac[0]=ans=1;
	for(i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
	invfac[n]=pow(fac[n],mod-2);
	for(i=n-1;i>=0;i--)invfac[i]=invfac[i+1]*(i+1)%mod;
	for(i=1;i<=n;i++)scanf("%lld",&x[i]);
	for(i=1;i<=n;i++)if(x[i]>1)break;
	if(i>n)
	{
		printf("%lld",fac[n]);
		return 0;
	}
	x[0]=x[n];
	for(i=1;i<=n;i++)
	{
		if(x[i]!=x[i-1])
		{
			vis[x[i]]++;
			if(x[i]==1)l[x[i]]=i;
		}
		if(x[i]==1)cnt++;
		if(vis[x[i]]>1)
		{
			printf("0\n");
			return 0;
		}
	}
	mp[(tk){1,n-1}]=1;
	j=1;pos=(l[1]==n)?1:l[1]+1;
	p=cnt-1;
	while(j<n)
	{
		y[j++]=x[pos];
		pos=(pos==n)?1:pos+1;
	}
	cnt=0;
	for(i=1;i<=n;i++)
	{
		if(!l[y[i]])l[y[i]]=i;
		r[y[i]]=i;
	}
	for(i=2;i<=n;i++)
	{
		if(!l[i])seq[++tot]=cnt;
		else
		{
			it=mp.lower_bound((tk){-1,r[i]});
			h=it->first;
			if(r[i]-l[i]+1>p+1)
			{
				printf("0\n");
				return 0;
			}
			if(l[i]>h.l+p)
			{
				mp.erase(h);
				mp[(tk){h.l,l[i]-1}]=1;
				if(r[i]<h.r)
				{
					if(r[i]-l[i]+1!=p+1)
					{
						printf("0\n");
						return 0;
					}
					mp[(tk){l[i]+1,h.r}]=1;
				} 
				else cnt+=h.r-l[i];				
			}
			else
			{
				if(r[i]<h.r)
				{
					cnt+=r[i]-p-h.l;
					mp.erase(h);
					mp[(tk){r[i]-p+1,h.r}]=1;
				}
				else
				{
					ans=ans*(p+1-r[i]+l[i])%mod;
					cnt+=h.r-h.l;
					mp.erase(h);
				}
			}
		}
	}
	for(i=1;i<=tot;i++)
	{
		if(seq[i]-i+1>0)ans=ans*(seq[i]-i+1)%mod;
		else
		{
			printf("0\n");
			return 0;
		}
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 21760
//
//  header_useful.h
//  c++_acm
//
//  Created by 李弘辰 on 2019/7/23.
//  Copyright © 2019 李弘辰. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <vector>
#include <list>
#include <set>
#include <utility> // pair
#include <map>
#include <iostream>
#include <sstream>
#include <algorithm> // sort
#include <string>
#include <stack>
#include <queue>
#include <fstream>
#include <bitset>

using namespace std;

#define ll long long
#define uchar unsigned char
#define ushort unsigned short
#define uint unsigned int
#define ulong unsigned long
#define ull unsigned long long

#define INT_INF 0x7fffffff

#define pi acos(-1)

#define mx(a,b) (a) > (b) ? (a) : (b)
#define mn(a,b) (a) < (b) ? (a) : (b)
#define mem(a,b) memset(a,b,sizeof(a))
#define fre(a) freopen(a,"r",stdin)

#define cio ios::sync_with_stdio(false); // Do not use it with "scanf" and other c input!

#define itn int
#define nit int
#define inr int
#define mian main
#define ednl endl
#define fro for
#define fir for
#define reutrn return
#define retunr return
#define reutnr return


/* header_useful_h */


int n,m,q;
int mx = -1;

struct Score {
    int a,b,c,d;
} arr[100];

void dfs(int k,int d,vector<int> A) {
    if (d == n) {
        int s = 0;
        for (int j = 0;j < q;j ++) {
            if (A[arr[j].b - 1] - A[arr[j].a - 1] == arr[j].c) {
                s += arr[j].d;
            }
        }
        mx = max(mx,s);
        return;
    }
    for (int i = k;i <= m;i ++) {
        A.push_back(i);
        dfs(i,d + 1,A);
        A.erase(A.end() - 1);
    }
}

int main()
{
    scanf("%d%d%d",&n,&m,&q);
    
    int a,b,c,d;
    for (int i = 0;i < q;i ++) {
        scanf("%d%d%d%d",&a,&b,&c,&d);
        arr[i].a = a;
        arr[i].b = b;
        arr[i].c = c;
        arr[i].d = d;
    }
    dfs(1,0,vector<int>());
    printf("%d\n",mx);
    return 0;
}


Measured memory_bytes: 3232
import numpy as np
import math
N, H = map(int, input().split())
a_list = []
b_list = []
for _ in range(N):
    a, b = map(int, input().split())
    a_list.append(a)
    b_list.append(b)

a_max = max(a_list)
b_list.sort()
def judge(H, n, a_max, b_list):
    b_copy = b_list.copy()
    count = 0
    while H > 0:
        if len(b_copy) == 0:
            count += math.ceil(H / a_max)
            break
        else:
            b_max = b_copy.pop()
            if a_max > b_max:
                count += math.ceil(H / a_max)
                break
            else:
                H -= b_max
                count += 1
    if count <= n:
        return True
    return False

right = 10 ** 9
left = 1
while right != left:
    
    mid = (left + right) // 2
    if judge(H, mid, a_max, b_list):
        right = mid
    else:
        left = mid + 1

print(left)

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

#define _ << " _ " <<
#define TRACE(x) cout << #x << " = " << x << endl

const int MaxN = 1e5 + 10; 
int n, m;
int p[MaxN];
vector<int> e[MaxN];
bool vis[MaxN];
set<int> pos, num;

void dfs(int x) {
    pos.insert(x);
    num.insert(p[x]);

    for (int y : e[x]) {
        if (!vis[y]) {
            vis[y] = true;
            dfs(y);
        }
    }
}


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

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
    }

    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }

    int sol = 0;

    for (int i = 1; i <= n; i++) {
        if (vis[i]) continue;
        vis[i] = true;
        pos.clear();
        num.clear();
        dfs(i);

        for (int x : pos) {
            if (num.find(x) != num.end()) sol++;
        }
    }

    cout << sol;

    return 0;
}


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

using namespace std;

int solve(){
	string c, s;
	map<string, bool> mp;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> c >> s;
		if (c == "insert") mp[s] = true;
		else {
			if (mp[s]) cout << "yes" << endl;
			else cout << "no" << endl;
		}
	}
}

signed main(){
	solve();
}

Measured memory_bytes: 52524
#include <iostream>
#define nmax 1000000
#define mod 1000000007
using std::cin;
using std::cout;
int n, f[nmax+nmax+3], fsum[nmax+nmax+3];
int qmod(int x)
{
    return (x < 0) ? x + mod : ((x < mod) ? x : x - mod);
}
int main()
{
    std::ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    if(n == 1){
      cout << 1;
      return 0;
    }
    if(n == 2){
      cout << 4;
      return 0;
    }
    f[n] = n;
    f[n - 1] = (long long) n * n % mod;
    for(int i = n + n + 1; i > n; --i)
      f[i] = 1;
    fsum[n + n + 1] = 1;
    for(int i = n + n; i > n - 2; --i)
      fsum[i] = qmod(fsum[i + 1] + f[i]);
    for(int i = n - 2; i > 0; --i){
      f[i] = qmod(qmod(f[i + 1] + qmod(fsum[i + 3] - fsum[i + n + 2])) + (long long) (n - 1) * (n - 1) % mod);
      fsum[i] = qmod(f[i] + fsum[i + 1]);
    }
    cout << f[1];
    return 0;
}


Measured memory_bytes: 15872
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef long long ll;
typedef char keytype;

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

/* a[0], ..., a[n-1] の数の最大公約数 */
int ngcd(int n, int a[])
{
    int i, d;

    d = a[0];
    for (i = 1; i < n && d != 1; i++)
        d = gcd(a[i], d);
    return d;
}

void quicksort(keytype a[], int first, int last)
{
    int i, j;
    keytype x, t;

    x = a[(first + last) / 2];
    i = first;  j = last;
    for ( ; ; ) {
        while (a[i] < x) i++;
        while (x < a[j]) j--;
        if (i >= j) break;
        t = a[i];  a[i] = a[j];  a[j] = t;
        i++;  j--;
    }
    if (first  < i - 1) quicksort(a, first , i - 1);
    if (j + 1 < last) quicksort(a, j + 1, last);
}

int is_prime(int x){
    if(x <= 1) return 0;
    for(int i = 2; i * i <= x; i++){
        if(x % i == 0) return 0;
    }
    return 1;
}

int is_substr(char s[], char t[], int i){
    int flag = 1;

    if(s[i] == '\0') flag = 0;

    for(int j = 0; j < strlen(t); ++j, ++i){
        if(s[i] != t[j]){
            flag = 0;
            break;
        }
    }
    return flag;
}

// factor list, number of factors, natural number
void factorize(int ftr[], int *num, int n){
    int a = 2, cnt = 0;

    while(n >= a){
        if(n % a == 0){
            n = n / a;
            ftr[cnt++] = a;
        }else{
            a++;
        }
    }
    *num = cnt;
}

//#define N 5
//int p[N + 1];
int nextperm(int p[], int N)  /* 辞書式順序で次の順列 */
{
    int i, j, t;

    i = N - 1;
    p[0] = 0;  /* 番人 */
    while (p[i] >= p[i + 1]) i--;
    if (i == 0) return 0;  /* 完了 */
    j = N;
    while (p[i] >= p[j]) j--;
    t = p[i];  p[i] = p[j];  p[j] = t;
    i++;  j = N;
    while (i < j) {
        t = p[i];  p[i] = p[j];  p[j] = t;  i++;  j--;
    }
    return 1;  /* 未了 */
}

void comb(int size1, int size2, int v[size1][size2]){
  for(int i = 0; i < size1; i++){
    v[i][0] = 1;
    v[i][i] = 1;
  }
  for(int k = 1; k < size1; k++){
    for(int j = 1; j < k; j++){
      v[k][j] = (v[k-1][j-1] + v[k-1][j]);
    }
  }
}

int abs_val(int a, int b){
    if(a > b) return a - b;
    else return b - a;
}

const int inf = 1012345678;
int main(){
    int h, w;
    char a[105][105];

    scanf("%d %d", &h, &w);
    for(int i = 0; i < h; ++i){
        scanf("%s", a[i]);
    }

    for(int i = 0; i < w + 2; ++i){
        printf("#");
    }
    puts("");
    for(int i = 0; i < h; ++i){
        printf("#");
        printf("%s",a[i]);
        printf("#\n");
    }
    for(int i = 0; i < w + 2; ++i){
        printf("#");
    }
    puts("");

    return 0;
}


Measured memory_bytes: 1744
n = int(input())
a = list(map(int, input().split()))
a=sorted(a)
length=len(a)

previous=1
count=0
for j in a+[n+1]:
    if j==previous:
        count+=1
    else:
        print(count)
        count=1
        for _ in range(j-previous-1):
            print(0)
        previous=j

Measured memory_bytes: 32224
/*input
10
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#pragma GCC optimize("unroll-loops,no-stack-protector")
//order_of_key #of elements less than x
// find_by_order kth element
using ll = unsigned long long;
using ld = long double;
using pii = pair<ll,ll>;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
#define REP1(i,n) for(int i=1;i<=n;i++)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
const ll INF64=1e18;
const int INF=1e6+1;
const ll MOD=1e9+7;
const ld PI=acos(-1);
const ld eps=1e-9;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
ll mult(ll a,ll b){
    return ((a%MOD)*(b%MOD))%MOD;
}
ll mypow(ll a,ll b){
    if(b<=0) return 1;
    ll res=1LL;
    while(b){
        if(b&1) res=mult(res,a);
        a=mult(a,a);
        b>>=1;
    }
    return res;
}
const ll maxn=2e5+5;
const ll maxlg=__lg(maxn)+2;
vector<string> v;
int n;
void rec(int u,string a){
    if(u==n){
        v.pb(a);
        return;
    }
    int mx=0;
    REP(i,sz(a)) MXTO(mx,a[i]-'a');
    REP(i,mx+2){
        string b=a;
        b+=i+'a';
        rec(u+1,b);
    }

}
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    cin>>n;
    rec(1,"a");
    sort(ALL(v));
    for(auto x:v) cout<<x<<'\n';
}

Measured memory_bytes: 9716
a, b, c = sorted(map(int, input().split()))
res = (c - a) // 2 + (c - b) // 2
a = (c - a) % 2
b = (c - b) % 2
if a == 0 and b == 0:
    pass
elif a == 1 and b == 1:
    res += 1
else:
    res += 2
print(res)

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

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

    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];

    sort(a.begin(), a.end(), greater<int>());

    ll res = a[0];
    int l = 1;
    int idx = 1;
    while(l != n-1){
        res += a[idx];
        l++;
        if(l == n-1) break;
        res += a[idx];
        l++;
        ++idx;
    }

    cout << res << endl;

    return 0;
}

Measured memory_bytes: 3940
#include <cstdio>
#include <cmath>
using namespace std;
int bxp(int base, int exp)
{
    int ans = 1;
    while(exp)
    {
        if(exp&1)
            ans*=base;
        base*=base;
        exp>>=1;
    }
    return ans;
}
int main()
{
    int n , m, ans;
    scanf("%d %d", &n, &m);

    if(m==100)
        m = 101;
    ans = m*bxp(100, n);
    printf("%d\n", ans);

}


Measured memory_bytes: 128
package main

import (
	"fmt"
)

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

func main() {
	var a [3]int
	fmt.Scan(&a[0], &a[1], &a[2])
	ans := -1

	for i := 0; i < 3; i++ {
		for j := 0; j < 3; j++ {
			if j == i {
				continue
			}
			for k := 0; k < 3; k++ {
				if k == i || k == j {
					continue
				}
				ans = max(ans, a[i]*10+a[j]+a[k])
			}
		}
	}
	fmt.Println(ans)

}


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

#define ALL(v) v.begin(), v.end()
#define V vector
#define P pair
using ll = long long;
using ld = long double;
const int MOD = 1e9+7;


int main() {
    int n; cin >> n;
    V<int> a(n + 1);
    a[0] = 0;
    for(int i = 1; i <= n; i++) cin >> a[i];
    a.push_back(0);

    V<int> sub(n + 1);
    for(int i = 0; i <= n; i++){
        sub[i] = abs(a[i + 1] - a[i]);
    }

    int sum = accumulate(ALL(sub), 0);

    for(int i = 1; i <= n; i++){
        int tmp1 = sub[i] + sub[i - 1];
        int tmp2 = abs(a[i + 1] - a[i - 1]);
        cout << sum - tmp1 + tmp2 << endl;
    }

    return 0;
}


Measured memory_bytes: 4016