akhauriyash/Code-Regression huggingface dataset:
module mod_two_dim_merge_sort
  implicit none
  integer, private, parameter :: intkind = 8
contains
  logical function less(a, b) result(res)
    integer(intkind), intent(in) :: a(:), b(:)
    real(8) :: a1, b1
    a1 = a(1) / real(a(2) + 1, 8)
    b1 = b(1) / real(b(2) + 1, 8)
    res = a1 > b1 .or. (a1 == b1 .and. a(2) >= b(2))
  end
  subroutine merge_sort(a)
    integer(intkind), intent(inout) :: a(:, :)
    integer :: n, m, l, i, u
    n = size(a, 1)
    m = n
    l = 1
    do while (m > 1)
      do i = 1, m / 2
        u = min(2 * i * l, n)
        call merger(a(2 * (i - 1) * l + 1:(2 * i - 1) * l, :), &
        a((2 * i - 1) * l + 1:u, :))
      end do
      l = 2 * l
      m = (m + 1) / 2
    end do
  end
  subroutine merger(a1, a2)
    integer(intkind), intent(inout) :: a1(:, :), a2(:, :)
    integer(intkind) :: a(size(a1, 1) + size(a2, 1), size(a1, 2))
    integer :: i1, i2, n1, n2
    i1 = 1
    i2 = 1
    n1 = size(a1, 1)
    n2 = size(a2, 1)
    do while (i1 <= n1 .and. i2 <= n2)
      if (less(a1(i1, :), a2(i2, :))) then
        a(i1 + i2 - 1, :) = a1(i1, :)
        i1 = i1 + 1
      else
        a(i1 + i2 - 1, :) = a2(i2, :)
        i2 = i2 + 1
       end if
    end do
    if (i1 <= n1) then
      a(i1 + i2 - 1:n1 + n2, :) = a1(i1:n1, :)
    else
      a(i1 + i2 - 1:n1 + n2, :) = a2(i2:n2, :)
    end if
    a1 = a(1:n1, :)
    a2 = a(n1 + 1:n1 + n2, :)
  end
end module mod_two_dim_merge_sort
program manga_market
  use mod_two_dim_merge_sort
  implicit none
  integer(8), parameter :: inf = 3e18
  integer, parameter :: k = 30
  integer :: n, l, i, j, m = 0
  integer(8) :: t, r, tmp
  integer(8), allocatable :: c(:, :), dp(:, :), s(:)
  read(*,*) n, t
  allocate(c(n, 2))
  do i = 1, n
    read(*,*) c(i, :)
  end do
  call merge_sort(c(1:n, 1:2))
  l = n + 1
  do while (c(l - 1, 1) == 0)
    l = l - 1
  end do
  allocate(dp(0:k, 0:l - 1), s(0:n - l + 1))
  dp = inf
  dp(0, :) = 0
  do i = 1, l - 1
    do j = 1, min(k, i)
      dp(j, i) = dp(j, i - 1)
      if (dp(j - 1, i - 1) > t) cycle
      tmp = dp(j - 1, i - 1) + 1
      dp(j, i) = min(dp(j, i), tmp + c(i, 1) * tmp + c(i, 2))
    end do
  end do
  s(0) = 0
  do i = n, l, -1
    s(n - i + 1) = s(n - i) + c(i, 2) + 1
  end do
  do i = 0, min(k, l - 1)
    r = t - dp(i, l - 1)
    if (r < 0) cycle
    do j = 0, n - l + 1
      if (s(j) > r) exit
      m = max(m, i + j)
    end do
  end do
  write(*,'(i0)') m
end program manga_market

Measured memory_bytes: 55340
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 998244353;
const ll INF = mod * mod;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef pair<ll, ll> LP;
typedef vector<ll> vec;
typedef vector<string> svec;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-8;

int p;
vec calc(int x) {
	vec ret(p);
	int r = 1;
	for (int i = p - 1; i >= 0; i--) {
		if (i == 0)r--;
		if (r < 0)r += p;
		ret[i] = r;
		r= r * x%p;
	}
	return ret;
}
int mod_inverse(int x, int m) {
	int ret = 1;
	int n = m - 2;
	while (n > 0) {
		if (n % 2)ret = ret * x%m;
		x = x * x%m; n >>= 1;
	}
	return ret;
}
int rinv[4000];
void init() {
	rinv[0] = 1;
	for (int i = 1; i < 4000; i++) {
		rinv[i] = rinv[i - 1] * mod_inverse(i,p)%p;
	}
}
void solve() {
	cin >> p; init();
	vector<int> a(p);
	rep(i, p) {
		cin >> a[i];
	}
	vec ans(p);
	rep(i, p) {
		vec u = calc(i);
		ll c = a[i];
		c = c * rinv[i] % p;
		c = c * rinv[p - 1 - i] % p;
		if ((p - 1 - i) % 2) {
			c = p - c; if (c == p)c = 0;
		}
		//cout<< i << endl;
		rep(j, p) {
			//cout << j << " " <<u[j] << endl;
			ans[j] = (ans[j] + c * u[j]) % p;
		}
	}
	rep(i, p) {
		if (i > 0)cout << " ";
		cout << ans[i];
	}
	cout << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	//init();
	solve();
	//cout << "finish" << endl;
	//stop
	return 0;
}


Measured memory_bytes: 512
n = int(input())
s = list(input())

ans = 0


for i in range(10):
    for j in range(10):
        for k in range(10):
            flag1 = 0
            flag2 = 0
            
            for l in range(n):
                if flag1 == 0 and s[l] == str(i):
                    flag1 = 1
                    continue
                
                if flag1 == 1 and flag2 == 0 and s[l] == str(j):
                    flag2 = 1
                    continue
                
                if flag1 == 1 and flag2 == 1 and s[l] == str(k):
                    ans += 1
                    break
                
print(ans)


Measured memory_bytes: 46428
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=sum(a)/(4*m)
count=0
for i in range(0,len(a)):
  if a[i]>=b:
    count=count+1
if count>=m:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  int l1,r1;
  int x = 0;
  cin >> N;
  
  for (int i=0; i<N; i++) {
    cin >> l1 >> r1;
  	x = x + r1 - l1 + 1;
  }
    
  cout << x << endl;
}

Measured memory_bytes: 256
n,k = map(int, input().split())
okashi = [0] * n
snuke = 0
for i in range(k):
    x = int(input())
    a = list(map(int, input().split()))
    for j in a:
        okashi[j-1] += 1
for i in range(n):
    if okashi[i] == 0:
        snuke += 1
print(snuke)

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

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

int min(int a,int b){
	if(a<b)return a;
	return b;
}

int compare_char(char *a,char *b){
	return strcmp(a,b);
}

int intsort(const void *a, const void *b){
	return *(int*)b - *(int*)a;
	/*qsort(a,aの配列数,sizeof(int),intsort);*/
}

int longsort(const void *a, const void *b){
	long *A=(long *)a;
	long *B=(long *)b;
	if(*A>*B) return -1;
	if(*A<*B) return 1;
	return 0;
}

int main(){
  int i,N,K,a[3];

  for(i=0;i<3;i++){
    scanf("%d",&a[i]);
  }
  qsort(a,3,sizeof(int),intsort);
  printf("%d\n",a[0]-a[2]);
  return 0;
}

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

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

using namespace std;

int main(){
  double temp,sum=0;

  rep(i,5) { cin >> temp; if( int(temp) < 40 ) temp = 40; sum += temp; }
  printf("%.0f\n",sum/5);
  return 0;
}

Measured memory_bytes: 1232
#include <iostream>
#include<bits/stdc++.h>
#define ll long long 

#define pb push_back
#define pii pair<int,int>
#define f(i,n) for(int i=0;i<n;i++)

using namespace std;
char arr[26];

void solve(){
	
	
	
	ll n;
	cin >> n;
	string res="";
	while(n!=0){
		int x = n%26;
		res = arr[x] + res;
		if(x==0) n--;
		
		n/=26;
	}	
	cout <<res <<endl;
}

int main() {
	
int i=1;
	for(char c='a';c <='z';c++){
		
		if(c=='z') arr[0]='z';
		else{
			arr[i]=c;
			i++;
		}
	}
	solve();
	    
	return 0;
}


Measured memory_bytes: 3568
#![allow(unused_imports)]

use std::cmp::{max, min, Ordering};
use std::collections::*;
use std::iter::once;
#[cfg(debug_assertions)]
include! {"./debug.rs"}

#[cfg(not(debug_assertions))]
macro_rules! debug {
    ($($arg:expr),*) => {};
}

macro_rules! read {
    ([$t:ident] ; $n:expr) =>
        ((0..$n).map(|_| read!([$t])).collect::<Vec<_>>());
    ([$t:ident]) =>
        (rl().split_whitespace().map(|w| read_type!(w, $t)).collect::<Vec<_>>());
    (_, [$t:ident] ; $n:expr) =>
        ((0..$n).map(|_| read!(_, [$t])).collect::<Vec<_>>());
    (_, [$t:ident]) =>
        (rl().split_whitespace().skip(1).map(|w| read_type!(w, $t)).collect::<Vec<_>>());
    ($($t:ident),+ ; $n:expr) =>
        ((0..$n).map(|_| read!($($t),+)).collect::<Vec<_>>());
    ($t:ident) => (read_type!(rl(), $t));
    ($($t:ident),*) => {{
        let buf = rl();
        let mut w = buf.split_whitespace();
        ($(read_type!(w.next().unwrap(), $t)),*)
    }};
}

macro_rules! read_type {
    ($s:expr, chars) => {
        $s.chars().collect::<Vec<char>>()
    };
    ($s:expr, usize1) => {
        read_type!($s, usize) - 1
    };
    ($s:expr, $t:ty) => {
        $s.parse::<$t>().unwrap()
    };
}

fn rl() -> String {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).unwrap();
    buf.trim_right().to_owned()
}

trait IteratorExt: Iterator + Sized {
    fn vec(self) -> Vec<Self::Item> {
        self.collect()
    }
}

impl<T: Iterator> IteratorExt for T {}

////////////////////////////////////////////////////////////////////////////////

fn main() {
    let s = read!(chars);

    if (s[0] == s[1] && s[2] == s[3]
        || s[0] == s[2] && s[1] == s[3]
        || s[0] == s[3] && s[1] == s[2])
        && !(s[0] == s[1] && s[0] == s[2])
    {
        println!("Yes");
    } else {
        println!("No");
    }
}


Measured memory_bytes: 4352
#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <iterator>
#include <assert.h>
#pragma warning(disable:4996) 
 
typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF 9223300000000000000
#define INF 2140000000
const long long MOD = 1000000007;
//const long long MOD = 998244353;

using namespace std;

char str[100005];

void solve()
{
    scanf("%s", str);
    int n = strlen(str);
    int K;
    scanf("%d", &K);
    ll sum = 0;
    int i;
    for (i = 0; i < n; i++) {
        int tmp = ('a'-str[i] + 26) % 26;
        if (sum + tmp <= K) {
            sum += tmp;
            str[i] = 'a';
        }
        else {
            continue;
        }
    }
    for (i = n-1; i >=0; i--) {
        int tmp = ('a'-str[i] + 26) % 26;
        if (sum + tmp <= K) {
            sum += tmp;
            str[i] = 'a';
        }
        else {
            continue;
        }
    }
    {
        int tmp = (str[n - 1] - 'a' + (K - sum)) % 26;
        str[n - 1] = 'a' + tmp;
    }
    printf("%s\n", str);
    
    return;
}

int main(int argc, char* argv[])
{
#if 1
    solve();
#else
    int T; scanf("%d", &T);
    while(T--) {
        solve();
    }
#endif
    return 0;
}


Measured memory_bytes: 384
#include <algorithm>
#include <iostream>
#include <deque>

using namespace std;

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

  deque<long> LDS;
  for (size_t n = 0; n < N; ++n) {
    long A;
    cin >> A;
    auto it = lower_bound(LDS.begin(), LDS.end(), A);
    if (it == LDS.begin()) LDS.push_front(A);
    else *(--it) = A;
  }
  cout << LDS.size() << endl;
  
  return 0;
}


Measured memory_bytes: 1024
#include<stdio.h>
#include<math.h>
double d,r,s,z[6];
int n,i,j,a[50];
int main(){
	for(scanf("%d",&n);n--;){
		for(i=0;i<6;i++)
			scanf("%lf",z+i);
		r=z[2];
		s=z[5];
		d=hypot(*z-z[3],z[1]-z[4]);
		printf("%d\n",a[j++]=d>r+s?0:r>d+s?2:s>d+r?-2:1);
	}
	
	i=a[1];
	if(i==2)return 1;
	if(i==-2)while(1);
	return i==0;
}

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

long long numoffactors(int n)
{
	if (n==1) return 1;
	long long ret=0;
	for (int i=1;i<sqrt(n);i++)
	{
		if (n%i==0) ret+=2;
	}
	if ( (long long)sqrt(n)==sqrt(n)) ret+=1;
	return ret;
}

int main(){
	int n;
	cin >> n;
	long long res=0;
	for (int i=1;i<=n-1;i++)
		res+=numoffactors(n-i);
	cout << res;
}

Measured memory_bytes: 3680
# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect
def s():
    return input()

S = s()
count = 0
abc = 'abcdefghijklmnopqrstuvwxyz'
if S[0] == 'A':
    if S[1] in abc:
        for i in range(1,len(S)-1):
            if S[i] in abc:
                continue
            elif S[i] == 'C':
                count += 1
            else:
                print('WA')
                exit()
        if S[-1] in abc and count == 1:
            print('AC')
            exit()

print('WA')


Measured memory_bytes: 5416
const main = (inputs) => {
  for (var i = 0; i < inputs[0].length; i++) {
    if (inputs[0][i] == 7) {
      console.log('Yes');
      return false;
    }
  }
  console.log('No');
}
main(require('fs').readFileSync('/dev/stdin', 'UTF-8').trim().split("\n"));

Measured memory_bytes: 29628
#include<iostream>
using namespace std;
int main(){
    int H,W;
    while(1){
        cin>>H>>W;
        if(H==0&&W==0)break;
        for(int i=0;i<H;i++){
            for(int j=0;j<W;j++){
                if(i==0||i==H-1||j==0||j==W-1)cout<<'#';
                else cout<<'.';
            }
            cout<<endl;
        }
        cout<<endl;
    }
    return 0;
}


Measured memory_bytes: 3100
import statistics
def main():
    N = int(input())
    A = []
    B = []
    for i in range(N):
        a, b = [int(_n) for _n in input().split()]
        A.append(a)
        B.append(b)
    a = statistics.median(A)
    b = statistics.median(B)
    # print(a,b)
    if N % 2 == 0:
        print(int(2 * (b-a))+1)
    else:
        print(int(b-a)+1)


main()

Measured memory_bytes: 113348
#include <bits/stdc++.h>
#define f first
#define s second
#define MOD 1000000007
#define PMOD 998244353
#define pb(x) push_back(x)
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> plii;
typedef pair<int, pii> piii;
const int INF = 1e9+10;
const ll LINF = 1LL*INF*INF;
const int MAXN = 2e5+10;
const int MAXM = 5e3+10;

priority_queue<int> pq;
vector<vector<pii> > graph;
queue<int> que;

int ans[MAXN];

bool visited[MAXN];

void dfs(int here,int val)
{
    visited[here] = true;

    int there;

    ans[here] = val;

    for(int i=0;i<graph[here].size();i++)
    {
        there = graph[here][i].f;
        if(visited[there])continue;
        if(graph[here][i].s&1)dfs(there,(1^val));
        else dfs(there,val);
    }
    return;
}

int main()
{
    int n,m,k,a,b,x,y,q;
    int sum = 0;
    int cnt = 0;
    int mx = 0;
    int mn = INF;
    int cur = 0, idx = -1;

    cin>>n;

    graph = vector<vector<pii> > (n+1);

    for(int i=1;i<n;i++)
    {
        cin>>x>>y>>a;
        graph[x].push_back(pii(y,a));
        graph[y].push_back(pii(x,a));
    }

    dfs(1,0);

    for(int i=1;i<=n;i++)
        cout<<ans[i]<<"\n";

    return 0;
}


Measured memory_bytes: 8320
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
ans = 0
AB.sort()
i=0
while(M>0):
  if AB[i][1] <= M:
    ans += AB[i][0]*AB[i][1]
    M -= AB[i][1]
    i += 1
  else:
    ans += AB[i][0] * M
    M = 0
print(ans)

Measured memory_bytes: 60760
#include <math.h>
#include <stdio.h>

int main(void)
{
  int i, n,m; scanf( "%d %d", &n, &m );
  int a[m], sum = 0;
  for(i = 0;i < m;i++) { scanf( "%d", &a[i] ); }
  for(i = 0;i < m;i++) { sum += a[i]; }
  if( n - sum < 0 ) { printf( "-1\n" ); }
  else { printf( "%d\n", n - sum );}
  return 0;
}

Measured memory_bytes: 1760
#include <stdio.h>

char s[100001];

int main(void)
{
	int n;
	char a, b, c;

	a = 0;
	b = 1;
	c = 2;

	scanf("%s", s);
	for (n = 0; s[n]; ++n)
	{
		a = s[n];
		if (a == b || a == c || b == c)
		{
			if (n < 2)
			{
				printf("1 2\n");
			}
			else
			{
				printf("%d %d\n", n - 1, n + 1);
			}
			return 0;
		}
		c = b;
		b = a;
	}

	printf("-1 -1\n");

	return 0;
}

Measured memory_bytes: 1808
N = int(input())
S = input()

eastNumber = S.count('E')
westNumber = 0
minimum = N

for i in range(N):
    if S[i] == 'E':
        eastNumber -= 1
        number = eastNumber + westNumber
        if minimum > number:
            minimum = number
    else:
        number = eastNumber + westNumber
        if minimum > number:
            minimum = number
        westNumber += 1

print(minimum)

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

// vector<tuple<long,long>> items; // (value, weight)
// auto item = items[i];
// long v = get<0>(item);
// long w = get<1>(item);
// long v, w;
//   for( int i = 0; i < N; i++ ){
//     cin >> v >> w;
//     items.push_back( make_tuple(v, w) ); // item : (value, weight)
//   }

int main(){
    int N;
    vector< tuple<string, int, int> > R;
    cin >> N;
    for(int i=0; i<N; i++){
        string s;
        int p;
        cin >> s >> p;
        R.push_back( make_tuple(s,p, i+1) ); 
    }
    sort(R.begin(), R.end(), 
    [](tuple<string, int, int> R1, tuple<string, int, int> R2){
        if(get<0>(R1) != get<0>(R2)) return get<0>(R1) < get<0>(R2);
        return get<1>(R1) > get<1>(R2);
    });

    // for(int i=0; i<N; i++){
    //     cout << get<0>(R[i]) << " " << get<1>(R[i]) << " " << get<2>(R[i]) << endl;
    // }

    for(int i=0; i<N; i++){
        cout << get<2>(R[i]) << endl;
    }
}

Measured memory_bytes: 256
using System;
 
namespace BoxAndBall {
    class Program {
        static void Main(string[] args) {
            int N, M, A = 0;
            string[] str = Console.ReadLine().Split(' ');
            N = int.Parse(str[0]);
            M = int.Parse(str[1]);
            int[,] ball = new int[N,2];
            for (int i = 0; i < N; i++) {
                ball[i,0] = 1;
                ball[i, 1] = 0;
            }
            ball[0, 1] = 1;
            for (int i = 0; i < M; i++) {
                string[] tmp = Console.ReadLine().Split(' ');
                var a = int.Parse(tmp[0]);
                var b = int.Parse(tmp[1]);
                if (ball[a - 1, 1] == 1) {
                    ball[b - 1, 1] = 1;
                }
                ball[a-1,0]--;
                ball[b-1,0]++;
                if (ball[a - 1, 0] < 1) {
                    ball[a - 1, 1] = 0;
                }
            }
            for(int i = 0; i < N; i++) {
                if (ball[i, 1] == 1)
                    A++;
            }
            Console.WriteLine(A);
        }
    }
}

Measured memory_bytes: 7512
import math
import fractions
N=int(input())
A=math.sqrt(N)
A=math.ceil(A)
mini=100000000000
for i in range(1,A+1):
    if N%i==0:
        x=len(str(i))
        y=len(str(N//i))
        if mini>max(x,y):
            mini=max(x,y)
print(mini)


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

int main(){
    int mod=1000000007;
    int n,k;
    scanf("%d %d",&n,&k);
    vector<int> x(n),y(n);
    vector<int> xary,yary;

    for (int i=0;i<n;++i) {
        scanf("%d %d",&x[i],&y[i]);
        xary.push_back(x[i]);
        yary.push_back(y[i]);
    }
    sort(begin(xary), end(xary));
    sort(begin(yary), end(yary));
    long long ans=1ll*(xary[n-1]-xary[0])*(yary[n-1]-yary[0]);
    for (int xi=0;xi<n;++xi) {
        for (int xj=xi+1;xj<n;++xj) {
            for (int yi=0;yi<n;++yi) {
                for (int yj=yi+1;yj<n;++yj) {
                    int num=0;
                        long long lx=xary[xi],rx=xary[xj];
                        long long by=yary[yi],uy=yary[yj];
                        for (int i=0;i<n;++i) if(lx<=x[i] and x[i]<=rx and by<=y[i] and y[i]<=uy) num++;
                        if (num>=k) ans=min(ans,1ll*(rx-lx)*(uy-by));
                }
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] l = new int[3];
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < 3; ++j) {
				l[j] = sc.nextInt();
			}
			Arrays.sort(l);
			System.out.println(l[0] * l[0] + l[1] * l[1] == l[2] * l[2] ? "YES" : "NO");
		}
		sc.close();
	}
}


Measured memory_bytes: 32616
/*
 * r s p グーチョキパー
 */

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		int K = scan.nextInt();
//		Scanner scan1 = new Scanner(System.in);
		int R = scan.nextInt();
		int S = scan.nextInt();
		int P = scan.nextInt();
//		Scanner scan2 = new Scanner(System.in);
		String a = scan.next();
		String array[] = a.split("");
		MustVictoryJanken(array,N);
		EfficentPointJanken(array,N,K);
		System.out.print(SumPint(array,N,R,S,P));

		/* デバック用
		for(int i = 0; i < N; i++) {
			System.out.print(array[i]);
		}
		*/

	}

	/*
	 * 必ずじゃんけんに勝利するパターン
	 */
	public static void MustVictoryJanken(String array[],int N) {
		for(int i = 0; i < N; i++) {
			if(array[i].equals("r")) {
			array[i] = "p";
			}else if(array[i].equals("s"))  {
			array[i] = "r";
			}else if(array[i].equals("p"))  {
			array[i] = "s";
			}
		}
	}

	/*
	 * K回前とかぶらないようにじゃんけんして最も得点が高くなるパターン
	 */
	public static void EfficentPointJanken(String array[],int N,int K) {
		for(int i=1; i < N; i++) {
		//もし回前がマイナスにならない場合
			if(i - K > -1) {
				if(array[i] == array[i - K]) {
				array[i] = "あいこ";
				}
			}
		}
	}

	public static int SumPint(String array[],int N,int R,int S,int P) {
		int sum = 0;
		for(int i=0; i<N; i++) {
			switch(array[i]) {
			case "r":
				sum += R;
				break;
			case "s":
				sum += S;
				break;
			case "p":
				sum += P;
				break;
			}
		}
		return sum;
	}


}


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

using namespace std;

int main(int arc, char **argv)
{
	unsigned int N;
	vector<unsigned char> nmbrs;
	for (cin >> N; N > 0; --N)
	{
		unsigned long long a;
		cin >> a;
		nmbrs.push_back(a % 4);
	}
	int nuller = count(nmbrs.begin(), nmbrs.end(), 0);
	int einser = count(nmbrs.begin(), nmbrs.end(), 1);
	int zweier = count(nmbrs.begin(), nmbrs.end(), 2);
	int dreier = count(nmbrs.begin(), nmbrs.end(), 3);
	cerr << nuller << " " << einser << " " << zweier << " " << dreier << endl;
	if ((einser + dreier + (zweier > 0 ? 1 : 0) - nuller) > 1)
	{
		cout << "No\n";
	}
	else
	{
		cout << "Yes\n";
	}
	return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#include <stack>
#include <queue>
#include <string>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <iterator>

using namespace std;


int main()
{
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	cout << (n / 2 + n % 2);
	
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#define MAX 10000
#define NIL -1

struct Node {
  int parent = NIL, left = NIL, right = NIL;
};

void pre_order_print(Node nodes[], int u) {
  if (u == NIL) return;
  printf(" %d", u);
  pre_order_print(nodes, nodes[u].left);
  pre_order_print(nodes, nodes[u].right);
}

void in_order_print(Node nodes[], int u) {
  if (u == NIL) return;
  in_order_print(nodes, nodes[u].left);
  printf(" %d", u);
  in_order_print(nodes, nodes[u].right);
}

void post_order_print(Node nodes[], int u) {
  if (u == NIL) return;
  post_order_print(nodes, nodes[u].left);
  post_order_print(nodes, nodes[u].right);
  printf(" %d", u);
}

int main() {
  int n, i, p, l, r, root;
  scanf("%d", &n);

  Node nodes[n];
  for (i = 0; i < n; i++) {
    scanf("%d %d %d", &p, &l, &r);
    nodes[p].left = l;
    nodes[p].right = r;

    if (l != NIL) nodes[l].parent = p;
    if (r != NIL) nodes[r].parent = p;
  }

  for (i = 0; i < n; i++) {
    if (nodes[i].parent == NIL) root = i;
  }

  printf("Preorder\n");
  pre_order_print(nodes, root);
  printf("\n");

  printf("Inorder\n");
  in_order_print(nodes, root);
  printf("\n");

  printf("Postorder\n");
  post_order_print(nodes, root);
  printf("\n");

  return 0;
}



Measured memory_bytes: 2732
#!usr/bin/env pypy3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def I(): return int(sys.stdin.readline())


def LS(): return [list(x) for x in sys.stdin.readline().split()]


def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res


def IR(n):
    return [I() for i in range(n)]


def LIR(n):
    return [LI() for i in range(n)]


def SR(n):
    return [S() for i in range(n)]


def LSR(n):
    return [LS() for i in range(n)]


sys.setrecursionlimit(1000000)


def main():
    N, X, Y = LI()
    X -= 1
    Y -= 1
    dist = [[N] * N for _ in range(N)]

    q = deque()
    for i in range(N):
        q.append(i)
        dist[i][i] = 0
        while q:
            u = q.popleft()
            t = dist[i][u] + 1
            if u < N - 1:
                if dist[i][u + 1] > t:
                    q.append(u + 1)
                    dist[i][u + 1] = t
            if u >= 1:
                if dist[i][u - 1] > t:
                    q.append(u - 1)
                    dist[i][u - 1] = t
            if u == X:
                if dist[i][Y] > t:
                    q.append(Y)
                    dist[i][Y] = t
            if u == Y:
                if dist[i][X] > t:
                    q.append(X)
                    dist[i][X] = t

    cnt = [0] * N

    for i in range(N):
        for j in range(i + 1, N):
            cnt[dist[i][j]] += 1

    for i in cnt[1:]:
        print(i)


main()


Measured memory_bytes: 137424
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define re register
#define ll long long
inline int gi(){
	int f=1,sum=0;char ch=getchar();
	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
	return f*sum;
}
const int Mod=1e9+7,N=200010;
int fac[N],inv[N],n,m,a,b;
int qpow(int a,int b){int ret=1;while(b){if(b&1)ret=1ll*ret*a%Mod;b>>=1;a=1ll*a*a%Mod;}return ret;}
int C(int p,int q){if(p<q || p<0 || q<0)return 0;return 1ll*fac[p]*inv[q]%Mod*inv[p-q]%Mod;}
int main(){
	n=gi();m=gi();
	a=gi();b=gi();int ans=0;fac[0]=inv[0]=inv[1]=1;
	for(int i=1;i<=200000;i++)fac[i]=1ll*fac[i-1]*i%Mod;
	for(int i=2;i<=200000;i++)inv[i]=1ll*(Mod-Mod/i)*inv[Mod%i]%Mod;
	for(int i=2;i<=200000;i++)inv[i]=1ll*inv[i-1]*inv[i]%Mod;
	for(int i=1;i<=n-a;i++)
		ans=(ans+1ll*C(b+i-2,i-1)*C(n-i+m-b-1,n-i)%Mod)%Mod;
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 1792
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    x=SI().split()[1][0]
    print("A"+x+"C")

main()

Measured memory_bytes: 3064
n = gets.to_i
k = gets.to_i
color = [3, 1, 2]
arr = []
k.times{
    a, b = gets.chomp.split.map(&:to_i)
    x = a
    x = (n + 1 - a) if a > (n + 1) / 2
    y = b
    y = (n + 1 - b) if b > (n + 1) / 2
    puts color[[x, y].min % 3]
}


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

int N;
int max_count = 0;
vector<vector<int>> field;

void search(int y, int x, int sum, vector<vector<int>> field)
{
    if (y == 1 && x == N - 1)
    {
        if (max_count < sum)
        {
            max_count = sum;
        }
        return;
    }

    if (x + 1 < N)
    {
        search(y, x + 1, sum + field[y][x + 1], field);
    }
    if (y == 0)
    {
        search(1, x, sum + field[1][x], field);
    }

    return;
}

int main()
{
    cin >> N;
    vector<vector<int>> field(2, vector<int>(N, 0));
    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> field[i][j];
        }
    }

    search(0, 0, field[0][0], field);

    cout << max_count;
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
      
#define FOR(i,a,b) for( ll i = (a); i < (ll)(b); i++ )
#define REP(i,n) FOR(i,0,n)
#define YYS(x,arr) for(auto& x:arr)
#define ALL(x) (x).begin(),(x).end()
#define SORT(x) sort( (x).begin(),(x).end() )
#define REVERSE(x) reverse( (x).begin(),(x).end() )
#define UNIQUE(x) (x).erase( unique( ALL( (x) ) ) , (x).end() )
#define PW(x) (1LL<<(x))
#define SZ(x) ((ll)(x).size())
#define SHOW(x) cout << #x << " = " << x << endl
#define SHOWA(x,n) for( int yui = 0; yui < n; yui++ ){ cout << x[yui] << " "; } cout << endl

#define pb emplace_back
#define fi first
#define se second

using namespace std;

typedef long double ld;
typedef long long int ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<ld> vd;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<vpl> gr;
typedef vector<vl> ml;
typedef vector<vd> md;
typedef vector<vi> mi;
     
const ll INF = (ll)1e9 + 10;
const ll INFLL = (ll)1e18 + 10;
const ld EPS = 1e-12;
const ll MOD = 1e9+7;
     
template<class T> T &chmin( T &a , const T &b ){ return a = min(a,b); }
template<class T> T &chmax( T &a , const T &b ){ return a = max(a,b); }
template<class T> inline T sq( T a ){ return a * a; }

ll in(){ long long int x; scanf( "%lld" , &x ); return x; }
char yuyushiki[1000010]; string stin(){ scanf( "%s" , yuyushiki ); return yuyushiki; }

// head

string s;

int a, b;

int main(){

  s = stin();

  YYS( w , s ){
    if( w == 'S' ){
      a++;
    } else if( w == 'T' ){
      if( a > 0 ){
        a--;
      } else {
        b++;
      }
    }
  }

  cout << a + b << endl;
  
  return 0;
}


Measured memory_bytes: 640
import java.util.*;
public class Main{
    public static void main(String[] args){
        final long mod = 1000000007;
        Scanner sc = new Scanner(System.in);
        long n = sc.nextInt();
        long a = 1;
        long b = 1;
        long c = 1;
        long d = 1;
        for(int i = 0; i < n; i++){
            //0~9のいずれかをN個並べてできる数列の数
            a *= 10;
            a %= mod;
            //1~8のいずれかをN個並べてできる数列の数
            b *= 8;
            b %= mod;
            //0~8のいずれかをN個並べてできる数列の数
            c *= 9;
            c %= mod;
            //1~9のいずれかをN個並べてできる数列の数
            d *= 9;
            d %= mod;
        }
        //条件を満たす数列の数
        long ans = (a - (c + d - b)) % mod;
        if(ans < 0){
            ans += mod;
        }
        
        System.out.println(ans);
    }
}

Measured memory_bytes: 35784
class UnionFind[T] {

  private[this] var map = Map.empty[T, T];

  def addPair(parent: T, child: T): Unit = {
    val pr = fetchRoot(parent);
    val cr = fetchRoot(child);
    if (pr != cr) {
      map = map + (cr -> pr);
    }
  }

  def fetchRoot(elem: T): T = {
    @scala.annotation.tailrec
    def sub(elem: T, pendings: List[(T, T)]): T = {
      map.get(elem) match {
        case None =>
          pendings.foreach { case (c, p) =>
            if (p != elem) {
              map = map + (c -> elem);
            }
          }
          elem;
        case Some(p) =>
          sub(p, (elem, p) :: pendings);
      }
    }
    sub(elem, Nil);
  }

}

object Main extends App {
  val sc = new java.util.Scanner(System.in);
  val n, m = sc.nextInt();
  val ps = Array.fill(n)(sc.nextInt());
  val xys = Array.fill(m)((sc.nextInt(), sc.nextInt()));

  val unionFind = new UnionFind[Int];
  xys.foreach { case (x, y) =>
    unionFind.addPair(y, x);
  }

  val answer = ps.zipWithIndex.count { case (p, i) =>
    unionFind.fetchRoot(p) == unionFind.fetchRoot(i + 1);
  }
  println(answer);
}

Measured memory_bytes: 85820
#include <bits/stdc++.h> //全てのヘッダファイルをインクルード

//ループ
#define rep(i, n) for(int i = 0; i < n; i++) //普通のループ
#define repr(i, n) for(int i = n; i >= 0; i--) //逆ループ

//型名省略
typedef long long ll;
//値
static const ll MX = 100005;
static const ll MX_ll = 1e18;

using namespace std;

//#include "./lib/generic/search.h"

int main(){
    string s, t;
    cin >> s >> t;
    int ans=-1e9, tmpans=0, tmp=0;
    for(int i=0; i<=s.length()-t.length(); i++){
        rep(j,t.length()){
            if(s[i+j]==t[j]){
                tmpans++;
            }
        }
        ans=max(ans, tmpans);
        tmpans=0;
    }
    ans=t.length()-ans;
    cout << ans << endl;
    return 0;
}


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

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

using namespace std;

void push(vector<vector<int>>& tb, int i, int j) {
  int d[2] = {0,1};
  REP(k,2)REP(l,2){
    int ni=i+d[k];
    int nj=j+d[l];
    if(tb[ni][nj] != 0) {
      ++tb[ni][nj];
      if(tb[ni][nj] == 5) tb[ni][nj] = 1;
    }
  }
}

int score(const vector<vector<int>>& tb) {
  int sum = 0;
  REP(i,5)REP(j,5){
    switch(tb[i][j]){
      case 2:
      sum += 60;
      break;
      case 3:
      sum += 70;
      break;
      case 4:
      sum += 80;
      break;
    }
  }
  return sum;
}

int main() {
  int n;
  cin >> n;
  REP(i,n){
    vector<vector<int>> tb(5,vector<int>(5));
    REP(j,5)REP(k,5) cin >> tb[j][k];
    vector<vector<vector<int>>> dp(256);
    REP(j,256){
      auto cp = tb;
      REP(k,4){
        int l=(j>>(2*k))%4;
        REP(m,l)push(cp,0,k);
      }
      dp[j] = cp;
    }
    REP(j,3) {
      vector<vector<vector<int>>> tmp(256);
      REP(k,256){
        int maxv=-1;
        vector<vector<int>> mxt;
        for(auto cp:dp){
          REP(l,4){
            int m=(k>>(2*l))%4;
            REP(o,m)push(cp,j+1,l);
          }
          int scr = score(cp);
          if(maxv < scr) {
            maxv = scr;
            mxt = cp;
          }
        }
        tmp[k] = mxt;
      }
      swap(tmp, dp);
    }
    int maxv = 0;
    for(auto t:dp){
      maxv=max(maxv, score(t));
    }
    cout << maxv << endl;
  }
  return 0;
}

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

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int mod = (int)1e9 + 7;
void dbg(){ cerr << "\n"; }  template <typename T,typename ...T2> 
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }
const int dr[]={0,1,0,-1,0};

ll fc(const VI& v){
	int n= sz(v);
	deque<int> dq = {v.front()};
	for(int i=0, l=1, r=n-1; l<=r; i++){
		if(i%2==0){
			if(l<=r) dq.push_back( v[r--]);
			if(l<=r) dq.push_front(v[r--]);
		}else{
			if(l<=r) dq.push_back( v[l++]);
			if(l<=r) dq.push_front(v[l++]);
		}
	}
	ll rtn =0;
	rep(i, n-1) rtn += abs(dq[i] - dq[i+1]);
	return rtn;
}

int main(){
	int n;
	cin >>n;
	VI a(n);
	rep(i, n) cin >>a[i];
	sort(all(a));
	ll ans = fc(a);
	reverse(all(a)); 
	ans = max(ans, fc(a));
	cout << ans <<"\n";
}



Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long long MOD = 1000000007;
  int N;
  cin>>N;
  long long kotae=1;
  for(int i=1;i<=N;i++){
    kotae=kotae*i%MOD;
  }
  cout <<kotae<<endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<string>
#include<bitset>
#define nl n<<1
#define nr (n<<1)|1
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int INF=0x3f3f3f3f;
const ll INFF=0x3f3f3f3f3f3f3f3f;
const double pi=acos(-1.0);
const double eps=1e-9;
const ll mod=100000073;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0' | ch>'9') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void Out(ll aa)
{
    if(aa>9)
        Out(aa/10);
    putchar(aa%10+'0');
}
int main()
{
    int n=read();
    ll ans=1;
    for(int i=1;i<=n;i++)
    {
        ll x;scanf("%lld",&x);
        ans=x/__gcd(ans,x)*ans;
    }
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 256
import java.io.InputStream;
import java.io.PrintStream;
import java.util.Scanner;

public class Main {
	InputStream in = System.in;
	PrintStream out = System.out;

	int mod = 1000000007;

	public void _main(String[] args) {
		Scanner sc = new Scanner(in);

		int N = sc.nextInt();
		int[] A = nextIntArray(sc, N);

		sc.close();

		long ans = 1;
		int[] x = new int[] { 0, 0, 0 };

		for (int i = 0; i < N; i++) {
			int z = 0;
			boolean b = false;
			if (x[0] == A[i]) {
				z++;
				x[0]++;
				b = true;
			}
			if (x[1] == A[i]) {
				z++;
				if (!b) {
					x[1]++;
					b = true;
				}
			}
			if (x[2] == A[i]) {
				z++;
				if (!b) {
					x[2]++;
					b = true;
				}
			}
			ans *= z;
			ans %= mod;
		}

		out.println(ans);

	}

	int[] f(String s) {
		int[] result = new int[s.length()];

		int[] cnt = new int[] { 0, 0, 0 };

		for (int i = 0; i < s.length(); i++) {
			int c = s.charAt(i);
			result[i] = cnt[c - '0']++;
		}
		return result;
	}

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

	@SuppressWarnings("unused")
	private int[] nextIntArray(Scanner sc, int n) {
		int[] result = new int[n];
		for (int i = 0; i < n; i++) {
			result[i] = sc.nextInt();
		}
		return result;
	}
}


Measured memory_bytes: 54392
import java.util.Scanner;

public class Main {
	public static Scanner sc = new Scanner(System.in);
	public static void main(String[] args){
		//A
		
		int a = sc.nextInt();
		int b = sc.nextInt();
		if(a+b < 17 && a < 9 && b < 9)
			System.out.println("Yay!");
		else
			System.out.println(":(");
		//B
		/*
		int d = sc.nextInt();
		int n = sc.nextInt();
		System.out.println((int)Math.pow(100,d)*n);
		*/
		//C
		/*
		int n = sc.nextInt();
		int[] a = new int[n];
		boolean[] k_flag = new boolean[n];
		for(int i = 0; i < n ; i++){
			int x = sc.nextInt();
			if(x%2 == 0) k_flag[i]=false;
			else k_flag[i] = true;
			a[i] = x;
		}
		for(int j = 0 ; j < n ; j++){
			if(a[j]%2 == 1)
				a[j] *= 3;
			else
				a[j] /= 2;
		}
		*/
		//D
	}
}


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

using namespace std;

#define S scanf
#define P printf
#define G getline
#define SZ size()
#define C clear()
#define B begin()
#define F front()
#define T top()
#define E end()
#define EM empty()
#define V vector
#define Q queue
#define DQ deque
#define PQ priority_queue
#define ST stack
#define FI first
#define SE second
#define PI acos(-1)
#define PS push
#define PP pop()
#define PSF push_front
#define PSB push_back
#define PPF pop_front()
#define PPB pop_back()
#define MP make_pair
#define LL long long int
#define ULL unsigned long long int
#define PII pair<int,int>
#define PSI pair<string,int>
#define PIS pair<int,string>
#define PLI pair<long long int,int>
#define PLL pair<long long int,long long int>
#define MII map<int,int>
#define MSI map<string,int>
#define MIS map<int,string>
#define MLI map<long long int,int>
#define FAST() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)





//int dx[]={-1,1,0,0};
//int dy[]={0,0,-1,1};
//int dx[]= {-1,0,1,-1,1,-1,0,1};
//int dy[]= {1,1,1,0,0,-1,-1,-1};






int main()
{
    FAST();

//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);

    int a,b;
    cin >> a >> b;
    if(a > b)swap(a,b);
    if(a == 1  && b == 2)cout << "3";
    else if(a == 1  && b == 3)cout << "2";
    else if(a == 2  && b == 3)cout << "1";
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <stack>
#include <deque>
#include <algorithm>
using namespace std;

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

  stack<int> state;
  deque<pair<int, int>> lakes;

  int lsum = 0;
  for (int i = 0; i < (int)s.size(); i++)
  {
    char ch = s[i];
    if (ch == '\\')
    {
      state.push(i);
    }
    else if (ch == '/' && state.size() > 0)
    {
      int ls = i - state.top();
      lsum += ls;

      while (lakes.size() > 0 && state.top() < lakes.back().first)
      {
        ls += lakes.back().second;
        lakes.pop_back();
      }
      lakes.push_back(make_pair(state.top(), ls));
      state.pop();
    }
  }

  cout << lsum << "\n"
       << lakes.size();
  for (auto itr = lakes.begin(); itr != lakes.end(); ++itr)
  {
    cout << " " << (*itr).second;
  }
  cout << endl;
}



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

using namespace std;

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

// container util
#define all(x) (x).begin(), (x).end()

// typedef
typedef long long llint;
typedef unsigned long long ull;
typedef complex<long double> Complex;
typedef pair<int, int> P;
typedef tuple<int, int, int> TP;
typedef vector<int> vec;
typedef vector<vec> mat;

// constant
const int MOD = (int)1e9 + 7;
const int INF = (int)1e9;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};
const double pi = 3.14159265358979323846;

// conversion
inline int toInt(string s) {
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}
template <class T>
inline string toString(T x) {
  ostringstream sout;
  sout << x;
  return sout.str();
}

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

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

  llint n, k;
  cin >> n >> k;
  llint x = n % k;
  llint y = x - k;
  if (y < 0) y = -y;
  cout << min(x, y) << endl;

  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <string>    
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
string str;

int main(){
	cin >> str;
	
	string ans = "NO";
	bool is_dream = false;
	bool is_eras = false;
	while(1){
		if(str.substr(0, 5) == "dream"){
			str = str.substr(5, str.size()-5);
			is_dream = true;
			is_eras = false;
		}
		else{
			if(str.substr(0, 4) == "eras"){
				str = str.substr(4, str.size()-4);
				is_dream = false;
				is_eras = true;
			}
			else{
				if((is_dream || is_eras) && str.substr(0, 2) == "er"){
					str = str.substr(2, str.size()-2);
					is_dream = false;
					is_eras = false;
				}
				else{
					if(is_eras && str.substr(0, 1) == "e"){
						str = str.substr(1, str.size()-1);
						is_dream = false;
						is_eras = false;
					}
					else{
						if(str == ""){ans = "YES";}
						break;
					}
				}
			}
		}
	}
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 512
#! /usr/bin/env python3
def main():
    S = input()
    r = len(S)
    if len(set(S)) == 1:
        print(0)
    else:
        cnt = 0
        l = list(S)
        while cnt < 200:
            cnt += 1
            l = [l[x]+S[x+cnt] for x in range(len(l)-1)]
            for i in set(''.join(l)):
                if all((1 if i in x else 0) for x in l):
                    print(cnt)
                    return
    
if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
function main(input) {
  const inputData = input.replace(/\s*$/g, '').split(/\s+/).map(v => parseInt(v));
  const [a, b, h, m] = inputData;

  const hRad = (h + m / 60) * Math.PI / 6;
  const mRad = m * Math.PI / 30;
  const hDeg = h * 30;
  const mDeg = m * 6;

  const vecA = {
    x: a * Math.sin(hRad),
    y: a * Math.cos(hRad)
  };
  const vecB = {
    x: b * Math.sin(mRad),
    y: b * Math.cos(mRad)
  };

  const res = Math.sqrt((vecA.x - vecB.x) ** 2 + (vecA.y - vecB.y) ** 2);

  console.log(res);
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));


Measured memory_bytes: 29764
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
//mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
//int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
const int maxx=1e5+10;
ll num[maxx];
ll sum=0;
int main() {
	int n;
	memset(num,0,sizeof(num));
	scanf("%d",&n);
	rep(i,0,n){
		int a;
		scanf("%d",&a);
		num[a]++;
		sum+=a;
	}
	scanf("%d",&n);
	rep(i,0,n){
		int a,b;
		scanf("%d%d",&a,&b);
		sum-=1ll*a*num[a];
		sum+=1ll*b*num[a];
		num[b]+=num[a];
		num[a]=0;
		printf("%lld\n",sum);
	}
	return 0;
} 

Measured memory_bytes: 4552
from collections import deque

N = int(input())
S = list(input())
stack = deque()
ans = ""
for s in S:
  ans += s
  if s == "(":
    stack.append(s)
  else:
    if not stack:
      ans = "("+ans
    else:
      _ = stack.pop()
if stack:
  ans += ")"*len(stack)
print(ans)


Measured memory_bytes: 3316
#include<stdio.h>
int main()
{
	int m;
	scanf("%d", &m);
	int i;
	long long int d[200005], c[200005];
	for (i = 0; i < m; i++)
		scanf("%lld %lld", &d[i], &c[i]);
	long long int ans = 0;
	for (i = 0; i < m; i++)
		ans += c[i];
	ans--;
	long long int v = 0;
	for (i = 0; i < m; i++)
		v += d[i] * c[i];
	ans += v / 10;
	while (v > 9)
	{
		v = v / 10 + v % 10;
		ans += v / 10;
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 3328
#include<iostream>
using namespace std;
int main(){
  int k,s,ans=0;
  cin >> k >> s;
  for(int i=0;i<=k;i++){
    for(int l=0;l<=k;l++){
      if (s-i-l <= k && s-i-l >= 0){
        ans++;
      }
    }
  }
  cout << ans;
}


Measured memory_bytes: 256
#include <iostream>
#include<bits/stdc++.h>
#define ll long long
#define inf 1e9+1
using namespace std;
struct item
{
    int wt;
    int val;
};
ll solve(vector<item> ar,int n,int W)
{   int max_value=n*1000;
    ll dp[n+1][max_value+1];
    for(int val=0;val<=max_value;val++)
        dp[1][val]=inf;
    dp[1][0]=0;
    dp[1][ar[1].val]=ar[1].wt;
    for(int i=2;i<=n;i++)
    {
        for(int v=0;v<=max_value;v++)
        {
            dp[i][v]=dp[i-1][v];
            if(ar[i].val>v)
            {
                continue;
            }
            dp[i][v]=min(dp[i][v],ar[i].wt+dp[i-1][v-ar[i].val]);
        }
    }
    ll ans=0;
    for(int x=0;x<=max_value;x++)
    {
        if(dp[n][x]<=W)
            ans=x;
        
    }
    return ans;
}
int main() {
    int n,W;
    cin>>n>>W;
    vector<item> ar(n+1);
    for(int i=1;i<=n;i++)
    {
        cin>>ar[i].wt>>ar[i].val;
    }
    cout<<solve(ar,n,W);
}


Measured memory_bytes: 78336
#!/usr/bin/env python3
import sys


def solve(N: int, M: int, A: "List[int]"):
    if (N-sum(A) < 0):
        print(-1)
    else:
        print(N-sum(A))
    return


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

if __name__ == '__main__':
    main()


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

using namespace std;
typedef long long ll;

struct UnionFind {
    vector<int> d;

    UnionFind(int n): d(n,-1) {}

    int root(int x) {
        if (d[x] < 0) return x;
        return d[x] = root(d[x]);
    }

    bool unite(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (d[x] > d[y]) swap(x,y);
        d[x] += d[y];
        d[y] = x;
        return true;
    }

    bool same(int x, int y) { return root(x) == root(y);}

    int size(int x) { return -d[root(x)];}
};

int main() {
    int n, m; cin >> n >> m;
    vector<int> a(m), b(m);
    for (int i = 0; i < m; i++) {
        cin >> a[i] >> b[i];
        a[i]--; b[i]--;
    }

    int ans = 0;
    for (int i = 0; i < m; i++) {
        UnionFind uf = UnionFind(n);
        for (int j = 0; j < m; j++) {
            if (j == i) continue;           
            uf.unite(a[j], b[j]);
        }

        if (uf.size(1) != n) ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256