akhauriyash/Code-Regression huggingface dataset:
import scala.io.Source
import scala.math._

object Main{
  def main(args: Array[String]){
    val lines = for{
      in <- Source.stdin.getLines.toList
    } yield in

    val data =  lines.head.split(" ").toList.map(_.toInt)
    println(data(0) * data(1) * sin(data(2) * Pi / 180) / 2)
    println(data(0) + data(1) + sqrt(pow(data(0), 2) + pow(data(1), 2) - 2 * data(0) * data(1) * cos(data(2) * Pi /180)))
    println(data(1) * sin(data(2) * Pi / 180))
  }
}

Measured memory_bytes: 43988
#include<iostream>
#include<string>
using namespace std;
int main(){
  string s;
  int w;
  cin >> s >> w;

  int n = s.length();

  for(int i=0; i<n; i++){
    if(i%w==0){
    cout << s[i];
    }
  }
  return 0;
}

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

int main(void){
   string S;
   cin>>S;
   int w;
   cin>>w;
   string ans="";
   for(int i=0;i<S.size();i+=w){
      ans+=S[i];
   }
   cout<<ans<<endl;
   return 0;
}


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

int main(){
    int n, t, a; cin >> n >> t >> a;
    vector<int> h(n);
    double min_diff = 1LL << 60;
    int min_index = -1;
    rep(i,n){
        cin >> h[i];
        double diff = abs(a - (t - 0.006 * h[i]));
        if(diff < min_diff) {
            min_diff = diff;
            min_index = i;
        }
    }
    min_index++;
    cout << min_index << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
int main(void){
int n,s[1000];
long long int max=0;
double ave,a=0;
while(1){
scanf("%d",&n);
if(n==0)break;
for(int i=0;i<n;i++){
scanf("%d",&s[i]);
max+=s[i];
}
ave=(double)max/n;
for(int i=0;i<n;i++)a+=pow(s[i]-ave,2);
a=sqrt(a/n);
printf("%f\n",a);
a=0;
max=0;
}
return 0;
}


Measured memory_bytes: 2104
#include <bits/stdc++.h>
#define rep(i,n)for(long long i=0;i<(n);i++)
using namespace std;
using P=pair<long long,long long>;
typedef unsigned long long ull;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
const ll MOD=1e9+7;
const ll INF=1e18;
const double pi=acos(-1);
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};


int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);  
  
  ll n,p;
  cin >> n >> p;
  vector<ll>a(n);
  rep(i,n) cin >> a[i];
  ll even=0,odd=0;
  rep(i,n){
    if(a[i]&1)odd++;
  }
  ll ans=pow(2,n);
  if(p==0 && odd==0) cout << ans << endl;
  if(p==1 && odd==0) cout << 0 << endl;
  if(odd) cout << ans/2 << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long 
#define pll pair<ll,ll>
#define vll vector<pll>
#define vl vector<ll>
#define f first
#define s second
#define N 50000
#define pb push_back
#define mp make_pair
#define MAP map<ll,ll>
#define INF 1000000000
#define mod 1000000007
#define foo(i,a,b) for(ll i=(a);i<=(b);i++)
#define rep(i,a,b) for(ll i=(a);i>=(b);i--)
#define sl set<ll> 
#define sll set<pll>
#define ub upper_bound
#define lb lower_bound
using namespace std;
ll dp[3005][3005];
string lcs(string s,string t,ll m,ll n){
	foo(i,0,n){
		foo(j,0,m){
			if(i==0 or j==0)
				dp[i][j]=0;
			else if(s[i-1]==t[j-1])
				dp[i][j]=max(dp[i-1][j-1]+1,max(dp[i-1][j],dp[i][j-1]));
			else
				dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
		}
	}
	//cout<<dp[n][m];
	string ans="";
	ll i=n,j=m;
	while(i>0 and j>0){
		if(dp[i][j]==dp[i-1][j]) i--;
		else if(dp[i][j]==dp[i][j-1]) j--;
		else{
			ans=s[i-1]+ans;
			i--,j--;
		}
	}
	return ans;
}
int main(){
	fastio;
	string s,t;
	cin>>s;
	cin>>t;
	ll n=s.size();
	ll m=t.size();
	string res=lcs(s,t,m,n);
	cout<<res;
}

Measured memory_bytes: 70784
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i < (n);i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define SCANF(i) int i;scanf("%d",&i)
typedef long long ll;
using namespace std;
using P = pair<int,int>;
const long long INF = 1LL << 60;
const int IINF=100000000;
const int MOD = (int)1e9 + 7;
//約数列挙
vector<long long> divisor(long long n) {
    vector<long long> ret;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i * i != n) ret.push_back(n / i);
        }
    }
    //sort(ret.begin(), ret.end()); // 昇順に並べる
    return ret;
}
vector<int> dx={1,0,-1,0};vector<int> dy={0,-1,0,1};

signed main () {
    string n;cin >> n;
    int div=0;
    REP(i,n.length()){
        int a='0' - n[i];
        div += a;
        div %= 9;
    }
    string ans = (!div) ? "Yes" : "No";
    cout << ans << endl; 

}//

Measured memory_bytes: 3640
#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
typedef pair<int, P> E;
const LL MOD = 1000000007LL;
int a[2001];
LL memo[2001][2];
int N, Z, W;
int solve(int n, int t) {
	if (memo[n][t] != -1) return memo[n][t];
	int ret;
	if (t) {
		ret = 0;
		for (int i = n + 1; i < N; i++) {
			ret = max(ret, solve(i, 0));
		}
		if (n == 0) ret = max(ret, abs(a[N] - W));
		else ret = max(ret, abs(a[N] - a[n]));
	}
	else {
		ret = 1 << 30;
		for (int i = n + 1; i < N; i++) {
			ret = min(ret, solve(i, 1));
		}
		if (n == 0) ret = min(ret, abs(a[N] - Z));
		else ret = min(ret, abs(a[N] - a[n]));
	}
	return memo[n][t] = ret;
}
int main() {
	cin >> N >> Z >> W;
	for (int i = 1; i <= N; i++) cin >> a[i];
	memset(memo, -1, sizeof(memo));
	cout << solve(0, 1) << endl;
}

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

using namespace std;

int main(){

  int t;
  int n;

  for(int i=0;i<4;++i){
	cin>>t>>n;

	if(t==1)
	  cout<<6000*n<<endl;
	else if(t==2)
	  cout<<4000*n<<endl;
	else if(t==3)
	  cout<<3000*n<<endl;
	else if(t==4)
	  cout<<2000*n<<endl;
  }
  
}



Measured memory_bytes: 3100
/*
Author : Devil088
*/
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define sep cout<<"\n";
#define Yes cout<<"Yes\n";
#define No cout<<"No\n";
#define YES cout<<"YES\n";
#define NO cout<<"NO\n";

inline string shift(string s){
	int n = s.length();
	string r = "";
	r+=s[n-1];
	for(int i=0;i<n-1;i++)r+=s[i];
	return r;
}

int main(){
	int n;
	cin>>n;
	
	if(n<1200){
		cout<<"ABC\n";
	}else if(n<2800){
		cout<<"ARC\n";
	}else cout<<"AGC\n";
}
/*
uday
adyu
7 46
45 6
*/



Measured memory_bytes: 256
import sys

while True:
    n = int(sys.stdin.readline().rstrip())
    if n == 0:
        break;
    x = {}
    for i in range(n):
        k,v = sys.stdin.readline().rstrip().split()
        x[k] = v
    y = []
    for i in range(int(sys.stdin.readline().rstrip())):
        a = sys.stdin.readline().rstrip()
        if a in x:
            y.append(x[a])
        else:
            y.append(a)
    print(''.join(y))

Measured memory_bytes: 8608
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;

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

int main()
{
  int N; cin >> N;
  vector<int> array(N);
  REP(i, N){ cin >> array[i]; }

  int count = 0;
  REP(i, N-2){
    if( array[i+1] < array[i+2] && array[i] < array[i+1] ){
      count++; 
    } else if(array[i+1] < array[i] && array[i+2] < array[i+1]){
      count++; 
    }
  }

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

Measured memory_bytes: 256
from pprint import pprint
INF = 1000000
dx = [1, -1, 0,  0]
dy = [0,  0, 1, -1]
# 入力
h, w = map(int, input().split())
maze = []
wallcount = 0
for i in range(h):
    l = list(input())
    maze.append(l)
    wallcount += l.count("#")

# ワーシャルフロイド用に枠を作る。
# 2次元マップしてもいいが面倒なので、１次元にする。[0 - x][0 - y]を[0- x * y]にflattenする
wsmap = lambda a, b: (a * w + b)
dp = []
# 辺がない時はINFを入れのでデフォルト値とする
for i in range(h * w):
    dp.append([INF] * (h * w))



# 迷路ををグラフにする。
goal = -1
dis = 0
import collections
q = collections.deque( [ (0,0,0) ] ) #x,y,d

while len(q) > 0:
    x, y, d = q.popleft()
    if x == w - 1 and y == h - 1:
        goal = d
    for dir in range(len(dx)):
        nx, ny = x + dx[dir], y + dy[dir]
        if -1 < nx and nx < w and -1 < ny and ny < h:
            if nx == w-1 and ny == h - 1:
                goal = d + 1
                break
            if maze[ny][nx] == ".": # そのマスが壁でないなら
                maze[ny][nx] = d
                q.append( (nx, ny, d + 1) )

    if goal != -1:
        break

# これで結果が出たので
import itertools
if goal == -1:
    print(-1)
else:
    needstep = goal
    res = h * w
    res -= wallcount
    res -= needstep + 1
    print(res)


Measured memory_bytes: 90844
#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <cmath>
#include <stack>
#define rep(i,n) for (int i=0; i<(n); ++i)
using namespace std;
using ll = long long int;

template <class T> ostream &operator<<(ostream &os, vector<T> &v) {
  for (auto i = v.begin(); i != v.end(); i++) {
    os << *i << " ";
  }
  return os;
}

ll c[10][1005];
ll INF = 100100100;
int main(){
  ll h, w, k;
  cin>>h>>w>>k;
  vector<string> v(h);
  rep(i,h) cin>>v[i];
  ll ans = INF;
  rep(div,1<<(h-1)) {
    ll g = 0;
    vector<int> id(h);
    rep(i,h) {
      id[i] = g;
      if( div>>i&1) ++g;
    }
    ++g;
    rep(i,g)rep(j,w) c[i][j] = 0;
    rep(i,h)rep(j,w) c[id[i]][j] += (v[i][j]-'0');
    ll num = g-1;
    vector<ll> now(g);
    auto add = [&](int j) {
		 rep(i,g) now[i] += c[i][j];
		 rep(i,g) if(now[i] > k) return false;
		 return true;
	       };
    rep(j,w) {
      if(!add(j)) {
	num++;
	now = vector<ll>(g);
	if(!add(j)){
	  num = INF;
	  break;
	};
      }
    }
    ans = min(ans, num);
  }
  std::cout << ans << std::endl;
  return 0;
}



Measured memory_bytes: 384
macro_rules! get_one {
    ($t:ty) => {{
        let mut line: String = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        line.trim().parse::<$t>().unwrap()
    }};

    ($t:ty; $n:expr) => {
        (0..$n).map(|_| get_one!($t)).collect::<Vec<_>>()
    };
}

fn main() {
    let _ = get_one!(usize);
    let v_s: Vec<char> = get_one!(String).chars().collect();
    let r_pos = pos('R', &v_s);
    let g_pos = pos('G', &v_s);
    let b_pos = pos('B', &v_s);

    let mut except = 0;
    for &r in r_pos.iter() {
        for &g in g_pos.iter() {
            if let Some('B') = v_s.get((2 * r - g) as usize) {
                except += 1;
            }
            if let Some('B') = v_s.get((2 * g - r) as usize) {
                except += 1;
            }
            if (r + g) % 2 == 0 && v_s[((r + g) / 2) as usize] == 'B' {
                except += 1;
            }
        }
    }

    let r_num = r_pos.len();
    let g_num = g_pos.len();
    let b_num = b_pos.len();

    println!("{}", r_num * g_num * b_num - except);
}

fn pos(chr: char, v: &Vec<char>) -> Vec<i32> {
    v.iter().enumerate().filter_map(|(i, &c)| if c == chr {Some(i as i32)} else {None}).collect()
}


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

int main()
{
   	long long n;
   	cin>>n;
   	long long arr[n] = {0};
   	for(int i=0; i<n-1; i++){
   		long long a;
   		cin>>a;
   		arr[a-1] += 1;
   	}

   	for(int i=0; i<n; i++){
   		cout<<arr[i]<<endl;
   	}
    return 0;
}

Measured memory_bytes: 5112
#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;
const ll INF = 1LL << 60;


int main() {
    int n; cin >> n;
    for(int i = 1; i <= n; i++){
        if((int)(i * 1.08) == n){
            cout << i << endl;
            return 0;
        }
    }
    cout << ":(" << endl;

    return 0;
}


Measured memory_bytes: 3608
#include <stdio.h>
#include <iostream>
using namespace std;
int t[110],p[110],x[110];
int main()
{
    int n,m,sum=0,i;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>t[i];
        sum+=t[i];
    }
    cin>>m;
    for(i=0;i<m;i++)
    {
        cin>>p[i]>>x[i];
    }
    for(i=0;i<m;i++)
    {
        cout<<sum-t[p[i]-1]+x[i]<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
N, M = map(int, input().split())

ac = [False] * N
wa = [0] * N
for _ in range(M):
    p, S = input().split()
    p = int(p) - 1
    if S == 'AC':
        ac[p] = True
    else:
        if not ac[p]:
            wa[p] += 1

a = 0
b = 0
for i in range(N):
    if ac[i]:
        a += 1
        b += wa[i]
print(*[a, b])

Measured memory_bytes: 4596
using System;
using System.Collections.Generic;
using System.Text;

namespace AtTest.AGC_B
{
    class _023
    {
        static void Main(string[] args)
        {
            Method(args);
            Console.ReadLine();
        }

        static void Method(string[] args)
        {
            int n = ReadInt();
            var sGrid = new char[n * 2, n * 2];
            for (int i = 0; i < n; i++)
            {
                string s = Read();
                for (int j = 0; j < n; j++)
                {
                    sGrid[i, j] = s[j];
                    sGrid[i, j + n] = s[j];
                    sGrid[i + n, j] = s[j];
                    sGrid[i + n, j  + n] = s[j];
                }
            }
            /*
            for(int i = 0; i < n * 2; i++)
            {
                for(int j = 0; j < n * 2; j++)
                {
                    Console.Write(sGrid[i, j] + " ");
                }
                Console.WriteLine();
            }
            */
            int res = 0;
            int tarCnt = (n * n - n) / 2;
            for (int i = 0; i < n; i++)
            {
                int cnt = 0;
                for (int k = 1; k < n; k++)
                {
                    for (int l = 0; l < k; l++)
                    {
                        if (sGrid[i + k, l] == sGrid[i + l, k])
                        {
                            cnt++;
                        }
                    }
                }
                if (cnt == tarCnt) res += n - i;
            }
            for (int i = 1; i < n; i++)
            {
                int cnt = 0;
                for (int k = 1; k < n; k++)
                {
                    for (int l = 0; l < k; l++)
                    {
                        if (sGrid[k, i + l] == sGrid[l, i + k])
                        {
                            cnt++;
                        }
                    }
                }
                if (cnt == tarCnt) res += n - i;
            }
            Console.WriteLine(res);
        }

        private static string Read() { return Console.ReadLine(); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }
    }
}

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

int main() {
    int a, b, c, d, x;
    cin >> a >> b >> c >> x;
    int res = 0;
    for (int e = 0; e <= a; ++e) {
        for (int f = 0; f <= b; ++f) {
            for (int g = 0; g <= c; ++g) {
                
                int tortal = 500 * e + 100 * f + 50 * g;
                if (x == tortal) res++;
            }
        }
    }
    cout << res << endl;
}

Measured memory_bytes: 3164
#include "bits/stdc++.h"
using namespace std;

#define ASC(vec) vec.begin(), vec.end()		// 昇順ソート 例：sort(ASC(vec));
#define DESC(vec) vec.rbegin(), vec.rend()	// 降順ソート 例:sort(DESC(vec));
#define rep(i, n) for(int i = 0; i < (n); i++)
#define Rep(i, n) for(int i = 1; i < n; i++)
#define REP(i, vec) for(auto i = vec.begin(); i != vec.end(); ++i)

const int mod = 1000000007;
const int inf = (1 << 21);
const long long INF = 1LL << 60;

using ii = pair<int, int>;
using ll = long long;
using vi = vector<int>;
using vd = vector<double>;
using vb = vector<bool>;
using vl = vector<ll>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
using vvb = vector<vector<bool>>;
using vii = vector<pair<int, int>>;
using vll = vector<pair<ll, ll>>;

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; }
template<class T> inline T GCD(T a, T b) { return b ? GCD(b, a % b) : a; }
template<class T> inline T LCM(T a, T b) { return (a + (b - 1)) / b; }

int round_int(int a, int b) { return (a + (b - 1)) / b; }

constexpr array<int, 9> dx = { 0, 1, 0, -1, -1, 1, 1, -1, 0 };
constexpr array<int, 9> dy = { 1, 0, -1, 0, 1, 1, -1, -1, 0 };

// ──────────────────────────────────────────────────────────────────

int main() {
	int n;
	cin >> n;
	vi a(n + 1);
	Rep(i, n + 1) cin >> a[i];

	vi b(n + 1);
	vi ans;
	for (int i = n; i >= 1; i--) {
		int cnt = 0;
		for (int j = i; j < n + 1; j += i) {
			if (b[j] == 1) cnt++;
		}

		if (cnt % 2 != a[i]) {
			b[i] = 1, ans.push_back(i);
		}
	}

	reverse(ASC(ans));
	cout << ans.size() << endl;
	rep(i, ans.size()) cout << ans[i] << " ";
}

Measured memory_bytes: 3064
#define taskname "test"

#include <bits/stdc++.h>

using namespace std;

#define sz(x) (int)x.size()
#define fi first
#define se second

typedef long long lli;
typedef pair<int, int> pii;

int n;

void read_input()
{
    cin >> n;
}

void solve()
{
    int x = n % 10;
    if(x == 3) cout << "bon\n";
    else if(x == 0 || x == 1 || x == 6 || x == 8) cout << "pon\n";
    else cout << "hon\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    read_input();
    solve();
}



Measured memory_bytes: 3652
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = int(a); i < int(b); ++i)
typedef long long ll;
long long mod = 1e9 + 7;
const int iINF = 0x3f3f3f3f;
const long long INF = 1LL << 60;
using namespace std;

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;
}

struct Edge
{
  int to, cost;
};

int V;
vector<vector<Edge>> g(100100);
int costs[100100] = {};

// pair<コスト, 頂点>
using P = pair<int, int>;

void dijkstra(int s)
{
  // コストが小さいものがtop()にくる
  priority_queue<P, vector<P>, greater<P>> q;
  memset(costs, 0x3f, sizeof(costs));
  costs[s] = 0;
  q.push(P(0, s));

  while (!q.empty())
  {
    P p = q.top();
    q.pop();

    int v = p.second;
    if (costs[v] < p.first)
      continue;

    rep(i, g[v].size())
    {
      Edge e = g[v][i];
      if (costs[e.to] > costs[v] + e.cost)
      {
        costs[e.to] = costs[v] + e.cost;
        q.push(P(costs[e.to], e.to));
      }
    }
  }
}

int main()
{
  int V, E, r;
  cin >> V >> E >> r;

  rep(i, E)
  {
    int s, t, d;
    cin >> s >> t >> d;
    Edge e = {t, d};
    g[s].push_back(e);
  }

  dijkstra(r);

  for (int i = 0; i < V; ++i)
  {
    if (costs[i] != iINF)
      cout << costs[i] << endl;
    else
      cout << "INF" << endl;
  }
  return 0;
}



Measured memory_bytes: 13056
use proconio::*;
use std::*;

fn main() {
    input! {
        n: isize,
    }
    let mut ans = 0;
    for a in 1..1000001 {
        for b in 1..1000001 {
            if a*b + 1 <= n {
                ans += 1;
            } else {
                break
            }
        }
    }
    println!("{}", ans)
}


Measured memory_bytes: 2176
a = input()
b = ""
c = 0
for i in range(len(a)//2):
    b += "p"
for i in range(len(a) - len(b)):
    b += "g"
for i in range(len(a)):
    if a[i] == b[i]:
        c += 0
    elif a[i] == "g" and b[i] == "p":
        c += 1
    elif a[i] == "p" and b[i] == "g":
        c -= 1
print(c)


Measured memory_bytes: 3316
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
int PREP = (cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(12), 0);
//int SEGV = getenv("D") || (exit(system("D= SEGFAULT_SIGNALS=all catchsegv ./prog.exe") >> 8), 0);
using Int = long long;
int main() {
    Int N; cin >> N;
    Int ans = LLONG_MAX;
    for (Int a = 1; a * a <= 2*N; a += 1) {
        if (2*N % a != 0) continue;
        Int b = 2*N / a;
        if (gcd(a, b) != 1) continue;
        for (int t = 0; t < 2; t++) {
            Int n = atcoder::inv_mod(a, b);
            auto y = (b - n) * a;
            if (0 < y && y < ans) ans = y;
            swap(a, b);
        }
    }
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 3664
//
// Created by tattsun on 2017/02/21.
//

#include <iostream>
#include <vector>
#include <algorithm>

#define POINT_MAX 500001

using namespace std;

int n, q;
int xs[POINT_MAX], ys[POINT_MAX];

class Point {
public:
    Point(int id, int x, int y)
    : id(id), x(x), y(y) {
    }
    int id, x, y;
};

class Node {
public:
    Node()
    : l(), r(), location(-1) {
    }
    Node* l;
    Node* r;
    int location;
};

bool ascX(const Point& x, const Point& y) {
    return x.x < y.x;
}

bool ascY(const Point& x, const Point& y) {
    return x.y < y.y;
}

class KdTree {
public:
    KdTree(vector<Point>& ps)
    : ps(ps) {
        root = buildKdTree(ps, 0, (int)ps.size(), 0);
    }

    void find(int x1, int x2, int y1, int y2, vector<int>& res) {
        _find(x1, x2, y1, y2, 0, root, res);
        sort(res.begin(), res.end());
    }
private:
    vector<Point>& ps;
    Node* root;

    void _find(int x1, int x2, int y1, int y2, int depth, Node* n, vector<int>& res) {
        Point& p(ps[n->location]);
        if(x1 <= p.x && p.x <= x2 &&
           y1 <= p.y && p.y <= y2) {
            res.push_back(p.id);
        }

        if(depth % 2 == 0) {
            if(n->l != nullptr && p.x >= x1) {
                _find(x1, x2, y1, y2, depth+1, n->l, res);
            }
            if(n->r != nullptr && p.x <= x2) {
                _find(x1, x2, y1, y2, depth+1, n->r, res);
            }
        } else {
            if(n->l != nullptr && p.y >= y1) {
                _find(x1, x2, y1, y2, depth+1, n->l, res);
            }
            if(n->r != nullptr && p.y <= y2) {
                _find(x1, x2, y1, y2, depth+1, n->r, res);
            }
        }
    }

    static Node* buildKdTree(vector<Point>& ps, int l, int r,
                            int depth) {
        if(l >= r){
            return nullptr;
        }

        if(depth % 2 == 0) {
            sort(ps.begin()+l, ps.begin()+r, ascX);
        } else {
            sort(ps.begin()+l, ps.begin()+r, ascY);
        }

        int mid = (l+r)/2;

        Node* n = new Node();
        n->location = mid;
        n->l = buildKdTree(ps, l, mid, depth+1);
        n->r = buildKdTree(ps, mid+1, r, depth+1);

        return n;
    }
};

int main() {
    vector<Point> ps;

    scanf("%d", &n);

    int x, y;
    for(int i=0; i<n; i++) {
        scanf("%d %d", &x, &y);
        ps.push_back(Point(i, x, y));
    }

    KdTree kd(ps);

    scanf("%d", &q);

    int x1, x2, y1, y2;
    for(int i=0; i<q; i++) {
        vector<int> ans;
        scanf("%d %d %d %d", &x1, &x2, &y1, &y2);
        kd.find(x1, x2, y1, y2, ans);
        for(auto it = ans.begin(); it != ans.end(); it++) {
            printf("%d\n", *it);
        }
        printf("\n");
    }
}

Measured memory_bytes: 23792
#include <iostream>
#include <vector>
#include <iomanip>
#include <string>
#include <sstream>
#include <algorithm>
#include <map>
#include <bits/stdc++.h>

using namespace std;
#define REP(i,n) FOR(i,0,n)
#define FOR(i,a,b) for(long long i=(a),i##Len_=(b);i<i##Len_;i++)
typedef long long ll;
static const ll MOD = 1000000007;
static const ll INF = 1000000000000000000LL;


vector <vector<int>> g;
vector <bool> used;
vector <int> v;
ll N,M;


//行きがけか帰りがけか?
int dfs(int u)
{
    if(used[u])return 0;

    used[u] = true;
    for(int i: g[u])
    {
        dfs(i);
    }
    v.push_back(u);
}

void tsort(){
	for(int i = 0; i < N; i++) dfs(i);
	//reverse(v.begin(), v.end());
}

int main() {
    cin >> N >> M;
    g.resize(N);
    used.resize(N, false);
    
    REP(i,M)
    {
        int x, y;
        cin >> x >> y;
        --x;--y;
        g[x].push_back(y);
    }

    tsort();
	//なぜ、二重にreverse???
    //reverse(v.begin(), v.end());


    //dp[i]: トポロジカルソートで頂点iより後ろのパスの最大長
    vector <int>dp(N,0);
    int res = 0;
    //vの順がソートされている
    for(int i: v)
    {
        for(int u: g[i])
        {
            dp[i] = max(dp[i],dp[u] + 1);
        }
        res = max(res, dp[i]);
    }




    cout << res << endl;

    return 0;
}


Measured memory_bytes: 8696
#include <iostream>
#include <cmath>
using namespace std;
int main(){
    int N;
    cin >> N;
    double a,b,c;
    double t=4.0/N;
    //cout << t << endl;
    int mx = 3500;
    for(a=1;a<=mx;++a){
        if(t<1/a)continue;
        
        for(b=a;b<=mx;++b){
            if(t<1/a+1/b)continue;
            c = round(1/(t-(1/a+1/b)));
            if(c>999999)continue;
            if(c<1)continue;
           // cout << a << b << c << endl;
            if(4*a*b*c==N*(a*b+b*c+c*a)){
                cout << a <<" "<< b <<" "<< c << endl;
                // cout << 1/a+1/b+1/c << endl;
                // cout << t ;
                return 0;
            }
        }
    }
}

Measured memory_bytes: 256
using System;


public class hello
{
    public static void Main()
    {
        var n = int.Parse(Console.ReadLine().Trim());
        var defmax = -1000000000;
        var minvalue = int.Parse(Console.ReadLine().Trim());
        for (int i = 0; i < n - 1; i++)
        {
            var rvalue = int.Parse(Console.ReadLine().Trim());
            defmax = Math.Max(defmax, rvalue - minvalue);
            minvalue = Math.Min(minvalue, rvalue);
        }
        Console.WriteLine(defmax);
    }
}

Measured memory_bytes: 9316
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cstdlib>

#include <algorithm>
#include <iostream>
#include <numeric>
#include <limits>
#include <functional>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <queue>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;

const int N = 200010;

int n, l;
int x[N];
ll p[N], s[N];

ll pp(int x, int a) {
  return p[x] - p[max(x - a, 0)];
}

ll ss(int x, int a) {
  return s[x] - s[min(x + a, n + 1)];
}

ll solve() {
  ll ret = 0;
  for (int i = 1; i <= n; ++i)
    p[i] = p[i - 1] + x[i];
  for (int i = n; i; --i)
    s[i] = s[i + 1] + (l - x[i]);
  for (int i = 1; i <= n; ++i) {
    ll cur;
    int j1 = min(i, n - i), j2 = min(i - 1, n - i + 1);
    cur = max((pp(i - 1, j1) + ss(i + 1, j1)) * 2 + x[i],
              (pp(i - 1, j2) + ss(i + 1, j2)) * 2 + (l - x[i]));
    ret = max(ret, cur);
  }
  return ret;
}

int main() {
#ifdef CAI_WEI_HAN
	freopen("test.in", "r", stdin);
#endif

  scanf("%d%d", &l, &n);
  for (int i = 1; i <= n; ++i)
    scanf("%d", &x[i]);
  ll ans = solve();
  printf("%lld\n", ans);

  return 0;
}



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

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

int main() {
	string str;
	while (cin >> str, str != "0") {
		int a = count(str.c_str() + 1, str.c_str() + str.size(), 'A');
		int b = count(str.c_str() + 1, str.c_str() + str.size(), 'B');
		if (a >= 10 && b >= 10) {
			if (a > b) a++;
			else b++;
		}
		else if (a == 10) a++;
		else if (b == 10) b++;
		
		cout << a << " " << b << endl;
	}
	return 0;
}

Measured memory_bytes: 1184
#include<stdio.h>
int solve(int, int,int *,int);
int main()
{
  int i,n,q;
  int A[2000],M[2000];
 
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }
  scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&M[i]);
  }
 
  for(i=0;i<q;i++){
    if(solve(0,M[i],A,n)){
      printf("yes\n");
    }
    else printf("no\n");
  }
  return 0;
}

int solve(int i,int m,int *A,int n)
{
    int S=0;
    if(m==0)return 1;
    if(i>=n)return 0;
    else{
    S+=solve(i+1,m,A,n);
    S+=solve(i+1,m-A[i],A,n);
    }
    return S;
}


Measured memory_bytes: 2044
#include "bits/stdc++.h"
using namespace std;

#define ll long long

int main() {
	int k;
	ll i,j;
	ll piv;
	ll a[10][100000] = { 0 };
	cin >> k;
	int chk = k;
	piv = 0;
	for (i = 1; i <= 9; i++) {
		a[0][piv++] = i;
		chk--;
		if (chk == 0) {
			i = 0;
			goto end;
		}
	}
	for (i = 1; ; i++) {
		j = 0;
		piv = 0;
		while (a[i-1][j] != 0) {
			if (a[i - 1][j] % 10 == 0) {
				a[i][piv++] = a[i - 1][j] * 10;
				chk--;
				if (chk == 0)goto end;
				a[i][piv++] = a[i - 1][j] * 10 + 1;
				chk--;
				if (chk == 0)goto end;
				j++;
			}
			if (a[i - 1][j] % 10 == 9) {
				a[i][piv++] = a[i - 1][j] * 10 + 8;
				chk--;
				if (chk == 0)goto end;
				a[i][piv++] = a[i - 1][j] * 10 + 9;
				chk--;
				if (chk == 0)goto end;
				j++;
			}
			if (a[i - 1][j] % 10 != 0 && a[i-1][j] % 10 != 9) {
				a[i][piv++] = a[i - 1][j] * 10+a[i - 1][j]%10 - 1;
				chk--;
				if (chk == 0)goto end;
				a[i][piv++] = a[i - 1][j] * 10 + a[i - 1][j] % 10;
				chk--;
				if (chk == 0)goto end;
				a[i][piv++] = a[i - 1][j] * 10 + a[i - 1][j] % 10 + 1;
				chk--;
				if (chk == 0)goto end;
				j++;
			}
		}
	}

end:

	cout << a[i][piv-1];
	return 0;

}

Measured memory_bytes: 8064
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Main main = new Main();
		main.run();
	}

	long fact[];
	long ifact[];
	int NMAX = 1000000;
	long MOD = 1000000007;
	public void run() {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		int m=sc.nextInt();
		fact = new long[NMAX+1];
		ifact = new long[NMAX+1];

		if(Math.abs(n-m)>1) {
			sc.close();
			System.out.println(0);
			return;
		}

		init();

		long ans = 0;
		if(n==m) {
			ans = fact[n] * fact[m];
			ans %= MOD;
			ans *= 2;
			ans %= MOD;
		}else {
			ans = fact[n] * fact[m];
			ans %= MOD;
		}
		System.out.println(ans);
		sc.close();
	}

	private void init() {
		fact[0]=1;
		fact[1]=1;
		for(int i=2; i<=NMAX; i++) {
			fact[i] = fact[i-1] * i;
			fact[i] %= MOD;
		}
		ifact[NMAX] = inv(fact[NMAX]);
		for(int i=NMAX-1; i>=0; i--) {
			ifact[i] = ifact[i+1] * i;
			ifact[i] %= MOD;
		}
	}


	private long pow(long n, long k) {
		if(k==0) return 1;
		if(k%2==0) {
			long tmp = pow(n, k/2);
			long ans = tmp * tmp;
			ans %= MOD;
			return ans;
		}else {
			long tmp = pow(n, k-1);
			long ans = tmp * n;
			ans %= MOD;
			return ans;
		}
	}

	private long inv(long x) {
		return pow(x, MOD-2);
	}



}


Measured memory_bytes: 52984
#include <bits/stdc++.h>
using namespace std;
char s[200005];
stack<int> st;
int main(){
	scanf("%s", s+1);
	int n = strlen(s+1);
	for(int i=1;i<=n;i++){
		if(s[i] == 'S') st.push(0);
		else if(s[i] == 'T'){
			if(!st.empty() && st.top() == 0) st.pop();
			else st.push(1);
		}
	}
	printf("%d\n", st.size());
}

Measured memory_bytes: 1280
#include <iostream>
#include <algorithm>
#include <set>
#include <cstring>
#include <unordered_set>
using namespace std;

const int mod = 998244353;
const int maxn = 2e5 + 7;
char s[maxn];

void add(int &a, int b) {
	a = (a + b) % mod;
}

int f[maxn][3][3][2];
int main() {
	scanf("%s", s);
	int n = strlen(s);
	if (n == 1) printf("1\n");
	else if (n == 2) printf("%d\n", (s[0] == s[1]) ? 1 : 2);
	else if (n == 3) {
		if (s[0] == s[1] && s[0] == s[2]) printf("1\n");
		else if (s[0] != s[1] && s[1] != s[2] && s[2] != s[0]) printf("3\n");
		else if (s[0] != s[1] && s[0] == s[2]) printf("7\n");
		else printf("6\n");
	}
	else {
		bool flag = false;
		for (int i = 1; i < n; i++) {
			if (s[i] != s[i - 1]) flag = true;
		}
		
		if (!flag) {
			printf("1\n");
			return 0;
		}
		
		int cnt = 0;
		for (int i = 0; i < n; i++) cnt = (cnt + s[i] - 'a') % 3;
		
		f[1][1][1][0] = 1; // (pos, last, mod 3, is diff)
		f[1][2][2][0] = 1;
		f[1][0][0][0] = 1;
		for (int i = 2; i <= n; i++) {
			for (int last = 0; last < 3; last++) 
			for (int last_cnt = 0; last_cnt < 3; last_cnt++)
			for (int is_diff = 0; is_diff < 2; is_diff++) 
			for (int cur = 0; cur < 3; cur++) {
				int nxt_cnt = (last_cnt + cur) % 3;
				int cur_diff = 0;
				if (last == cur) cur_diff = 1;
				add(f[i][cur][nxt_cnt][max(cur_diff, is_diff)], f[i - 1][last][last_cnt][is_diff]);
			}
		}
		
		
		int ans = ((f[n][0][cnt][1] + f[n][1][cnt][1]) % mod + f[n][2][cnt][1]) % mod;
		ans = (ans + 1) % mod;
		for (int i = 1; i < n; i++) 
			if (s[i] == s[i - 1]) {
				ans = (ans + mod - 1) % mod;
				break;
			}
		printf("%d\n", ans);
//		printf("%d\n", ((f[n][0][cnt][1] + f[n][1][cnt][1]) % mod + f[n][2][cnt][1]) % mod);
	}
	return 0;
}


Measured memory_bytes: 14464
N,M=map(int,input().split())
war=[list(map(int,input().split())) for _ in range(M)]
war=sorted(war,key=lambda x:x[1],reverse=True)
war.sort(key=lambda x:x[0],reverse=True)
#print(war)
cnt=0
flag=0
ma=war[0][0]
for i in range(M):
    if war[i][1]<=ma:
        cnt=cnt+1
        flag=0
        ma=war[i][0]
print(cnt+1)


Measured memory_bytes: 68824
#include<bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
typedef long long int lli;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef vector<pll> vop;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define REP(i,a,b) for( int i=a;i<b;i++)
#define REPR(i,a,b) for(int i=a;i>=b;i--)
#define adb(a) for(auto i:a) cout << i << " "; cout << endl
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
#define endl "\n"
#define mem(a,b) memset(a,b,sizeof(a))
#define mod 998244353
#define PI 3.14159265358979323846
const ll N = 200007;

struct LessSecond
{
    template<typename T, typename U>
    bool operator()(const std::pair<T, U> &x, const std::pair<T, U> &y) const
    {
        return x.second < y.second;
    }
};

ll power(ll a, ll b, ll m) { ll ans = 1; a = a % m; while (b) { if (b & 1) ans = (ans * a) % m; b /= 2; a = (a * a) % m; } return ans; }

ll lcm(ll a, ll b) { return (a * b) / __gcd(a, b); }

ll modInverse(ll a, ll m) { ll g = __gcd(a, m); return power(a, m - 2, m); }

int h, w, k, n = 1;
char a[7][7];

int fun(vi r, vi c)
{
    //cout << n << endl;
    n++;
    char b[7][7];
    REP(i, 1, h + 1) REP(j, 1, w + 1) b[i][j] = a[i][j];
    // adb(r);
    // adb(c);
    REP(i, 0, r.size())
    {
        REP(j, 1, w + 1)
        {
            b[r[i]][j] = 'r';
        }
    }
    REP(i, 0, c.size())
    {
        REP(j, 1, h + 1)
        {
            b[j][c[i]] = 'r';
        }
    }
    int black = 0;
    REP(i, 1, h + 1)
    {
        REP(j, 1, w + 1)
        {
            if (b[i][j] == '#')
                black++;
        }
    }
    if (black == k)
        return 1;
    else
        return 0;
}

int main()
{


    fastIO;
    int test = 1;
    //cin >> test;
    while (test--)
    {
        cin >> h >> w >> k;
        REP(i, 1, h + 1)
        {
            REP(j, 1, w + 1) cin >> a[i][j];
        }
        int ans = 0;
        for (int mask = 0; mask < (1 << (h + w)); mask++) {
            vi r, c;
            for (int i = 0; i < h; i++) {
                if (mask & (1 << i)) {
                    r.PB(i + 1);
                }
            }
            REP(i, h, h + w)
            {
                if (mask & (1 << i))
                    c.PB(i - h + 1);
            }
            int rr = fun(r, c);
            //cout << rr << endl;
            ans += rr;
        }
        cout << ans << endl;
    }
    return 0;
}



Measured memory_bytes: 3640
<?php
$num = fgets(STDIN);
$monster = explode(" ",fgets(STDIN));
$hero = explode(" ",fgets(STDIN));
$damage = 0;
for ($i = 0; $i<$num; $i++) {
    if($monster[$i]+$monster[$i+1] >= $hero[$i]) {
        $damage += $hero[$i];
        if ($monster[$i] < $hero[$i]) {
            $monster[$i+1] = $monster[$i+1]-($hero[$i]-$monster[$i]);
        }
    } else {
        $damage += ($monster[$i] + $monster[$i+1]);
        $monster[$i+1] = 0;
    }
}

echo $damage;

Measured memory_bytes: 20980
#include <iostream>

using namespace std;

int main(int argc, char const *argv[])
{
	int x, a, b, t;
	cin >> x >> a >> b;
	t = b-a;
	if (t <= 0)
		cout << "delicious" << endl;
	else if (t <= x)
		cout << "safe" << endl;
	else
		cout << "dangerous" << endl;
	return 0;
}

Measured memory_bytes: 256
import bisect
import heapq
import itertools
import math
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18

W = sys.stdin.readline().rstrip()

if any([w % 2 for w in Counter(list(W)).values()]):
    print('No')
else:
    print('Yes')


Measured memory_bytes: 23176
use std::io::*;
use std::str::FromStr;
use std::collections::HashMap;
use std::collections::BTreeSet;
use std::collections::HashSet;
use std::cmp;
use std::f64::consts;

fn main() {
    let n: i32 = read();
    let vec: Vec<(i32,i32,i32)> = (0..n).map(|_| (read(),read(),read())).collect();

    let mut ans: String = "".to_string();

    'outer: for cx in 0..101 {
        'inner: for cy in 0..101 {
            let mut set: HashSet<i32> = HashSet::new();

            'last: for t in vec.iter() {
                let height: i32 = calculate_height(
                    t.0,
                    cx,
                    t.1,
                    cy,
                    t.2
                );

                if t.2 == 0 && height > 0 {
                    continue 'last;
                }
                set.insert(height);
            }

            if set.len() == 1 {
                let v: Vec<i32> = set.into_iter().collect();
                let top_height: i32 = v[0];

                let mut ok: bool = true;
                'a: for t in vec.iter() {
                    if !height_is_ok(
                        top_height,
                        t.0,
                        cx,
                        t.1,
                        cy,
                        t.2
                    ) {
                        ok = false;
                        break 'a;
                    }
                }
                if ok {
                    ans = format!("{} {} {}", cx, cy, top_height);
                    break 'outer;
                }
            }
        }
    }

    println!("{}", ans);
}

fn height_is_ok(
    h: i32,
    xi: i32,
    cx: i32,
    yi: i32,
    cy: i32,
    hi: i32
) -> bool {
    let height = cmp::max((h-(xi-cx).abs() - (yi-cy).abs()), 0);
    return height == hi;
}

fn calculate_height(
                xi: i32,
                cx: i32,
                yi: i32,
                cy: i32,
                hi: i32
) -> i32 {
    return (xi-cx).abs() + (yi-cy).abs() + hi;
}

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}


Measured memory_bytes: 4352
knum=gets.strip.to_i
nums=gets.strip.split(" ").map do |i|
  i.to_i
end
a=nums[0]
b=nums[1]
s='NG'
while(a<=b)
  if a%knum==0
    s="OK"
    break
  end
  a+=1
end
puts s

Measured memory_bytes: 14344
#include<iostream>
#include<string>
int main()
{
  int n;
  int an[1000];
  int l=0;
  std::cin>>n;
  std::string x;
  std::string y;
  int ans[1001][1001];
  int j,k;
  for(int i=0;i<n;i++){
    std::cin>>x;
    std::cin>>y;
    for(int j=0;j<=1000;j++){
      for(int k=0;k<=1000;k++){
	ans[j][k]=0;
      }
    }
    for(int j=1;j<x.size()+1;j++){
      for(int k=1;k<y.size()+1;k++){
	if(x[j-1]==y[k-1]){
	  ans[j][k]=ans[j-1][k-1]+1;
	}else{
	  if(ans[j][k-1]>ans[j-1][k]){
	    ans[j][k]=ans[j][k-1];
	  }else{
	    ans[j][k]=ans[j-1][k];
	  }
	}
      }
    }
    std::cout<<ans[x.size()][y.size()]<<'\n';  
  }
  return 0;
}



Measured memory_bytes: 7072
from collections import defaultdict

def main():
    """
    n = argmax(dp)とすると、
    (n - dp[n], n]は操作を行わなくてok

    逆にそれ以外の数は1回操作する
    -> N - dp[n]
    """
    N = int(input())

    dp = defaultdict(int)

    for _ in range(N):
        p = int(input())
        dp[p] = dp[p - 1] + 1
    
    print(N - max(dp.values()))

if __name__ == "__main__":
    main()

Measured memory_bytes: 32992
N, K = map(int, input().split())
MOD = 10 **9 + 7
suma = [0]

for i in range(1, N+1):
    suma.append(suma[-1] + i)
ans = 0

for i in range(K, N+1):
    ans += ((suma[N] - suma[N-i]) - suma[i-1] + 1) % MOD
ans += 1
print(ans % MOD)

Measured memory_bytes: 19232
#include <bits/stdc++.h>
#define ll long long
#define M 1000000007
#define mp make_pair
#define pb push_back
#define p(k) printf("%d ",k)
#define pl(k) printf("%lld ",k)
#define pn(k) printf("%d\n",k)
#define pln(k) printf("%lld\n",k)
#define ps(str) printf("%s",str)
#define s(k) scanf("%d",&k)
#define sl(k) scanf("%lld",&k)
#define ss(str) scanf("%s",str)
#define sz(a) a.size()
#define all(a) a.begin(),a.end()
#define ppi pair<int,int>
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ft first
#define sd second
#define count(x) __builtin_popcountll(x)

using namespace std;

const int N = 305;
double dp[N][N][N];
double ex[N][N][N];
void test_case(){
	int n,i,k,one,two,three;
	s(n);
	vector<int>cnt(5,0);
	for(i=0;i<n;i++){
		s(k);
		cnt[k]++;
	}
	for(one=0;one<N;one++){
		for(two=0;two<N;two++){
			for(three=0;three<N;three++){
				dp[one][two][three] = 0;
				ex[one][two][three] = 0;
			}
		}
	}
	dp[cnt[1]][cnt[2]][cnt[3]] = 1.0;
	for(three = cnt[3];three >= 0;three--){
		for(two = N-1;two >= 0;two--){
			for(one = N-1;one >= 0;one--){
				int tot = one+two+three;
				if(one==0 && two==0 && three==0){
					continue ;
				}
				if(one+two+three>n){
					continue ;
				}
				double ex_waste = ((double)(n-tot)/(double)tot+1)*dp[one][two][three];
				ex[one][two][three] += ex_waste;
				if(one-1>=0){
					double pr = (double)one / (double)(one + two + three);
					dp[one-1][two][three] += dp[one][two][three]*pr;
					ex[one-1][two][three] += (ex[one][two][three])*pr;          
				}
				if(one+1<N && two-1>=0){
					double pr = (double)two / (double)(one + two + three);
					dp[one+1][two-1][three] += dp[one][two][three]*pr;
					ex[one+1][two-1][three] += (ex[one][two][three])*pr;
				}
				if(two+1<N && three-1>=0){
					double pr = (double)three / (double)(one + two + three);
					dp[one][two+1][three-1] += dp[one][two][three]*pr;
					ex[one][two+1][three-1] += (ex[one][two][three])*pr;
				}
				//~ printf("%lf\n",dp[one][two][three]);
			}
		}
	}
	printf("%0.10lf",ex[0][0][0]);
}
signed main(){
	int t;
	t = 1;
	//~ s(t);
	while(t--){
		test_case();
	}
	return 0;
}


Measured memory_bytes: 443648
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

class Main {
    public static void main(String[] args) {

        Scanner inpunt = new Scanner(System.in);
        int x ,y ;
        String result="";
        x=inpunt.nextInt();
        y=inpunt.nextInt();
        inpunt.nextLine();
        String array[] = new String[x];
        for(int i=0;i<x;i++){
           array[i]=inpunt.nextLine();
        }

        Arrays.sort(array);

        for(int i=0;i<x;i++){
            result += array[i];
        }
        System.out.println(result);

    }
}

Measured memory_bytes: 26068
#include<stdio.h>

int selectionSort(int A[],int N){
    int i,j,t,sw = 0,minj;
    for(i = 0;i < N - 1;i++){
        minj = i;
        for(j = i;j < N;j++){
            if(A[j] < A[minj]) minj = j;
        }
        t = A[i]; 
        A[i] = A[minj]; 
        A[minj] = t;
        if(i != minj) sw++;
    }
    return sw;
}

int main(){
    int A[100],N,i,sw;
    
    scanf("%d",&N);
    for(i = 0;i < N;i++) scanf("%d",&A[i]);
    
    sw = selectionSort(A,N);
    
    for(i = 0;i < N;i++){
        if(i > 0) printf(" ");
        printf("%d",A[i]);
    }
    printf("\n");
    printf("%d\n",sw);
    
    return 0;
}


















Measured memory_bytes: 2044
#include<bits/stdc++.h>
using namespace std;
void fl()
{
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
}
int main()
{
	ios::sync_with_stdio();
//  fl();
	string ss;
	cin>>ss;
	int cnt=0;
	for(int i=0;i<ss.length()/2;i++)
	{
		if(ss[i]!=ss[ss.length()-i-1])
			cnt++;	
	}
	cout<<cnt<<endl;	
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
typedef vector<vector<P>> vvP;
#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 = 100010;

int main() {
    ll h, a;
    cin >> h >> a;
    out((h+a-1)/a);
    re0;
}

Measured memory_bytes: 256
STDIN.read.chomp.split("\n").each do |list|
  a, b, c, d, e, f = list.split.map(&:to_f)
  x = (b * f - c * e) / (b * d - a * e)
  y = (a * f - c * d) / (a * e - d * b)
  puts [x.zero? && x.abs || x, y.zero? && y.abs || y].map { |i| format('%.3f', i) }.join(' ')
end

Measured memory_bytes: 8608
#include <stdio.h>
#include <string.h>

int flg[9];

struct P{
	char s[8];
}p[9],set[9];

int solve(int idx){
	int i,j,k,res=0;

	if(idx == 9) return 1;

	for(k=0;k<9;k++){
		if(flg[k] == 1) continue;
		flg[k] = 1;
		for(i=0;i<4;i++){
			for(j=0;j<4;j++){
				set[idx].s[(i+j)%4] = p[k].s[j];
			}

			if(idx%3>0 &&
				 set[idx].s[3] + 32 != set[idx-1].s[1] &&
				 set[idx].s[3] - 32 != set[idx-1].s[1])
				continue;
			if(idx>2 &&
				 set[idx].s[0] + 32 != set[idx-3].s[2] &&
				 set[idx].s[0] - 32 != set[idx-3].s[2])
				continue;

			res += solve(idx+1);
		}
		flg[k] = 0;
	}

	return res;
}

int main(void){
	int i,n;

	scanf("%d",&n);

	while(n--){
		for(i=0;i<9;i++){
			scanf("%s",p[i].s);
		}
		memset(flg,0,sizeof(flg));
		printf("%d\n",solve(0));
	}

	return 0;
}

Measured memory_bytes: 412
#include <cstdio>
#include <cstring>
using namespace std;
bool p[21][21];
int ans;
int H,W,h,w;
int main(){
	memset(p,true,sizeof(p));
	scanf("%d%d%d%d",&H,&W,&h,&w);
	for (int i=1;i<=h;i++)
	    for (int j=1;j<=W;j++)
	        p[i][j]=false;
	for (int j=1;j<=w;j++)
	    for (int i=1;i<=H;i++)
	        p[i][j]=false;
	for (int i=1;i<=H;i++)
	    for (int j=1;j<=W;j++)
	        if (p[i][j]==true) ans++;
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 128
n = int(input())
s = [input() for _ in range(3)]

ans = 0
for v in zip(*s):
    len_ = len(set(v))
    ans += len_ - 1

    # if len_ == 3:
    #     ans += 2
    # elif len_ == 2:
    #     ans += 1
    # else:
    #     # len_ == 1
    #     ans += 0

print(ans)


Measured memory_bytes: 2940
use std::collections::HashSet;

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn chars(s: &str) -> HashSet<char> {
    let mut chars = HashSet::new();
    for c in s.chars() {
        chars.insert(c);
    }
    chars
}

fn same_chars(right_chars: HashSet<char>, left_chars: HashSet<char>) -> Vec<char> {
    let same_chars: Vec<char> = right_chars.iter().filter(|c| {
        right_chars.get(c).is_some() && left_chars.get(c).is_some()
    }).map(|c| *c).collect();
    same_chars
}

fn main() {
    let n: i8     = read();
    let s: String = read();
    let char_type_conuts: Vec<i8> = (1 .. n).map(|separate_index| {
        let (right, left) = s.split_at(separate_index as usize);
        let same_chars    = same_chars( chars(right), chars(left) );
        same_chars.len() as i8
    }).collect();
    println!("{}", char_type_conuts.iter().max().unwrap_or(&0));
}

Measured memory_bytes: 4352