akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

ll single(ll X){
  if(X%2==1){
    return ((X+1)/2)%2;
  }
  else{
    return ((X/2)%2)^X;
  }
}

int main(){
  ll A, B;cin>>A>>B;
  if (A==0){
    ll ans=single(B);
    cout << ans << endl;
  }
  else{
    ll ans=single(B)^single(A-1);
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <string>
#include <cassert>

using namespace std;

const int mod = 1e9 + 7;

using VL = vector<long long>;
using VVL = vector<VL>;
using VVVL = vector<VVL>;

int n;

void show(VVL &vv) {
    for (auto v: vv) {
        for (auto x: v) {
            printf("%3lld ", x);
        }
        printf("\n");
    }
}

VVL prod(const VVL &a, const VVL &b) {
    VVL ret(n, VL(n, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                ret[i][j] += a[i][k] * b[k][j];
                ret[i][j] %= mod;
            }
        }
    }
    return ret;
}

int main() {
    long long dist;
    cin >> n >> dist;

    const int maxi = 61;
    VVVL a(maxi, VVL(n, VL(n, 0)));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[0][i][j];
        }
    }

    for (int bit = 1; bit < maxi; bit++) {
        a[bit] = prod(a[bit - 1], a[bit - 1]);
    }

    int bit = 0;
    VVL mat(n, VL(n, 0));
    for (int i = 0; i < n; i++) {
        mat[i][i] = 1;
    }


    while (dist > 0) {
        if (dist & 1) {
            mat = prod(mat, a[bit]);
        }

        bit++;
        dist >>= 1;
    }

    // for (int i = 0; i < maxi; i++) {
    //     printf("i %d ------\n", i);
    //     show(a[i]);
    // }
    // show(mat);

    long long ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ans += mat[i][j];
        }
    }
    ans %= mod;
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1664
ans = 0
arr = [int(input()) for _ in range(5)]
ans = float('inf')
maxsum = 0
for i in range(5):
    maxsum += -(-arr[i] // 10) * 10
for i in range(5):
    if maxsum - -(-arr[i] // 10) * 10 + arr[i] < ans:
        ans = maxsum - -(-arr[i] // 10) * 10 + arr[i]
print(ans)

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

int main(){
  string s, t;
  cin >> s >> t;
  
  sort(s.begin(), s.end());
  sort(t.begin(), t.end());
  reverse(t.begin(), t.end());
  
  if(s < t) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define badi_val 10e13
int main(){	
	ios_base::sync_with_stdio(false);
	    cin.tie(NULL);
	   	int n;
	   	cin >> n;
	   	string s;
	   	cin >> s;
	   	s = "*"+s;
	   	int ans = 0;
	   	for(int i = 1 ; i < s.size() ; i++){
	   		if(s[i] != s[i - 1])
	   			ans++;
	   	}
	   	cout << ans << endl;
		return 0; 
}

Measured memory_bytes: 512
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,m = li()
ab = []
for _ in range(m):
    a,b = li_()
    ab.append(tuple([a,b]))
    
ab.sort(key=lambda x:x[1])
ans = 0
cur = -1

for a,b in ab:
    if a >= cur:
        ans += 1
        cur = b
        
print(ans)

Measured memory_bytes: 18200
use std::io::stdin;
use std::cmp::min;

fn main() {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    let mut first_line = buf.split_whitespace();
    let _ = first_line.next().unwrap();
    let _ = first_line.next().unwrap();
    let coupon: i32 = first_line.next().unwrap().parse().unwrap();

    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    let type_a = buf.split_whitespace();
    let type_a = type_a.map(|iter| iter.parse::<i32>().unwrap()).collect::<Vec<i32>>();

    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    let type_b = buf.split_whitespace();
    let type_b = type_b.map(|iter| iter.parse::<i32>().unwrap()).collect::<Vec<i32>>();

    let mut coupon_pair = Vec::new();
    for _ in 0..coupon{
        let mut buf = String::new();
        stdin().read_line(&mut buf).unwrap();
        let mut input = buf.split_whitespace();
        let a_index: usize = input.next().unwrap().parse().unwrap();
        let b_index: usize = input.next().unwrap().parse().unwrap();
        let discount: usize = input.next().unwrap().parse().unwrap();
        coupon_pair.push([a_index, b_index, discount]);
    }

    println!("{}", solve(type_a, type_b, coupon_pair));
}

fn solve(type_a: Vec<i32>, type_b: Vec<i32>, coupon_pair: Vec<[usize; 3]>) -> i32{
    let normal_min = type_a.iter().min().unwrap() + type_b.iter().min().unwrap();
    let mut discounts = Vec::with_capacity(coupon_pair.len());
    
    for coupon in coupon_pair{
        let discount: i32 = type_a[coupon[0] - 1] + type_b[coupon[1] - 1] - coupon[2] as i32;
         discounts.push(discount);
    }
    let discount_min = *(discounts.iter().min().unwrap());
    return min(normal_min, discount_min)
}

Measured memory_bytes: 12384
rot = {
    "North": (1,5,2,3,0,4),
    "East" : (3,1,0,5,4,2),
    "West" : (2,1,5,0,4,3),
    "South": (4,0,2,3,5,1),
    "Right": (0,2,4,1,3,5),
    "Left" : (0,3,1,4,2,5)
}
while 1:
    n = input()
    if not n:
        break
    dice = [1,2,3,4,5,6]
    nxt = [0]*6
    ans = 0
    for i in xrange(n):
        r = rot[raw_input()]
        dice = [dice[r[i]] for i in xrange(6)]
        ans += dice[0]
    print ans+1

Measured memory_bytes: 4244
#include <bits/stdc++.h>
using namespace std;
long long n,m,total,ans;
long long arr[100001];
long long pre[100001];
long long countt(long long cost){
    long long ans=0;
    for (int i=0;i<n;i++){
        long long cur=cost-arr[i];
        int num=upper_bound(arr,arr+n,cur)-(arr);
        ans+=num;
    }
    return ans;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>m;
    for (int i=0;i<n;i++){
        cin>>arr[i];
        ans+=arr[i]*(n*2);
    }
    m=n*n-m;
    sort(arr,arr+n);
    pre[0]=arr[0];
    for (int i=1;i<n;i++) pre[i]=pre[i-1]+arr[i];
    long long mini=0,maxi=10000000;
    while (mini+1<maxi){
        long long middle=(mini+maxi)/2;
        if (countt(middle)<m) mini=middle;
        else maxi=middle;
    }
    long long total=0;
    //cout<<maxi<<'\n';
    for (int i=0;i<n;i++){
        long long cur=maxi-arr[i];
        long long pos=upper_bound(arr,arr+n,cur)-(arr);
        if (pos==0) break;
        long long num=((arr[i]*pos)+pre[pos-1]);
        total+=num;
        m-=pos;
        //cout<<pos<<' '<<arr[pos-1]<<' '<<num<<'\n';
    }
    //cout<<m<<' '<<ans<<' '<<total<<'\n';
    total+=(maxi)*m;
    cout<<ans-total;
}

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

using namespace std;
#define ll long long

const int N = 1e5 + 5;
ll INF = 1e9 + 7;


int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin>>n;

    ll count = 0;

    for(int i=1;i<n;i++)
    {
        int d = n/i;
        if(i*d == n)
        {
            count += (d - 1);
        }
        else
        {
            count += (d);
        }
    }

    cout<<count<<endl;

}


Measured memory_bytes: 3648
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <numeric>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

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

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

#define IN(l, r, x) ((l) <= (x) && (x) < (r))

bool ok(string s, int k)
{
    // int convert = 0;
    int n = s.size();
    // rep (i, n - k)
    // {
    //     if ((s[i] == '1' && convert == 0) || (s[i] == '0' && convert == 1))
    //     {
    //         convert ^= 1;
    //     }
    // }
    bool ret = true;
    for (int i = n - k; i < k; ++i)
    {
        if (s[n - k] != s[i]) ret = false;
    }
    return ret;
}

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

    string s;
    cin >> s;
    int n = s.size();

    int l, r;
    l = CEIL(n, 2);
    r = n + 1;
    while (l + 1 < r)
    {
        int m = (l + r) / 2;
        if (ok(s, m))
        {
            l = m;
        }
        else
        {
            r = m;
        }
    }

    cout << l << "\n";
    return 0;
}



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

#define ll long long
#define vvi vector<vector<int>>
#define vec vector
#define pq priority_queue
#define all(v) (v).begin(), (v).end()
#define uniqueV(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define rep(i, n) for (int (i) = (0); (i) < (n); ++(i))
#define repp(i, m, n) for (int (i) = (m); (i) < (n); ++(i))
#define debug(x) cerr << #x << ": " << x << endl;
#define debug2(x, y) cerr<<"("<<#x<<", "<<#y<<") = "<<"("<<x<<", "<<y<<")"<<endl;
#define debug3(x, y, z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = "<<"("<<x<<", "<<y<<", "<<z<<")"<<endl;
#define debugB(value, size) cerr<<#value<<": "<<bitset<size>(value) << endl;
#define line() cerr << "---------------" << endl;

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const double PI = 3.14159265358979323846;

template<typename T>
void printA(vector<T> &printArray, char between = ' ') {
   int paSize = printArray.size();
   for (int i = 0; i < paSize; i++) { cerr << printArray[i] << between;}
   if (between != '\n') {cerr << endl;}
}

// ------------------------------------------------------------------------------------------

using pii = pair<ll, ll>;

ll H, W, N;
ll A[111111], B[111111];
set<pii> con;
set<pii> S;
ll ans[100];

void make(ll y, ll x) {
   for (ll i = -2; i <= 0; i++) {
      for (ll j = -2; j <= 0; j++) {
         ll ny = y + i, nx = x + j;
         if (ny >= 1 && ny <= H-2 && nx >= 1 && nx <= W-2) {
            S.insert({ny, nx});
         }
      }
   }
   // for (int i = -1; i <= 1; i++) {
   //    for (int j = -1; j <= 1; j++) {
   //       int ny = y + i, nx = x + j;
   //       if (ny < 1 || ny > H || nx < 1 || nx > W) continue;
   //       if (ny + 2 <= H && nx + 2 <= W) {
   //          S.insert({ny, nx});
   //       }
   //    }
   // }
}

int main() {
   cin >> H >> W >> N;
   rep (i, N) {
      cin >> A[i] >> B[i];
      con.insert({A[i], B[i]});
      make(A[i], B[i]);
   }

   ll white = (H-2) * (W-2);
   for (pii p : S) {
      ll y = p.first, x = p.second;
      int cnt = 0;
      // debug2(y, x)
      for (ll i = y; i < y+3; i++) {
         for (ll j = x; j < x+3; j++) {
            if (con.find({i, j}) != con.end()) {
               cnt++;
            }
         }
      }
      if (cnt) white--;
      ans[cnt]++;
   }

   ans[0] = white;
   for (int i = 0; i <= 9; i++) {
      cout << ans[i] << endl;
   }


   return 0;
}

Measured memory_bytes: 64256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
using ld = long double;
template<typename T> using V = vector<T>;
template<typename T> using VV = vector<vector<T>>;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,a,n) for(ll i=a;i<(ll)(n);++i)
#define repr(i,a,n) for(ll i=n-1;(ll)a<=i;--i)
#define lb lower_bound
#define ub upper_bound
#define ENDL '\n'
typedef pair<int,int> Pi;
typedef pair<ll,ll> PL;
const ll mod = 1000000007;
const ll INF = 1000000099;
const ll LINF = (ll)(1e18 +99);
const vector<ll> dx={-1,1,0,0},dy={0,0,-1,1};
template<typename T,typename U> inline bool chmin(T& t, const U& u){if(t>u){t=u;return 1;}return 0;}
template<typename T,typename U> inline bool chmax(T& t, const U& u){if(t<u){t=u;return 1;}return 0;}
template<typename T> inline T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T,typename Y> inline T mpow(T a, Y n) {
  T res = 1;
  for(;n;n>>=1) {
    if (n & 1) res = res * a;
    a = a * a;
  }
  return res;
}



signed main(){
  cin.tie(0);ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(20);
  ll h,w,n;cin>>h>>w>>n;
  cout<<(n+max(h,w)-1)/max(h,w)<<ENDL;
}
//( ・ __ ・ ) KEEP BEING ORGANIZED
//CHECK overflow,vector_size,what to output?

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

namespace kangaroo
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] x = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int a = x[0];
            int b = x[1];
            
            Console.WriteLine(a*b+" "+ 2*(a+b));
            Console.ReadLine();
        }
    }
}




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

#define fr first
#define sc second
#define OK puts("OK");
#define pb push_back
#define mk make_pair


using namespace std;

typedef long long ll;

const int inf = (int)1e9 + 7;
const int N = (int)1e5 + 7;

string a;

int main () {
        cin >> a;

        for (int i = 0; i < a.size() - 8; i ++)
                cout << a[i];
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<stdio.h>
#include<string>
using namespace std;
#define pb push_back
#define pf push_front

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define sz(x) int(x.size())
#define INF 1e5
int main(){
	string s;
	cin>>s;
	if(s=="Sunny") cout<<"Cloudy"<<endl;
	if(s=="Cloudy") cout<<"Rainy"<<endl;
	if(s=="Rainy") cout<<"Sunny"<<endl;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void) {

	int n, i, j, judge=0;

	scanf("%d", &n);

	for (i = 0; i * 4<=100; i++) {
		for (j = 0; i * 4 + j * 7 <= 100; j++) {
			
			if (i * 4 + j * 7 == n) {
				judge = 1;
				break;
			}
		}
	}
	
	if (judge == 1){
		printf("Yes");
	}
	else {
		printf("No");
	}

	return 0;
}

Measured memory_bytes: 128
X,N=map(int,input().split())
if N==0:
    print(X)
    exit()
p=list(map(int,input().split()))

ans=1000
for i in range(0,102):
    if i in p:
        continue
    if abs(ans-X)>abs(i-X):
        ans=i
print(ans)

Measured memory_bytes: 9180
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
input = sys.stdin.buffer.readline
def inputS(): return input().rstrip().decode()
readlines = sys.stdin.buffer.readlines  

N  = int(input())
XY = [[] for _ in range(N)] # 証言者

for i in range(N):
  A = int(input())
  for _ in range(A):
    ind, bl = map(int, input().split())
    XY[i].append((ind-1, bl))

ans = 0
for bit in range(1<<N):
  cnt = 0
  ok = True
  for i in range(N):
    # i 人目が「不親切」だったら、証言はすべて無意味
    if not bit >> i & 1:
      continue
    # 証言通りかそれぞれ確認
    for x, y in XY[i]:
      # y = 1 なのに「不親切」だったらダメ      
      # y = 0 なのに「正直者」だったらダメ
      if bit >> x & 1 ^ y:
        ok = False
        break
    if ok:
      cnt += 1
    else:
      break
  else:
    ans = max(ans, cnt)
print(ans)    

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

long long getMaxDifference (const vector <int> &nums) {
    int n = nums.size();
    vector <vector <long long>> dp(n, vector <long long>(n));

    for (int left = n - 1; left >= 0; --left) {
        for (int right = left; right < n; ++right) {
            if (left == right) {
                dp[left][right] = nums[left];
            } else {
                dp[left][right] = max(nums[left] - dp[left + 1][right],
                                      nums[right] - dp[left][right - 1]);
            }
        }
    }
    return dp[0][n - 1];
}

int main() {
    int n;
    cin >> n;
    vector <int> nums(n);
    for (int &i : nums) {
        cin >> i;
    }
    cout << getMaxDifference(nums) << "\n";
    return 0;
}


Measured memory_bytes: 70656
n = int(input())
a = [int(i) for i in input().split()]
a.append(0)
cnt = 1
ans = 0
for i in range(1,n+1):
    if a[i-1] == a[i]:
        cnt += 1
    else:
        ans += cnt//2
        cnt = 1
print(ans)

Measured memory_bytes: 3060
def solve():
    n = int(input())
    a = []
    b = []
    for _ in range(n):
        x,y = map(int,input().split())
        a.append(x)
        b.append(y)
    ans = 0
    for i in range(n)[::-1]:
        if (a[i]+ans)%b[i]:
            ans+=b[i]-(a[i]+ans)%b[i]
    print(ans)
if __name__=='__main__':
    solve()

Measured memory_bytes: 11048
// In the name of GOD
 
#include <bits/stdc++.h>
#define ll long long
#define pp pair <int, int>
using namespace std;
const int N = 1e5 + 10;
const ll INF = 1e18;

void solve() {
	string s, t;
	cin >> s >> t;
	int n = s.length(), m = t.length();
	vector <vector <int>> dp(n+1, vector <int> (m+1, 0));
	for (int i = 0; i < n; ++i) {
	 	for (int j = 0; j < m; ++j) {
	 		if (s[i] == t[j]) {
	 			dp[i + 1][j + 1] = dp[i][j] + 1;
	 		}
	 		else {
	 			dp[i + 1][j + 1] = max (dp[i][j + 1], dp[i + 1][j]);
	 		}
	 		// cout << dp[i + 1][j + 1] << " ";
	 	}
	 	// cout << "\n";
	 }
	 // cout << dp[n][m];
	 int i = n, j = m;
	 string ans = "";
	 while (i > 0 && j > 0) {
	 	if (s[i - 1] == t[j - 1]) {
	 		ans += s[i - 1];
	 		// cout << s[i];
	 		i--; j--;
	 	}
	 	else if (dp[i - 1][j] >= dp[i][j - 1])
	 		i--;
	 	else 
	 		j--;
	 }
	 reverse(ans.begin(), ans.end());
	 cout << ans;
}
int main () {
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
    int tt = 1;
    // cin >> tt;
    for (int tc = 1; tc <= tt; ++tc) {
        solve();
    }
}                                  

Measured memory_bytes: 35584
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigDecimal;

class Main {

	private static BufferedReader br = new BufferedReader(
			new InputStreamReader(System.in));

	public static void main(String[] args)
			throws IOException {

		try {
			Integer week = Integer.parseInt(br
					.readLine());

			int i = week.intValue();
			BigDecimal amount = new BigDecimal(
					"100000");
			BigDecimal interest;
			while (i > 0) {
				interest = amount.multiply(
						new BigDecimal("0.05"));
				amount = amount.add(interest)
						.setScale(-3,
								BigDecimal.ROUND_UP);
				i--;
			}
			System.out.println(amount
					.toPlainString());
		} catch (NumberFormatException e) {
			br.close();
			e.printStackTrace();
		} catch (IOException e) {
			br.close();
			e.printStackTrace();
		}

	}

}

Measured memory_bytes: 24512
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCorder
{
	public class Program
	{
		static void Main(string[] args)
		{
			Scanner cin = new Scanner();
			int n = cin.Int();
			string[] s = new string[n];
			for (int i = 0; i < n; i++) {
				s[i] = new string(cin.Next().OrderBy(x => x).ToArray());
			}

			long ans = 0;
			Dictionary<string, int> hash = new Dictionary<string, int>();
			for (int i = 0; i < n; i++) {
				if (hash.ContainsKey(s[i])) {
					ans += hash[s[i]];
					hash[s[i]] += 1;
				} else {
					hash[s[i]] = 1;
				}
			}

			Console.WriteLine(ans);
		}
	}

	public class Scanner
	{
		private readonly char[] delimiter_ = new char[] { ' ' };
		private string[] buf_;
		private int index_;
		
		public Scanner()
		{
			buf_ = new string[0];
			index_ = 0;
		}

		public string Next()
		{
			if (index_ < buf_.Length) {
				return buf_[index_++];
			}

			string st = Console.ReadLine();
			while (st == "") {
				st = Console.ReadLine();
			}

			buf_ = st.Split(delimiter_, StringSplitOptions.RemoveEmptyEntries);
			if (buf_.Length == 0) {
				return Next();
			}

			index_ = 0;
			return buf_[index_++];
		}

		public int Int()
		{
			return int.Parse(Next());
		}
		public int[] ArrayInt(int N, int add = 0)
		{
			int[] Array = new int[N];
			for (int i = 0; i < N; i++) {
				Array[i] = Int() + add;
			}
			return Array;
		}

		public long Long()
		{
			return long.Parse(Next());
		}

		public long[] ArrayLong(int N, long add = 0)
		{
			long[] Array = new long[N];
			for (int i = 0; i < N; i++) {
				Array[i] = Long() + add;
			}
			return Array;
		}

		public double Double()
		{
			return double.Parse(Next());
		}

		public double[] ArrayDouble(int N, double add = 0)
		{
			double[] Array = new double[N];
			for (int i = 0; i < N; i++) {
				Array[i] = Double() + add;
			}
			return Array;
		}
	}
}


Measured memory_bytes: 29192
//2018.9.25 by ljz
#include<bits/stdc++.h>
using namespace std;
#define res register int
#define LL long long
#define inf 0x3f3f3f3f
#define eps 1e-15
inline int read(){
    res s=0;
    bool w=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return w?-s:s;
}
inline void _swap(res &x,res &y){
    x^=y^=x^=y;
}
inline int _abs(const res &x){
    return x>0?x:-x;
}
inline int _max(const res &x,const res &y){
    return x>y?x:y;
}
inline int _min(const res &x,const res &y){
    return x<y?x:y;
}
const int kcz=1e9+7;
const int NN=2e3+10,KK=2e3+10,N=NN*KK+NN+KK;
namespace MAIN{
    inline int qpow(res x,res y,const res &kcz){
        res ans=1;
        while(y){
            if(y&1)ans=(LL)ans*x%kcz;
            x=(LL)x*x%kcz,y>>=1;
        }
        return ans%kcz;
    }
    int inv[N],fac[N];
    inline void pre(){
        inv[0]=inv[1]=fac[0]=fac[1]=1;
        for(res i=2;i<=N-10;i++)fac[i]=(LL)fac[i-1]*i%kcz,inv[i]=(LL)(kcz-kcz/i)*inv[kcz%i]%kcz;
        for(res i=2;i<=N-10;i++)inv[i]=(LL)inv[i-1]*inv[i]%kcz;
    }
    inline int C(const res &x,const res &y){
        return (LL)fac[x]*inv[y]%kcz*inv[x-y]%kcz;
    }
    int n,k;
    int dp[NN][KK];
    inline void add(res &x,const res &y){
        x+=y;
        x>=kcz?x-=kcz:1;
    }
    inline void MAIN(){
        pre();
        n=read(),k=read()-1;
        if(!k){puts("1");return;}
        dp[0][0]=1;
        for(res i=0;i<=n;i++)
            for(res j=i;j<=n;j++){
                if(i)add(dp[i][j],dp[i-1][j]);
                if(j)add(dp[i][j],(LL)dp[i][j-1]*C(i+j*k-1,k-1)%kcz);
            }
        printf("%d\n",(LL)dp[n][n]*fac[n]%kcz);
    }
}
int main(){
    MAIN::MAIN();
    return 0;
}

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

int main() {
    int n, q;
    string s;
    cin >> n >> q >> s;
    vector<int> l(q), r(q);
    for (int i = 0; i < q; i++) cin >> l[i] >> r[i];
    int ac[n + 1];
    for (int i = 0; i <= n; i++) ac[i] = 0;
    for (int i = 1; i < n; i++) ac[i + 1] = s[i - 1] == 'A' && s[i] == 'C' ? ac[i] + 1 : ac[i];
    for (int i = 0; i < q; i++) cout << ac[r[i]] - ac[l[i]] << endl;
}


Measured memory_bytes: 2176
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int W = Integer.parseInt(sc.next());
		int H = Integer.parseInt(sc.next());
		int N = Integer.parseInt(sc.next());
		int[] X = new int[N];
		int[] Y = new int[N];
		int[] A = new int[N];
		for(int i = 0;i < N;i++) {
			X[i] = Integer.parseInt(sc.next());
			Y[i] = Integer.parseInt(sc.next());
			A[i] = Integer.parseInt(sc.next());
		}
		sc.close();
		int[][] blk = new int[W][H];
		for(int i = 0;i < W;i++) {
			for(int j = 0;j < H;j++) {
				blk[i][j] = 0;
			}
		}
		for(int i = 0;i < N;i++) {
			switch(A[i]){
			case 1:
				for(int j = 0;j < X[i];j++) {
					for(int k = 0;k < H;k++) {
						blk[j][k]++;
					}
				}
				break;
			case 2:
				for(int j = X[i];j < W;j++) {
					for(int k = 0;k < H;k++) {
						blk[j][k]++;
					}
				}
				break;
			case 3:
				for(int j = 0;j < W;j++) {
					for(int k = 0;k < Y[i];k++) {
						blk[j][k]++;
					}
				}
				break;
			case 4:
				for(int j = 0;j < W;j++) {
					for(int k = Y[i];k < H;k++) {
						blk[j][k]++;
					}
				}
				break;
			}
		}
		int ans = 0;
		for(int i = 0;i < W;i++) {
			for(int j = 0;j < H;j++) {
				if(blk[i][j] == 0) {
					ans++;
				}
			}
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 22996
#include <iostream>
#include <iomanip>
typedef long long ll;
using namespace std;
const  ll INF = 1e9;
const  ll MOD = 1e9 + 7;
#define repi(i,n,init) for(ll i=init;i<(n);i++)

int main()
{
    int a,b;
    cin >> a >> b;
    if(b >= a){
        cout << a << endl;
    }else{
        cout << a-1 << endl;
    }
    return 0;
}

Measured memory_bytes: 3564
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main(){
string str1,str2;
cin>>str1>>str2;
str2+=str2;
for(int i=0;i<str2.length()-str1.length();i++){
bool st=true;
for(int j=i;j<i+str1.length();j++){
st=st&&str1[j-i]==str2[j];
}
if(st){cout<<"Yes"<<endl;return 0;}
}
cout<<"No"<<endl;
return 0;
}

Measured memory_bytes: 256
def divide(n, p):
    c = 0
    while n%p == 0 and c < 18:
        c += 1
        n //= p
    return c

n = int(input())
table = [[0]*19 for _ in range(19)]
for i in range(n):
    sub = input()
    key = float(sub)
    if "." in sub:
        a, b = map(str, sub.split("."))
        s = int(a)*1000000000+10**(9-len(b))*int(b)
    else:
        s = int(sub)
        s *= 1000000000
    if key != s/1000000000:
        while True:
            pass
    c2, c5 = divide(s, 2), divide(s, 5)
    table[c2][c5] += 1

ans = 0
for i in range(19):
    for j in range(19):
        for k in range(19):
            for l in range(19):
                if i+k < 18 or j+l < 18:
                    continue;
                if i == k and j == l:
                    ans += table[i][j]*(table[k][l]-1)
                else:
                    ans += table[i][j]*table[k][l]

ans //= 2
print(ans)

Measured memory_bytes: 9232
from collections import defaultdict,deque
import numpy as np
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N,K = inpl()
AA = np.array(inpl())
S = sum(AA)

koho = set()
for i in range(1,int(math.sqrt(S))+3):
    if S%i == 0:
        koho.add(i)
        koho.add(S//i)

koho = sorted(list(koho))
ans = 0
for k in koho:
    AA_modk = sorted(AA%k)
    #print(k,AA_modk)

    Ln = Rn = 0
    L = 0
    R = N-1
    while L <= R:
        if Ln <= Rn:
            Ln += AA_modk[L]
            L += 1
        else:
            Rn += k - AA_modk[R]
            R -= 1

    #print(Ln,Rn)

    if K >= Ln:
        ans = max(k,ans)

print(ans)


Measured memory_bytes: 12500
#include<bits/stdc++.h>
  #define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  #define range(i,l,h) for(int i=l;i<h;i++)
  #define endl '\n'
  #define I INT_MAX
  #define L INT_MIN
  #define pb push_back
  #define ll long long
  #define ull unsigned long long
  #define vi vector<int>
  using namespace std;
  using std::ios;
  constexpr int MOD=1e9+7;
  constexpr int mod=998244353;

  int main()
  {
    fastio;    
    int n;
    cin>>n;
    vector<int> a(n);
    range(i,0,n)
    {
      cin>>a[i];
    }

    ll sum=1000,st=0;
    for(int i=0;i<n-1;i++)
    {
      if(a[i]<a[i+1])
      {
        st+=(sum/a[i]);
        sum=sum%a[i];
      }
      else if(a[i]>a[i+1])
      {
        sum+=(st*a[i]);
        st=0;
      }
    }

    if(st>0&&a[n-1]>=a[n-2])
      sum+=(st*a[n-1]);

    cout<<sum;
  }
    

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

int gcd(int n, int m) {
    int r;

    while(m % n != 0) {
        r = m;
		m = n % m;
		n = r;
    }

    return n;
}

int main() {
    int n, m = 2;

    cin >> n;

    cout << m * n / gcd(m, n);

    return 0;
}

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

using namespace std;

#define int long long
#define vi vector <int>
#define all(v) v.begin(), v.end()
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define forn(i, from, n) for (int i = (int)(from); i < (int)(n); ++i)

const int INF = 1e9 + 9;

void updMx(int &a, int b){
    if (a < b) a = b;
}

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

#ifdef LOCAL
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif

    int n, W;
    cin >> n >> W;
    vi wei(n + 1), cost(n + 1);
    forn(i, 1, n + 1)
        cin >> wei[i] >> cost[i];
    vector <vi> dp(n + 1, vi(W + 1, 0));
    forn(i, 1, n + 1){
        forn(w, 0, wei[i])
            dp[i][w] = dp[i - 1][w];
        forn(w, wei[i], W + 1){
            dp[i][w] = dp[i - 1][w];
            updMx(dp[i][w], dp[i - 1][w - wei[i]] + cost[i]);
        }
    }
    int ans = 0;
    forn(i, 0, W + 1)
        updMx(ans, dp[n][i]);
    cout << ans;
    return 0;
}

Measured memory_bytes: 80256
N = int(input())
S = input()
ary = []
if S[0] == '(':
    ary.append(1)
else:
    ary.append(0)
    ary.append(1)
for i in range(1, N):
    if S[i-1] == S[i]:
        ary[-1] += 1
    else:
        ary.append(1)
if len(ary) % 2:
    ary.append(0)
c = [0, 0]
for i in range(0, len(ary), 2):
    c[0] += ary[i]
    c[1] += ary[i+1]
    if c[0] < c[1]:
        ary[0] += c[1]-c[0]
        c[0] = c[1]
if c[0] > c[1]:
    ary[-1] += c[0]-c[1]
ans = ''
for i, n in enumerate(ary):
    if i % 2 == 0:
        ans += '('*n
    else:
        ans += ')'*n
print(ans)


Measured memory_bytes: 38256
from math import factorial
a = 0
b = 0
n, m = map(int,input().split())
if 1 < n:
  a = factorial(n) / factorial(2) / factorial(n - 2)
if 1 < m:
  b = factorial(m) / factorial(2) / factorial(m - 2)
print(int(a+b))

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

int main()
{
    int n,w;
    cin>>n>>w;
    int arr[n+1][2];
    for(int i=0;i<n;i++)cin>>arr[i][0]>>arr[i][1];
    ll dp[n+2][w+1];
    memset(dp,0,sizeof dp);

    for(int i=1;i<=n;i++){
        for(int j=1;j<=w;j++){
           if(j>=arr[i-1][0])dp[i][j]=max(arr[i-1][1]+dp[i-1][j-arr[i-1][0]],dp[i-1][j]);
           else dp[i][j]=dp[i-1][j];
        }
    }
    cout<<dp[n][w];
    return 0;
}


Measured memory_bytes: 79872
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <math.h>
#include <map>
#include <queue>
#include <set>
#include <stack>
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
typedef long long ll;
using namespace std;
const int MAXN=2e5+50;
const int inf=0x3f3f3f3f;
const int M=5000*4;
char ch[MAXN];
int cnt[MAXN];
int main()
{
int b[3][3];
int a[3][3]={0};
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
cin>>b[i][j];
int n;
cin>>n;
for(int i=0;i<n;i++)
{
    int x;
    cin>>x;
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        {
            if(b[i][j]==x)
            a[i][j]=1;
            
        }
    }
}


if((a[0][0]==1&&a[0][1]==1&&a[0][2]==1)||(a[1][0]==1&&a[1][1]==1&&a[1][2]==1)||(a[2][0]==1&&a[2][1]==1&&a[2][2]==1)||(a[0][0]==1&&
a[1][0]==1&&a[2][0]==1)||(a[0][1]==1&&a[1][1]==1&&a[2][1]==1)||(a[0][2]==1&&a[1][2]==1&&a[2][2]==1)||(a[0][0]==1&&a[1][1]==1&&a[2][2]==1
)||(a[2][0]==1&&a[1][1]==1&&a[0][2]==1))

cout<<"Yes";
else
cout<<"No";



    
 return 0;
 
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

int main() {
    int n;
    cin >> n;

    vector<ll> dp(n+1, 0);

    dp[0] = 0;
    dp[1] = 1;

    for ( int i = 1; i <= n; i++ ) {
        ll tmp_num = 6;
        ll tmp_min6 = 1e9;
        while(1) {
            if ( tmp_num > i ) break;
            tmp_min6 = min(tmp_min6, dp[i - tmp_num] + 1);
            tmp_num *= 6;
        }
        ll tmp_min9 = 1e9;
        tmp_num = 9;
        while(1) {
            if ( tmp_num > i ) break;
            tmp_min9 = min(tmp_min9, dp[i - tmp_num] + 1);
            tmp_num *= 9;
        }
        ll tmp_min = min(tmp_min6, tmp_min9);
        dp[i] = min(dp[i-1]+1, tmp_min);
    }

//    for ( int i = 0; i <= n; i++ ) {
//        cout << i << " " << dp[i] << endl;
//    }

    cout << dp[n] << endl;


    return 0;
}

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

bool solve(){
    string s, t;
    cin >> s >> t;
    reverse(s.begin(), s.end());
    for(auto c : s){
        if(c == 'J'){
            t.insert(t.begin(), t.back());
            t.pop_back();
        }
        if(c == 'C'){
            t.push_back(t.front());
            t.erase(t.begin());
        }
        if(c == 'E'){
            string tmp;
            tmp.insert(tmp.end(),t.begin()+(t.size()+1)/2,t.end());
            if(int(t.size())%2) tmp.push_back(t[t.size()/2]);
            tmp.insert(tmp.end(),t.begin(), t.begin()+t.size()/2);
            t = tmp;
        }
        if(c == 'A'){
            reverse(t.begin(), t.end());
        }
        if(c == 'P'){
            for(auto& d : t){
                if(d >= '0' && d <= '9') d = (d-'0'+9)%10+'0';
            }
        }
        if(c == 'M'){
            for(auto& d : t){
                if(d >= '0' && d <= '9') d = (d-'0'+1)%10+'0';
            }
        }
    }
    cout << t << endl;
    return true;
}

int main(){
    int t; cin >> t; for(;t>0;t--) solve();
    return 0;
}


Measured memory_bytes: 3136
#include<iostream>
#include<vector>
#include<algorithm>

int main(void){
    long long int n;
    std::cin >> n;
    std::vector<long long int> A(n);

    for(long long int i = 0; i < n; i++){
	std::cin >> A[i];
    }
    std::sort(A.begin(), A.end(), std::greater<long long int>());

    long long int ans = A[0];
    long long int num = (n - 2) / 2;
    for(long long int i = 0; i < num; i++){
	ans += 2 * A[1 + i];
    }
    if(n % 2 == 1) ans += A[1 + num];

    std::cout << ans << std::endl;

    return 0;
}


Measured memory_bytes: 4836
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define reps(i,a,b) for(int i=a;i<b;++i)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
template<typename T> inline bool chmax(T &a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T> inline bool chmin(T &a,T b){if(b<a){a=b;return 1;}return 0;}
template<typename T> vector<T> make_vec(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>
auto make_vec(size_t a,Ts... ts){return vector<decltype(make_vec<T>(ts...))>(a,make_vec<T>(ts...));}
template<typename T,typename U,typename... V>
typename enable_if<is_same<T,U>::value>::type fill_v(U &u,const V... v){u=U(v...);}
template<typename T,typename U,typename... V>
typename enable_if<!is_same<T,U>::value>::type fill_v(U &u,const V... v){for(auto &e:u)fill_v<T>(e,v...);}

struct dice {
    vector<int> label;
    dice(vector<int> &label) : label(label) {}
    void to_e() {
        int tmp = 0;
        swap(label[0], tmp);
        swap(label[2], tmp);
        swap(label[5], tmp);
        swap(label[3], tmp);
        swap(label[0], tmp);
    }
    void to_n() {
        int tmp = 0;
        swap(label[0], tmp);
        swap(label[4], tmp);
        swap(label[5], tmp);
        swap(label[1], tmp);
        swap(label[0], tmp);
    }
    void to_s() {
        int tmp = 0;
        swap(label[0], tmp);
        swap(label[1], tmp);
        swap(label[5], tmp);
        swap(label[4], tmp);
        swap(label[0], tmp);
    }
    void to_w() {
        int tmp = 0;
        swap(label[0], tmp);
        swap(label[3], tmp);
        swap(label[5], tmp);
        swap(label[2], tmp);
        swap(label[0], tmp);
    }
    int top() { return label[0];}
};

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

    vector<int> label(6);
    rep(i, 6) cin >> label[i];
    dice d(label);
    string s;
    cin >> s;
    rep(i, sz(s)) {
        if (s[i] == 'E') d.to_e();
        else if (s[i] == 'N') d.to_n();
        else if (s[i] == 'S') d.to_s();
        else d.to_w();
    }
    cout << d.top() << endl;
}



Measured memory_bytes: 3196
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
const ll MOD = 1e9 + 7 ;
const ll dx[4] = { -1,1,0,0 };
const ll dy[4] = { 0,0,-1,1 };
const ll MAX =  3e6 ;
#define pb push_back
#define f first
#define s second
#define all(v) v.begin(),v.end()
long long gcd(long long  a, long long  b) { return (b == 0 ? a : gcd(b, a % b)); }
ll n , m , x ,y, k , Q , ans ; string s,t;
ll dp[2][MAX];
vector < vector < int > > g ;

ll solve(int u , int parent = -1,int cur = 0){

     ll &ret = dp[cur][u];

     if(~ret)
        return ret;

     ret = 1LL ;

     for(auto v : g[u])
        if(v != parent){
            if(cur == 0)
                ret = (ret%MOD * 1LL * (solve(v,u,0)%MOD + solve(v,u,1)%MOD)%MOD)%MOD;
            else
                ret = (ret%MOD * 1LL *  solve(v,u,0)%MOD)%MOD;
        }

    return ret;

}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);  cout.tie(0);
//   freopen("test.in","r",stdin);

    cin>>n;

    g.clear();
    g.resize(n + 1);

    for(int i = 0 ; i < n - 1 ; ++i){
        int u,v;
        cin>>u>>v;
        --u; --v;
        g[u].pb(v);
        g[v].pb(u);
    }

    for(int i = 0 ; i < n ; ++i)
        for(int j = 0 ; j < 2 ; ++j)
            dp[j][i] = -1 ;

    cout<<(solve(0,-1,0) + solve(0,-1,1))%MOD<<'\n';

    return 0;
}


Measured memory_bytes: 18304
#include<stdio.h>
   
   int main(void)
   {
           int n=0,s=0;
           char c;
   
           while(scanf("%c",&c)!=EOF)
           {
                  if((c=='A')||(c=='G')||(c=='T')||(c=='C')){
                          n=n+1;
                  }
                  else if(s<n){
                          s=n;
                          n=0;
                  }
          }
  
          printf("%d\n",s);
          return 0;
  }
  


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

int main() {
  string s, t;
  cin >> s >> t;
  int count=0;
  for (int i=0;i<s.size();i++){
    if(s.at(i)!=t.at(i)){
      count++;
    }
   }
   cout << count << endl;
  
}


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

using namespace std;

int n,have[100];
string t;

int main() {
  //  freopen("in.txt","r",stdin);
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>t;
    int n = t.size();
    for (int i=0;i<n;i++) have[t[i]-'a']=1;
    for (char ch = 'a';ch <= 'z'; ch++)
      if (!have[ch-'a']) {
          cout<<t<<ch<<endl;
          return 0;
      }
    memset(have,0,sizeof(have));
    string ans;
    for (int i = n-2;i>=0;i--) {
        ans="";
        for (int j=0;j<i;j++) {
            ans+=t[j];
            have[t[j]-'a']=1;
        }
        for (char ch = 'a';ch <= 'z';ch++)
          if (!have[ch-'a'] && ch > t[i]) {
              ans += ch;
              cout<<ans;
              return 0;
          }
        memset(have,0,sizeof(have));
    }
    cout<<-1;
}


Measured memory_bytes: 256
s=input()
t=input()
u=[]
for i in range(len(s)-len(t)+1):
  for j in range(len(t)):
    if s[i+j]!='?' and s[i+j]!=t[j]:
      break
  else:
    u.append(s[:i].replace('?','a')+t+s[i+len(t):].replace('?','a'))
if len(u)==0:
  print('UNRESTORABLE')
  exit()
u.sort()
print(u[0])

Measured memory_bytes: 38384
using System;

class ColorfulSlimes
{
	static public void Main(string[] args)
	{
		int N, x;
		string[] vals = Console.ReadLine().Split(' ');

		N = int.Parse(vals[0]);
		x = int.Parse(vals[1]);
		vals = Console.ReadLine().Split(' ');
		int[] a = new int[N+1];
		for(int i=1; i<=N; i++)
			a[i] = int.Parse(vals[i-1]);

		int[,] b = new int[N+1,N];
		for(int i=1; i<=N; i++)
		{
			b[i,0] = a[i];
		}
		for(int i=1; i<=N; i++)
		{
			for(int k=1; k<=N-1; k++)
			{
				int j;
				if(i - k >= 1)
					j = i - k;
				else
					j = i - k + N;
				b[i,k] = Math.Min(b[i,k-1], a[j]); 
			}
		}

		long minTime = long.MaxValue;
		for(int k = 0; k <= N-1; k++)
		{
			long t = 0;
			for(int i=1; i <= N; i++)
			{
				t += b[i,k];
			}
			t += (long)k * x;
			if(t < minTime)
			{
				minTime = t;
			}
		}
		Console.WriteLine(minTime);	
	}

}


Measured memory_bytes: 28768
#include<bits/stdc++.h>
 
using namespace std;
 
#define debug(x) cout << (#x) << " is " << x << endl;
#define Q int t; scanf("%d", &t); for(int q=1; q<=t; q++)
typedef long long int lli;
typedef pair<int, int> pi;
 
#define N 300005
int H[N], W[N];
 
int main()
{
    int h, w, m, hmx=0, wmx=0;
    cin >> h >> w >> m;
    vector<pi> p;
    for(int i=0; i<m; i++){
		int x, y;
		cin >> x >> y;
		H[x]++;
		W[y]++;
		p.push_back({x, y});
		hmx = max(hmx, H[x]);
		wmx = max(wmx, W[y]);
	}
	lli hc=0, wc=0;
	for(int i=1; i<=h; i++) hc += (H[i] == hmx);
	for(int i=1; i<=w; i++) wc += (W[i] == wmx);
	
	lli cc = 0;
	for(auto el: p){
		if(H[el.first]==hmx && W[el.second]==wmx) cc++;
	}
	if(cc == hc*wc){
		cout << hmx+wmx-1 << endl;
	}
	else
		cout << hmx+wmx << endl;
		
 
    return 0;
}

Measured memory_bytes: 9808
main = do
    (n:as) <- map read . words <$> getContents :: IO [Int]
    print $ if check as then solve as else (-1)

check as = head as == 0 && and (zipWith f as (tail as))
    where f a b | a + 1 >= b = True
                  | otherwise = False

solve as = fst $ foldl f (0,0) as
    where f (s,a) b | a + 1 == b = (s+1,b)
                    | otherwise = (s+b,b)

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

int main(){
    int N;
    cin >> N;
    vector<int> vec(N);
    for (int i = 0; i < N; i++){
        cin >> vec.at(i);
    }
    sort(vec.begin(),vec.end());
    int ans = vec.at((N + 1)/2) - vec.at((N + 1)/2 - 1);
    cout << ans << endl;
}


Measured memory_bytes: 640
package main

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

func main() {
	sc.Split(bufio.ScanWords)
	n := nextInt()

	s := make([]int, n)
	m := make(map[int]int, n)
	for i := range s {
		var v int
		if i == 0 {
			s[i] = 1
			m[0] = 0
		} else {
			s[i] = s[i-1] + 1
			v = nextInt()
		}
		if _, ok := m[v]; ok {
			m[v] += 1
		} else {
			m[v] = 1
		}
	}

	for _, v := range s {
		if v, ok := m[v]; ok && v != 0 {
			fmt.Println(v)
		} else {
			fmt.Println("0")
		}
	}
}

// =================================
// I/O util
// =================================

var sc = bufio.NewScanner(os.Stdin)

func nextLine() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

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

Measured memory_bytes: 12216
#include<bits/stdc++.h>
using namespace std;
#define mods 1000000007
#define pb push_back
#define mp make_pair
#define st first
#define nd second
typedef long long int lint;
typedef unsigned long long int ulint;
list <lint> gelen[100020],giden[100020];
lint dp[100020];
bool hes[100020];
lint hesap(lint a);
lint n,m;
int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    lint i,j,cev=0,a,b,k,l;
	cin>>n>>m;
	for(i=0;i<m;i++){
		cin>>a>>b;
		gelen[b].pb(a);
		giden[a].pb(b);
	}
	for(i=1;i<=n;i++){
		if(gelen[i].size()==0){
			cev=fmax(cev,hesap(i));
		}
	}
	cout<<cev;
	
	
	
	return 0;
}
lint hesap(lint a){
	if(hes[a]==true) return dp[a];
	hes[a]=true;
	lint cev=0;
	if(giden[a].size()==0){
		dp[a]=0;
		return 0;
	}
	list <lint> :: iterator it;
	for(it=giden[a].begin();it!=giden[a].end();it++){
		cev=fmax(cev,hesap(*it)+1);
	}
	dp[a]=cev;
	return cev;
}

Measured memory_bytes: 15232
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(n, m, s, t, UVAB):
    g = defaultdict(list)
    for u, v, a, b in UVAB:
        g[u].append((v, (a, b)))
        g[v].append((u, (a, b)))

    def d(s, ck):
        dist = [0 if s == i else sys.maxsize for i in range(n+1)]
        # p = [None for i in range(n+1)]
        q =[]
        heapq.heappush(q, (dist[s], s))
        while q:
            c, u = heapq.heappop(q)
            if dist[u] > c:
                continue
            for v, cost in g[u]:
                alt = dist[u] + cost[ck]
                if dist[v] > alt:
                    dist[v] = alt
                    heapq.heappush(q, (alt, v))
        return dist

    dist0 = d(s, 0)
    dist1 = d(t, 1)

    ans = [sys.maxsize] * (n+1)
    
    for i in range(n-1, -1, -1):
        # print(i)
        ans[i] = min(ans[i+1], dist1[i+1] + dist0[i+1])
    c = 10**15
    return '\n'.join(map(lambda x: str(c-x), ans[:-1]))


def main():
    n, m, s, t = read_int_n()
    UVAB = [read_int_n() for _ in range(m)]

    
    print(slv(n, m, s, t, UVAB))


if __name__ == '__main__':
    main()


Measured memory_bytes: 97720