akhauriyash/Code-Regression huggingface dataset:
pub struct ProconReader<R: std::io::Read> {
    reader: R,
}

impl<R: std::io::Read> ProconReader<R> {
    pub fn new(reader: R) -> Self {
        Self { reader }
    }
    pub fn get<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .reader
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&byte| byte == b' ' || byte == b'\n' || byte == b'\r')
            .take_while(|&byte| byte != b' ' && byte != b'\n' && byte != b'\r')
            .collect::<Vec<_>>();
        std::str::from_utf8(&buf)
            .unwrap()
            .parse()
            .ok()
            .expect("Parse Error.")
    }
}

mod rolling_hash {
    const MASK30: u64 = (1 << 30) - 1;
    const MASK31: u64 = (1 << 31) - 1;
    const MOD: u64 = (1 << 61) - 1;
    const MASK61: u64 = (1 << 61) - 1;
    const BASE: u64 = 1_000_000_000 + 9;
    pub struct RollingHash {
        h: Vec<u64>,
        p: Vec<u64>,
    }
    impl RollingHash {
        pub fn new(s: &[u64]) -> Self {
            let n = s.len();
            let mut h = vec![0; n + 1];
            let mut p = vec![0; n + 1];
            p[0] = 1;
            for i in 0..n {
                h[i + 1] = mul(h[i], BASE) + s[i];
                p[i + 1] = mul(p[i], BASE);
            }
            Self { h, p }
        }
        pub fn get(&self, range: std::ops::Range<usize>) -> u64 {
            let l = range.start;
            let r = range.end;
            (self.h[r] + MOD - mul(self.h[l], self.p[r - l])) % MOD
        }
    }
    fn mul(a: u64, b: u64) -> u64 {
        let au = a >> 31;
        let ad = a & MASK31;
        let bu = b >> 31;
        let bd = b & MASK31;
        let mid = ad * bu + au * bd;
        let midu = mid >> 30;
        let midd = mid & MASK30;
        calc_mod(au * bu * 2 + midu + (midd << 31) + ad * bd)
    }
    fn calc_mod(x: u64) -> u64 {
        let xu = x >> 61;
        let xd = x & MASK61;
        let mut res = xu + xd;
        if res >= MOD {
            res -= MOD;
        }
        res
    }
}

fn main() {
    let stdin = std::io::stdin();
    let mut rd = ProconReader::new(stdin.lock());

    use rolling_hash::RollingHash;

    let n: usize = rd.get();
    let s: String = rd.get();
    let t = s.chars().map(|c| c as u64).collect::<Vec<_>>();
    let rh = RollingHash::new(&t);
    let mut ans = 0;
    for i in 0..n {
        for j in (i + 1)..n {
            let mut ok = 0;
            let mut ng = std::cmp::min(j - i, n - j) + 1;
            while ng - ok > 1 {
                let m = (ng + ok) / 2;
                if rh.get(i..(i + m)) == rh.get(j..(j + m)) {
                    ok = m;
                } else {
                    ng = m;
                }
            }
            ans = std::cmp::max(ans, ok);
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 2268
#include <iostream>

using namespace std;

typedef long long ll;

int MOD;

struct Modint {
  ll val;
  
  Modint (ll _val = 0)
    : val(_val % MOD) {}

  Modint operator+ (Modint other) const {
    return Modint(val + other.val);
  }

  void operator+= (Modint other) {
    val += other.val;
    val %= MOD;
  }

  Modint operator- () const {
    return Modint(MOD - val);
  }

  Modint operator- (Modint other) const {
    return Modint(val + MOD - other.val);
  }

  void operator-= (Modint other) {
    val += MOD - other.val;
    val %= MOD;
  }

  Modint operator* (Modint other) const {
    return Modint(val * other.val);
  }

  void operator*= (Modint other) {
    val *= other.val;
    val %= MOD;
  }

  bool operator== (Modint other) const {
    return val == other.val;
  }

  bool operator!= (Modint other) const {
    return val != other.val;
  }
};

Modint exp (Modint a, int k) {
  if (k == 0) {
    return Modint(1);
  } else if (k % 2 == 0) {
    Modint half = exp(a, k / 2);
    return half * half;
  } else {
    return a * exp(a, k - 1);
  }
}

Modint inv (Modint a) {
  return exp(a, MOD - 2);
}

ostream& operator<< (ostream& out, Modint p) {
  out << p.val;
  return out;
}

const int MAX_N = 1e4 + 5;

ll cnt [MAX_N];

int main () {
  ios::sync_with_stdio(false);
  
  int n;
  cin >> n >> MOD;

  string s;
  cin >> s;

  if (MOD == 2 || MOD == 5) {
    ll ans = 0;
    ll pre = 1;
    for (char c : s) {
      if ((c - '0') % MOD == 0) {
        ans += pre;
      }
      pre++;
    }
    cout << ans << endl;
    return 0;
  }
  
  cnt[0] = 1;
  int p = n;
  ll ans = 0;
  Modint cur (0);
  for (char c : s) {
    cur += exp(Modint(10), p) * Modint(c - '0');
    ans += cnt[cur.val];
    cnt[cur.val]++;
    
    p--;
  }

  cout << ans << endl;
}


Measured memory_bytes: 720
# pragma GCC optimize("O3")
# include <bits/stdc++.h>
# define maxn 100005
# define ll long long
# define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
# define rc(s) return cout << s,0
# define _ ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
# define db(x) cerr << #x << " = " << x << '\n'
# define pb push_back
# define mp make_pair
# define sz(x) (int)((x).size())
//# define int ll
using namespace std;

int mx = 0;
int n;
bool dp[10001];
int s[101];

int32_t main(){_
    //freopen("input","r",stdin);
	cin >> n;
	for(int i = 0;i <= n;i++) dp[0] = 1;
	for(int i = 1;i <= n;i++) cin >> s[i];
		for(int j = 1;j <= n;j++)
	{
		for(int i = 10000;i >= s[j];i--)
		{
			if(dp[i - s[j]]) dp[i] = 1;
			if(dp[i] && (i % 10)) mx = max(mx,i);
		}
	}
	rc(mx);
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define dbg(x) cerr << #x << " = " << x << endl
#define _ << ' ' <<
using namespace std;
using ll = long long;
using vi = vector<int>;
const int mod = 1000000007;
int add(int a, int b) { return (a += b) < mod? a : a - mod; }
int sub(int a, int b) { return (a -= b) >=  0? a : a + mod; }
int mul(int a, int b) { return 1LL * a * b % mod; }
void adds(int& a, int b) { a = add(a, b); }
void subs(int& a, int b) { a = sub(a, b); }
void muls(int& a, int b) { a = mul(a, b); }
void maxs(int& a, int b) { a = max(a, b); }
void mins(int& a, int b) { a = min(a, b); }
int pwr(int a, ll p) {
    if (p == 0) return 1;
    if (p & 1) return mul(a, pwr(a, p - 1));
    return pwr(mul(a, a), p / 2);
}
int inv(int a) { return pwr(a, mod - 2); }

int f[30];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    int n;
    cin >> n >> s;
    for (char c : s)
        f[c - 'a']++;
    int sol = 1;
    for (int i = 0; i < 30; ++i)
        muls(sol, f[i] + 1);

    cout << sub(sol, 1);
}


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

int main(){
    int h,w;
    cin>>h>>w;
    char img[h][w];
    for(int r=0;r<h;r++){
        for(int c=0;c<w;c++){
            cin>>img[r][c];
        }
    }
    for(int r=0;r<2*h;r++){
        for(int c=0;c<w;c++){
            cout<<img[(r+1+1)/2-1][c];
        }
        cout<<endl;
    }
    return 0;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
#define MOD 1000000007
#define int long long
#define pb push_back
#define bw(i,r,l) for (int i=r-1;i>=l;i--)
#define fw(i,l,r) for (int i=l;i<r;i++)
using namespace std;
const int N=2e5+1;
int n,ans=0,a[N],x[N],cur[N];
void bad() {
	cout<<"-1";
	exit(0);
}
signed main() {
	//freopen("aome.inp","r",stdin);
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>n;
	fw (i,0,n) {
		cin>>a[i];
		if (i) {
			if (a[i]>a[i-1]+1) bad();
			if (a[i]==a[i-1]+1) ans++;
			else ans+=a[i];
		}
	}
	if (a[0]!=0) bad();
	/*
	If a[i] == a[i - 1] + 1 then just add 1 to answer
	Else add a[i - 1]
	*/
	cout<<ans;
	return 0;
}

Measured memory_bytes: 2944
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;

#define rep(i,N) for(int i=0;i<(int)(N);++i)
#define rrep(i,N) for(int i=(int)(N)-1;i>=0;--i)
#define debug(x) cout<<#x<<"="<<x<<endl;
constexpr int MOD=1000000007;
constexpr ll INF=(1LL<<61)-1;
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;}
template<typename T> void fail(T v){cout << v << endl;exit(0);}
//templte

void solve(){
    int N;
    scanf("%d",&N);
    bool use[505][505]={};
    int dist[505][505],gh[]={1,-1,0,0},gw[]={0,0,1,-1};
    rep(i,N)rep(j,N)dist[i][j]=min(i,min(j,min(N-i-1,N-j-1)));
    queue<int> Q;
    ll res=0;
    rep(i,N*N){
        int p;scanf("%d",&p);
        p--;
        int h=p/N,w=p%N;
        use[h][w]=1;
        res+=dist[h][w];
        Q.push(h*N+w);
        while(Q.size()){
            p=Q.front();Q.pop();
            h=p/N;w=p%N;
            int d=dist[h][w];
            if(!use[h][w])d++;
            rep(k,4){
                int y=gh[k]+h,x=gw[k]+w;
                if(0<=y&&y<N&&0<=x&&x<N&&chmin(dist[y][x],d))Q.push(y*N+x);
            }
        }
    }
    printf("%lld\n",res);
}

int main(){
    //cin.tie(0);
    //ios::sync_with_stdio(false);
    //cout << fixed << setprecision(20);
    solve();
    return 0;
}   

Measured memory_bytes: 4952
import java.util.*;
public class Main{
    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        String n = in.nextLine();
        if(n.indexOf("7") < 0) 
        {
            System.out.println("No");
        } 
      	else
        {
            System.out.println("Yes");
        }
    }
}


Measured memory_bytes: 35624
// https://atcoder.jp/contests/

#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)--)
#define FOR(i, m, n) for (int(i) = (m); (i) < (n); i++)
#define INF 1e9
#define ALL(v) (v).begin(), (v).end()
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

int main()
{
  ll N, M, a, rr[3] = {0, 0, 1}, MOD = 1e9 + 7;
  vector<bool> A;
  cin >> N >> M;

  REP(i, N + 1)
  {
    A.push_back(true);
  }
  REP(i, M)
  {
    cin >> a;
    A[a] = false;
  }

  FOR(i, 1, N + 1)
  {
    if (A[i])
    {
      rr[0] = rr[1];
      rr[1] = rr[2];
      rr[2] = (rr[0] + rr[1]) % MOD;
    }
    else
    {
      rr[0] = rr[1];
      rr[1] = rr[2];
      rr[2] = 0;
    }
  }

  cout << rr[2] << '\n';
  return 0;
}


Measured memory_bytes: 256
#include<iostream>

int main(){
   int i[5],a,b,n;
   for(a=0;a<5;++a){
    std::cin>>i[a];
    }
    for(a=0;a<4;++a){
        for(b=a+1;b<5;++b){
        if(i[a]<i[b]){
        n=i[a];
        i[a]=i[b];
        i[b]=n;
        }
        }
  }
  
      for(a=0;a<4;++a){
      std::cout<<i[a]<<" ";
      }
      std::cout<<i[4]<<std::endl;
      
    return 0;
    }

Measured memory_bytes: 1160
#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
#define ll long long 
#define M 1000000007
#define P pair<int,int>

ll n,s;

ll f(ll b,ll n){
  if(n<b) return n;
  
  return f(b,n/b) + n%b;
}

int main(){
  cin>>n>>s;
  if(s==n){
    cout<<n+1<<endl;
    return 0;
  }
  if(s<n){
    ll b;
    for(b=2;b*b<=n;b++)
      if(f(b,n)==s){
        cout<<b<<endl;
        return 0;
      }
    for(ll i=b;i>=1;i--){
      b = (n-s)/i+1;
      if(b>=2&&f(b,n)==s){
        cout<<b<<endl;
        return 0;
      }
    }
  }

  cout<<-1<<endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
	int m[28], f;
	bool b[30];
	for (int i = 0; i < 30; ++i) {
		b[i] = false;
	}
	for (int i = 0; i < 28; ++i) {
			cin >> m[i];
			b[m[i]-1] = true;
		}
	for (int i = 0; i < 30; ++i) {
		if (!b[i])cout << i+1 <<endl;
	}

    return 0;
}

Measured memory_bytes: 3088
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> a(n);
	for(int i = 0; i < n; ++i){ cin >> a[i]; }
	bool all_even = true;
	for(const int x : a){
		if(x % 2 != 0){ all_even = false; }
	}
	cout << (all_even ? "second" : "first") << endl;
	return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define endl '\n'
#define INF 1e9 + 5

//This solution is  recursive but slow

using namespace std;

int main() { 
    int n; cin >> n;
    int k;cin>>k;
    int jumps[n];
    vector<int> dp(n, INF); 
    int aux = 0;
    //Reading data
    for (int i = 0; i < n; i++) cin >> jumps[i];
    //Initialize base cases
    dp[0] = 0;
    //Initialize dp
    for ( int i = 0; i < n; i++ ) {
        for ( int j = i + 1; j <= i + k; j++ ) {
            if (j < n)
                dp[j] = min(dp[j], dp[i] + abs( jumps[j] - jumps[i]));
        } 
    }
    cout << dp[n - 1] << endl;
    return 0;
}


Measured memory_bytes: 4004
n, m = map(int, input().split())
ans = [0, 1]
for i in range(1, min(n, m)):
    k = 1 << i
    x = (1 << k) - 1
    slide = [a << k for a in ans]
    new_ans = [s | a for s, a in zip(slide, ans)]
    new_ans.extend(s | (a ^ x) for s, a in zip(slide, ans))
    ans = new_ans
if n > m:
    ans *= 1 << (n - m)
elif n < m:
    for i in range(n, m):
        k = 1 << i
        ans = [(a << k) | a for a in ans]

ans = [a0 ^ a1 for a0, a1 in zip(ans, ans[1:])]
ans = [a ^ (a >> 1) for a in ans]

print('\n'.join(map(('{:0' + str(2 ** m - 1) + 'b}').format, ans)))


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

using namespace std;

int main() {
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    if(a + b > c + d) {
        cout << "Left" << endl;
    } else if(a + b == c + d) {
        cout << "Balanced" << endl;
    } else {
        cout << "Right" << endl;
    }






}

Measured memory_bytes: 256
n=int(input())
a=int(input())
b=int(input())
c=int(input())
d=int(input())
e=int(input())

def f(a):
    if n%a==0:
        return n//a
    else:
        return n//a+1
l=[]
for i in [a,b,c,d,e]:
    l.append(f(i))

print(max(l)+4)



Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);

const int INF = 2e9;
const int MAXN = 1e5 + 5;

int n, k, h[MAXN], dp[MAXN];

int main() {
    IOS

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

    dp[1] = 0;
    for (int i = 2; i <= n; i++) {
        dp[i] = INF;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k && i + j <= n; j++) {
            dp[i + j] = min(dp[i + j], dp[i] + abs(h[i] - h[i + j]));
        }
    }

    cout << dp[n] << '\n';
}

Measured memory_bytes: 4464
from collections import deque

n, k = map(int,input().split())
A = list(map(int,input().split()))

def f(num) :
    return (num*(num+1) / 2) / num

for i, a in enumerate(A) :
    A[i] = f(a)

res = 0
tmp = 0

for i, a in enumerate(A) :
    if i < k :
        tmp += a
        res += a
    else :
        tmp += a
        tmp -= A[i-k]
        res = max(res, tmp)

print(res)


Measured memory_bytes: 25572
#include<iostream>
using namespace std;
int main(void)
{
int a,b,c;
int count1=0,count2=0;
char tmp;
while(cin>>a>>tmp>>b>>tmp>>c)
{
if(a*a+b*b==c*c)count1++;
else if(a==b)count2++;

}
cout<<count1<<endl;
cout<<count2<<endl;
return 0;
}

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

int N, K;
int A[5001];

void insertionSort(int g) {
	for (int i = g; i < N; i++) {
		int v = A[i];
		int j = i - g;

		while (j >= 0 && A[j] < v) {
			A[j + g] = A[j];
			j -= g;
		}
		A[j + g] = v;
	}
}

void shellSort() {
	vector<int>G;
	for (int h = 1;;) {
		if (h > N)break;
		G.push_back(h);
		h = 3 * h + 1;
	}

	for (int i = G.size() - 1; i >= 0; i--) {
		insertionSort(G[i]);
	}
}

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

	cin >> N >> K;
	for (int i = 0; i < N; i++)cin >> A[i];

	shellSort();

	int sum = 0, cnt = 0;
	for (int i = 0; i < N; i++) {
		if (sum + A[i] < K) {
			sum += A[i];
			cnt++;
		}
		else cnt = 0;
	}

	cout << cnt << endl;

    return 0;
}



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

int main(){
    int a,b,x;
    cin >> a >> b >> x;

    //安い方の1Lの代金
    int y = min(a,b*2);

    //zは下三桁が500を超えているか超えていないかを判断する
    //cはとりあえずyの値段で買っていい個数
    int z = x%1000;
    int c = x/1000;

    if(z==0){
        cout << c*y << endl;
        return 0;
    }
    

    if(z>500){
        //500よりも大きい時はyにc+1Lかけると最小
        cout << (c+1)*y << endl;
    }else{
        //どちらを買っても必要な量は超えるので安い方を足す
        int ans = y*c;
        if(a>b){
            ans += b;
        }else{
            ans += a;
        }
        cout << ans << endl;
    }
}


Measured memory_bytes: 3096
from scipy import gcd
from collections import Counter

def sum_of_gcd(N):
    temp = [gcd(i, k) for i in range(1, N+1) for k in range(1, N+1)]
    counts = Counter(temp)

    return sum([gcd(c, i)*counts[c] for i in range(1, N+1) for c in counts.keys()])

print(sum_of_gcd(int(input())))

Measured memory_bytes: 33924
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

int main()
{
  int n,m;
  scanf("%d%d",&n,&m);
  if(m%2==1){
    printf("-1\n");
    return 0;
  }
  vector<vector<int> > e(n);
  for(int i=0;i<m;i++){
    int a,b;
    scanf("%d%d",&a,&b);
    a--,b--;
    e[a].push_back(b);
    e[b].push_back(a);
  }
  vector<int> pr(n);
  vector<bool> v(n,false);
  pr[0]=-1;
  v[0]=true;
  queue<int> Q;
  Q.push(0);
  vector<int> P;
  while(!Q.empty()){
    int i=Q.front();
    Q.pop();
    P.push_back(i);
    for(int x=0;x<e[i].size();x++){
      int j=e[i][x];
      if(v[j])continue;
      v[j]=true;
      pr[j]=i;
      Q.push(j);
    }
  }
  vector<bool> D(n,false);
  vector<pair<int,int> > ans;
  for(int i=0;i<n;i++){
    for(int x=0;x<e[i].size();x++){
      int j=e[i][x];
      if(pr[i]!=j&&pr[j]!=i&&i<j){
	ans.push_back(make_pair(i,j));
	D[i]=!D[i];
      }
    }
  }
  for(int t=n-1;t>0;t--){
    int i=P[t];
    if(D[i]){
      ans.push_back(make_pair(i,pr[i]));
      D[i]=!D[i];
    }
    else{
      ans.push_back(make_pair(pr[i],i));
      D[pr[i]]=!D[pr[i]];
    }
  }
  for(int t=0;t<m;t++){
    printf("%d %d\n",ans[t].first+1,ans[t].second+1);
  }
  return 0;
}


Measured memory_bytes: 8572
N,K=map(int,input().split())

if K%2:
  tmp0=0
  for i in range(1,N+1):
    if i%K==0:
      tmp0+=1
  print(tmp0**3)
else:
  tmp0=0
  tmp1=0
  for i in range(1,N+1):
    if i%K==0:
      tmp0+=1
    if i%K==K//2:
      tmp1+=1
  print(tmp0**3+tmp1**3)

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <utility>
#include <deque>
using namespace std;
using ll = long long;
auto sum = [](ll x) { return x * (x + 1) / 2; };
int main() {
    string S;
    cin >> S;
    deque<pair<char, ll>> dp;
    for (ll i = 0, cnt = 1, len = S.size(); i < len; i++) {
        if (i == len - 1 || (i < len - 1 && S[i] != S[i + 1])) {
            dp.push_back(make_pair(S[i], cnt));
            cnt = 1;
        }
        else cnt++;
    }
    ll ans = dp[0].first == '>' ? dp[0].second : 0;
    for (ll i = 0, len = dp.size(); i < len; i++) {
        const char c = dp[i].first;
        const ll x = dp[i].second;
        if (i == len - 1) {
            if (c == '<') ans += sum(x);
            else ans += sum(x - 1);
        }
        else {
            const ll y = dp[i + 1].second;
            if (c == '<') {
                if (x < y) ans += sum(x - 1) + y;
                else ans += sum(x);
            }
            else ans += sum(x - 1);
        }
    }
    cout << ans <<endl;
}


Measured memory_bytes: 4868
#include <stdio.h>
#define BUFMAX 10
#define DAYSEC 86400
#define HOURSEC 3600
#define MINSEC 60

int main(){
    char buf[BUFMAX];
    int t,h,m,s;

    fgets(buf,BUFMAX,stdin);
    buf[BUFMAX-1] = '\0';
    sscanf(buf,"%d", &t);
    h = t / HOURSEC;
    m = (t % HOURSEC) / MINSEC;
    s = t % MINSEC;
    printf("%d:%d:%d\n",h, m, s);
    return 0;
}

Measured memory_bytes: 1776
#include <iostream>
#include <vector>

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

using namespace std;

int main(){
  int N;
  cin >> N;
  vector<int> W(N);
  rep(i,N) cin >> W[i];
  int ans = (int)1e9+7;
  rep(T,N){
    int left = 0, right = 0;
    for(int i = 0; i<T; ++i){
      left += W[i];
    }
    for (int i = T; i<N; ++i){
      right += W[i];
    }
    ans = min(ans, abs(right-left));
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>

typedef long long unsigned int ll;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

using namespace std;

int main()
{
	long long n, m, cnt;
	long long a, b;
	
	cin >> n >> m;
	bool s[200050] = {};
	bool t[200050] = {};

	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		
		if (a == 1) {
			s[b] = true;
		}
		
		if (b == n) {
			t[a] = true;
		}
	}
	
	for (int i = 0; i < 200050; i++) {
		if (s[i] == true && t[i] == true) {
			cout << "POSSIBLE" << endl;
			return 0;
		}
	}
	cout << "IMPOSSIBLE" << endl;

	return 0;

}



Measured memory_bytes: 640
n= int(input())
L=list(map(int,input().split()))
ans=[]
p=0
for i in range(1,n-1,2):
	p+=L[i]

ans.append(sum(L)-2*p)

for i in range(1,n):
	ans.append(2*L[i-1]-ans[i-1])

print(*ans)

Measured memory_bytes: 14028
n = int(input())
l = list(map(int, input().split()))
d = {}

for a in l:
  if a in d:
    d[a] += 1
  else:
    d[a] = 1

ans = 0
for k, v in d.items():
  if k > v:
    ans += v
  elif k < v:
    ans += v-k
  else:
    pass
print(ans)


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

char a,b,c,d;

int main(){
	scanf("%c%c%c%c",&a,&b,&c,&d);
	if(a==b||b==c||c==d){
		printf("Bad\n");
	}
	else printf("Good\n");
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
using namespace std;

long long n;

int main(void) {
  scanf("%lld", &n);
  int ans = 0, u = 0, w = 0;
  while(n) {
    ans += n % 10;
    w = n % 10;
    n /= 10;
    u++;
  }
  printf("%d\n", max(ans, (u - 1) * 9 + w - 1));
  return 0;
}


Measured memory_bytes: 128
#include<stdio.h>

#define MAX 100005
#define NIL -1

struct Node {int p,l,r;};

struct Node T[MAX];
int n,D[MAX],H[MAX];


void print(int u){
  int i,c;
  printf("node %d: ",u);
  printf("parent = %d, ",T[u].p);
  printf("depth = %d, ",D[u]);

  if(T[u].p==NIL)printf("root, ");
  else if(T[u].l==NIL)printf("leaf, ");
  else printf("internal node, ");

  printf("[");

  for(i=0,c=T[u].l;c!=NIL;i++,c=T[c].r){
    if(i)printf(", ");
    printf("%d",c);
  }
  printf("]\n");
}

void rec(int u,int p){
  D[u]=p;
  if(T[u].r!=NIL)rec(T[u].r,p);
  if(T[u].l!=NIL)rec(T[u].l,p+1);}

int main(){
  int i,j,d,v,c,l,r;
  scanf("%d",&n);
  for(i=0;i<n;i++)
    T[i].p=T[i].l=T[i].r=NIL;

  for(i=0;i<n;i++){
   scanf("%d%d",&v,&d);
    for(j=0;j<d;j++){
      scanf("%d",&c);
	if(j==0)T[v].l=c;
	else T[l].r=c;
	l=c;
	T[c].p=v;
      }
    }
    for(i=0;i<n;i++){
      if(T[i].p==NIL)r=i;
    }

    rec(r,0);

    for(i=0;i<n;i++)
      print(i);
    return 0;}
  



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


int main(){
	string s;
	cin >> s;
	set<char> counter;
	rep(i, s.size()){
	    if(counter.count(s[i])){
            cout << "no\n";
            return 0;
	    }
	    counter.insert(s[i]);
	}
	cout << "yes\n";
}


Measured memory_bytes: 256
#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
template<typename T1,typename T2> bool chmin(T1 &a,T2 b){if(a<=b)return 0; a=b; return 1;}
template<typename T1,typename T2> bool chmax(T1 &a,T2 b){if(a>=b)return 0; a=b; return 1;}




signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);
 
    int n,k;
    cin>>n>>k;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    ll ans = 1e17;
    for(int bit=0;bit<(1<<n);bit++){
        int cnt = 0;
        int now = 0;
        ll cost = 0;
        for(int i=0;i<n;i++){
            if(a[i] > now){
                cnt++;
                now = a[i];
            }
            else if(bit & (1<<i)){
                now++;
                cost += now - a[i];
                cnt++;
            }
        }
        if(cnt >= k)chmin(ans,cost);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<algorithm>

using namespace std;

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

int main(){
    int N;
    cin >> N;
    int l,r;
    int sum=0;
    REP(i,N){
        cin >> l >> r;
        sum += r-l+1;
    }
    cout << sum;
}

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
vector<int> dx = {-1, -1, -1, 0, 0, 1, 1, 1};
vector<int> dy = {-1, 0, 1, -1, 1, -1, 0, 1};

int main () {
    int n, k; cin >> n >> k;
    vector<int> p(n);
    rep(i, n) cin >> p[i];
    sort(all(p));
    int ans = 0;
    rep(i, k) ans += p[i];
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3616
#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 <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

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

    int n, m;
    cin >> n >> m;
    vector< vs64 > c(8, vs64(n, 0));

    vs64 data(3);
    rep (i, n)
    {
        cin >> data[0] >> data[1] >> data[2];
        rep (j, 8)
        {
            int temp = j;
            rep (k, 3)
            {
                c[j][i] += (temp & 1 ? data[k] : -data[k]);
                temp >>= 1;
            }
        }
    }

    rep (j, 8)
    {
        sort(c[j].begin(), c[j].end(), greater<s64>());
    }

    s64 ans = 0;
    rep (j, 8)
    {
        s64 sum = accumulate(c[j].begin(), c[j].begin() + m, (s64)0);
        ans = MAX(ans, sum);
    }

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



Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

using ll = long long;
using ull = uint64_t;
using P = pair<int, int>;
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

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

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

    int N, M, R;
    cin >> N >> M >> R;
    vector<int> r(R);
    for(int i = 0; i < R; ++i){
        cin >> r[i];
        --r[i];
    }
    vector<vector<int>> dist(N, vector<int>(N, INF));
    for(int i = 0; i < N; ++i)  dist[i][i] = 0;
    for(int i = 0; i < M; ++i){
        int a, b, c;
        cin >> a >> b >> c;
        --a, --b;
        dist[a][b] = c;
        dist[b][a] = c;
    }
    for(int k = 0; k < N; ++k){
        for(int i = 0; i < N; ++i){
            for(int j = 0; j < N; ++j){
                chmin(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    vector<int> p(R);
    for(int i = 0; i < R; ++i)  p[i] = i;
    int ans = INF;
    do{
        int S = 0;
        for(int i = 0; i + 1 < R; ++i){
            S += dist[r[p[i]]][r[p[i + 1]]];
        }
        chmin(ans, S);
    } while(next_permutation(p.begin(), p.end()));
    cout << ans << endl;
}

Measured memory_bytes: 3828
#include <algorithm>
#include <functional>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <bitset>
#include <climits>

#define all(c) (c).begin(), (c).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)
#define fr first
#define sc second

const int INF=100000000;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
using namespace std;
typedef long long ll;

int K,R,L;
double P,E,T;

inline double dfs(int depth,double r,double l) {
    //cout<<string(depth,'\t');printf("%.8f %.8f\n",l,r);
    if(depth==K) {
        //string(depth,'\t');printf("%.8f %d\n",(l+r)/2,abs(T-(l+r)/2)<=E);
        return 1.0*(abs(T-(l+r)/2)<=E);
    }
    double h=(l+r)/2;

    if(l<T-E) return 0;
    if(r>T+E) return 0;

    double ret=0.0;
    if(h>=T) {
        ret+=dfs(depth+1,r,h)*(1-P);
        ret+=dfs(depth+1,h,l)*(P);
    }
    else {
        ret+=dfs(depth+1,r,h)*(P);
        ret+=dfs(depth+1,h,l)*(1-P);
    }

    return ret;
}


int main() {
    cin>>K>>R>>L;
    cin>>P>>E>>T;

    printf("%.20f\n",dfs(0,R,L));
    return 0;
}

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

using namespace std;

int main(){
	int a,b,c,k;
	cin >> a >> b >> c;
	cin >> k;
	int ans = max(a,max(b,c));
	for(int i=0;i<k;i++){
		ans*=2;
	}
	ans += a + b + c - max(a,max(b,c));
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
 
////////////// Prewritten code follows. Look down for solution. ////////////////

#define fs first
#define sc second
#define pb push_back
#define len(x) ((int)(x).size())
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

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

const ll LINF = 1e18;
const int INF = 1e9;
const int MOD = 1e9+7;

/// command for char arrays with spaces -> scanf(" %[^\n]", text);
 
////////////////////////// Solution starts below. //////////////////////////////

const int N = 1e3+5;
vi adj[N];

int main(){
	fastio;
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < m; i++){
		int a, b;
		cin >> a >> b;
		adj[a].pb(b);
	}

	auto bfs = [&](int source){
		int aux = 0;
		vi vis(n+1, 0);
		vi parent(n+1, 0);
		queue<int> q;
		q.push(source);
		parent[source] = -1;
		bool flag = false;
		while(!q.empty()){
			int v = q.front();
			q.pop();
			vis[v] = 1;
			for(int u : adj[v]){
				if(!vis[u]){
					parent[u] = v;
					q.push(u);
				}else if(u == source){
					aux = v;
					flag = true;
					break;
				}
			}
			if(flag) break;
		}
		vi ans;
		if(!aux) return ans;
		for(int v = aux; v != -1; v = parent[v]){
			ans.pb(v);
		}
		return ans;
	};

	int szNow = INF;
	vi ans;
	for(int i = 1; i <= n; i++){
		vi cycle = bfs(i);
		if(!cycle.empty() and len(cycle) < szNow){
			ans = cycle;
			szNow = len(ans);
		}
	}
	cout << (len(ans) == 0 ? -1 : len(ans)) << '\n';
	for(int x : ans) cout << x << '\n';
	return 0;
}

Measured memory_bytes: 384
/*
dp(i) = the sum of the subsequence ending at ith element and whose sum is maximum
ans = max(dp[i]) for all i
dp(1) = beauty(1)

dp(i) = max{
               1.beauty(i) 
               2.max(beauty(i)+dp(j) for all j<i and hj<hi) over all j 
      }


*/ 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct flower{
    ll hi;
    ll bty;
};
ll solve(vector<flower>& v , ll n){
   vector<ll> dp(n+1);
   map<ll , ll>meaningful;
   dp[1] = v[1].bty;
   meaningful[v[1].hi] = dp[1];
   ll ans = dp[1];
   for(int i=2 ; i<=n ; i++){
       dp[i] = v[i].bty;
       auto it = meaningful.lower_bound(v[i].hi + 1);
       if(it != meaningful.begin()){
           it--;
           dp[i] += it->second;
       }
       meaningful[v[i].hi] = dp[i];
       it = meaningful.upper_bound(v[i].hi);
       while(it != meaningful.end() && it->second <= dp[i]){
           auto temp = it;
           temp++;
           meaningful.erase(it);
           it = temp;
       }
       ans = max(ans , dp[i]);
   }
   return ans;
}
int main() {
    ll n;
    cin>>n;
    vector<flower>v(n+1);
    for(ll i=1 ; i<=n ; i++){
         cin>>v[i].hi;
    }
    for(ll i=1 ; i<=n ; i++){
       cin>>v[i].bty;  
    }
    cout<<solve(v , n);
    return 0;
}


Measured memory_bytes: 17408
#include <bits/stdc++.h>
#ifdef DEMETRIO
#define deb(...) fprintf(stderr,__VA_ARGS__)
#define deb1(x) cerr << #x << " = " << x << endl
#else
#define deb(...) 0
#define deb1(x) 0
#endif
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,ThxDem=b;i<ThxDem;++i)
#define SZ(x) ((int)x.size())
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;

ll dp[100005],h[100005];

ll f(ll x){
	if(x<0)return 1000000000;
	if(x==0){
		return 0;
	}
	if(dp[x]>=0){
		return dp[x];
	}
	dp[x]=min(f(x-1)+abs(h[x-1]-h[x]),f(x-2)+abs(h[x-2]-h[x]));
	return dp[x];
}

int main(){FIN;
	ll n; cin>>n;
	memset(dp,-1,sizeof dp);
	fore(i,0,n)cin>>h[i];
	cout<<f(n-1);
	return 0;
}


Measured memory_bytes: 3328
package main

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

type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextRuneSlice() []rune {
	return []rune(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func main() {
	sc := NewScanner()
	N := sc.nextInt()
	for i := 1; i <= 9; i++ {
		for j := 1; j <= 9; j++ {
			if i*j == N {
				fmt.Println("Yes")
				return
			}
		}
	}
	fmt.Println("No")
}


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

long long f(long long n, long long k)
{
    if (n > k)
    {
        long long diff = n - k;
        n -= (diff / k) * k;
        if (n > k)
        {
            n = min(n, n - k);
        }
    }
    else if (n == k)
    {
        n = 0;
    }
    else
    {
        n = k - n;
    }
    return n;
}

int main()
{
    long long N, K;
    cin >> N >> K;
    long long ans = N;
    for (int i = 0; i < 2; i++)
    {
        N = f(N, K);
        ans = min(ans, N);
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

H,N = map(int,readline().split())
m = map(int,read().split())
AB = zip(m,m)

INF = 10 ** 18
dp = [INF] * (20000)
dp[0] = 0

for a,b in AB:
    for n in range(H):
        if dp[n+a] > dp[n] + b:
            dp[n+a] = dp[n] + b

answer = min(dp[H:])
print(answer)

Measured memory_bytes: 42476
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <list>
#include <numeric>
#include <stack>
#include <queue>
#include <tuple>
#include <bitset>
#include <map>
#include <math.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
typedef long long ll;
typedef pair<int,int> P;
const int inf = 1012345678;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};

vector<P> p;


int main(){
  int A,B,T;
  cin >> A >> B >> T;
  cout << T/A * B << endl;
}



Measured memory_bytes: 256
import java.util.*;
import java.io.*;
import java.lang.*;

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

        int a = sc.nextInt();
        
        if (a == 0)
            System.out.println("1");
        else
            System.out.println("0");
    }
}

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

using namespace std;

#define LL long long
const int MAXN = (int)2e5+10;

int arr[MAXN];

int main() {
    int n;
    cin >> n;
    int m = n;
    int ans = 0;
    while(m) {
        ans += m%10;
        m /= 10;
    }
    if(n%ans == 0) cout << "Yes\n";
    else cout << "No\n";
    return 0;
}

Measured memory_bytes: 256
[N,K] = list(map(int,input().split()))
H=  list(map(int,input().split()))

#Hを大きい順に並べ替え
H.sort(reverse=True)

#大きい順からK個必殺技
del H[0:K]

#残ったリストの要素の合計
print(sum(H))

Measured memory_bytes: 87372
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,k,p[N];
double ans[N],res;
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&p[i]);
		ans[i]=(1.0+p[i])/2.0;
		ans[i]+=ans[i-1];
	}
	for(int i=k;i<=n;++i)
	res=max(res,ans[i]-ans[i-k]);
	printf("%.7lf\n",res);
	return 0;
}

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

#define endl '\n'
#define lfs cout<<fixed<<setprecision(10)
#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define test cout<<"test"<<endl;
#define fi first
#define se second
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define rep(i,n,m) for(ll i = (n); i < (ll)(m); i++)
#define rrep(i,n,m) for(ll i = (m) - 1; i >= (ll)(n); i--)
using ll = long long;
using ld = long double;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const ll INF = 1e18;
using P = pair<ll, ll>;
template<typename T>
void chmin(T &a,T b){if(a>b)a=b;}
template<typename T>
void chmax(T &a,T b){if(a<b)a=b;}
void pmod(ll &a,ll b){a=(a+b)%MOD;}
void pmod(ll &a,ll b,ll c){a=(b+c)%MOD;}
void qmod(ll &a,ll b){a=(a*b)%MOD;}
void qmod(ll &a,ll b,ll c){a=(b*c)%MOD;}
ll median(ll a,ll b, ll c){return a+b+c-max({a,b,c})-min({a,b,c});}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
template<typename T1,typename T2>
void ans(bool x,T1 y,T2 z){if(x)cout<<y<<endl;else cout<<z<<endl;}  
template<typename T>
void debug(vector<vector<T>>&v,ll h,ll w){for(ll i=0;i<h;i++)
{cout<<v[i][0];for(ll j=1;j<w;j++)cout spa v[i][j];cout<<endl;}};
void debug(vector<string>&v,ll h,ll w){for(ll i=0;i<h;i++)
{for(ll j=0;j<w;j++)cout<<v[i][j];cout<<endl;}};
template<typename T>
void debug(vector<T>&v,ll n){if(n!=0)cout<<v[0];
for(ll i=1;i<n;i++)cout spa v[i];cout<<endl;};
template<typename T>
vector<vector<T>>vec(ll x, ll y, T w){
  vector<vector<T>>v(x,vector<T>(y,w));return v;}
ll gcd(ll x,ll y){ll r;while(y!=0&&(r=x%y)!=0){x=y;y=r;}return y==0?x:y;}
vector<ll>dx={1,0,-1,0,1,1,-1,-1};
vector<ll>dy={0,1,0,-1,1,-1,1,-1};
template<typename T>
vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
template<typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v(ts...))>(a,make_v(ts...));
}
ostream &operator<<(ostream &os, pair<ll, ll>&p){
  return os << p.first << " " << p.second;
}  
int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  ll res=0,buf=0;
  bool judge = true;
  ll n,k;cin>>n>>k;
  vector<ll>point(3);
  rep(i,0,3)cin>>point[i];
  string t;cin>>t;
  auto dp=vec(k,3,0LL);
  string tmp="rsp";
  rep(i,0,n){
    vector<ll>next(3);
    rep(j,0,3){
      rep(o,0,3){
        if(j==o)continue;
        ll p=0;
        if(tmp[(o+1)%3]==t[i])p+=point[o];
        chmax(next[o],dp[i%k][j]+p);
      }
    }
    dp[i%k]=next;
  }
  rep(i,0,k)res+=*max_element(ALL(dp[i]));
  cout<<res<<endl;
  return 0;
}

Measured memory_bytes: 5200
// AOJ 1086 Live Schedule
// 2018.2.4 bal4u

#include <stdio.h>
#include <string.h>

int E[31][16], F[31][16];
int dp[31][51][6];

//#define getchar_unlocked()  getchar()
int in()
{
	int n = 0;
	int c = getchar_unlocked();
	do n = (n<<3)+(n<<1) + (c & 0xf), c = getchar_unlocked();
	while (c >= '0');
	return n;
}

int main()
{
    int C, D, W, X, c, d, w, x, k, ans;
	int se, sf, t;

	while (C = in()) {
		D = in(), W = in(), X = in();

		for (c = 0; c < C; c++) for (d = 0; d < D; d++) E[d][c] = in();
		for (c = 0; c < C; c++) for (d = 0; d < D; d++) F[d][c] = in();

		for (d = 0; d < D; d++) {
			memcpy(dp[d+1], dp[d], sizeof(dp[d]));
			for (c = 0; c < C; c++) {
				se = sf = 0;
				for (k = c; k < C; k++) {
					if (!E[d][k]) break;
					se += E[d][k], sf += F[d][k];
					if (k == c) {
						for (w = sf; w <= W; w++) for (x = 0; x <= X; x++) {
							if ((t=dp[d][w-sf][x]+se) > dp[d+1][w][x]) dp[d+1][w][x] = t;
						}
					} else {
						for (w = sf; w <= W; w++) for (x = 0;  x < X; x++) {
							if ((t=dp[d][w-sf][x]+se) > dp[d+1][w][x+1]) dp[d+1][w][x+1] = t;
						}
					}
				}
			}
		}
		
		ans = 0;
		for (w = 0; w <= W; w++) for (x = 0; x <= X; x++)
			if (ans < dp[D][w][x]) ans = dp[D][w][x];
		printf("%d\n", ans);
	}
	return 0;
}


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

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

    int i = 0;
    while(str[i] != '\0'){
        int j = i + 1;
        while(str[j] != '\0'){
            if(str[i] == str[j]){
                cout << "no" << endl;
                return 0;
            }
            j++;
        }
        i++;
    }

    cout << "yes" << endl;

    return 0;
}

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

int main(){
  vector <int> a={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  int k;
  cin >> k;
  cout << a.at(k-1) << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
 
using ll = long long;
/*
    g++ -std=c++11 test.cpp -o test.out && ./test.out
*/


void solve(){
    int n; cin >>n ;
    int ac = 0;
    int wa = 0;
    int tle = 0;
    int re = 0;
    for(int i = 0; i < n; i++){
        string s; cin >> s;
        if(s == "AC"){
            ac++;
        } else if(s == "WA"){
            wa++;
        } else if(s == "TLE"){
            tle++;
        } else {
            re++;
        }
    }

    cout << "AC x " << ac << endl;
    cout << "WA x " << wa << endl; 
    cout << "TLE x " << tle << endl; 
    cout << "RE x " << re << endl; 
}

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

Measured memory_bytes: 3648
#include <bits/stdc++.h>  // g++ -std=c++14 -o a a.cpp

 using namespace std;

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

 #define rep(i, n) for(int i = 0; i < (n); i++)
 #define repto(i, n) for(int i = 0; i <= (n); i++)
 #define all(c) (c).begin(), (c).end()
 #define uniq(c) c.erase(unique(all(c)), (c).end())
 #define _1 first
 #define _2 second
 #define pb push_back
 #define INF 1145141919
 #define MOD 1000000007
 #define DEBUG(x) cout << #x << ": " << x << endl;

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

 __attribute__((constructor)) void initial() {
     cin.tie(0);
     ios::sync_with_stdio(false);
 }

 int main() {
     string S;
     cin >> S;
     int l = S.length();
     int maxLen = 0;
     int current = 0;
     rep(i, l) {
         if (S[i] == 'A' || S[i] == 'C' || S[i] == 'T' || S[i] == 'G') {
             current++;
         } else {
             maxLen = max(maxLen, current);
             current = 0;
         }
     }
     maxLen = max(maxLen, current);
     cout << maxLen << endl;
 }


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define MAX 1000005
#define MOD (ll)(1e9+7)
#define INF INT32_MAX
#define INFL INT64_MAX
using namespace std;

void solve()	{
	int n;
	cin >> n;
	int a[n];
	int rec[100000];
	memset(rec,0,sizeof(rec));
	for(int i=0; i<n; i++)	{
		cin >> a[i];
		rec[a[i]]++;
		if(a[i]-1>=0)	rec[a[i]-1]++;
		if(a[i]+1<100000) rec[a[i]+1]++;
	}
	int ans=-INF;
	for(int i=0; i<100000; i++)	{
		ans=max(ans,rec[i]);
	}
	cout << ans << endl;
}

int main()	
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t=1;
	//cin >> t;
	for(int i=1; i<=t; i++)	{
		solve();
	}
	return 0;
}

Measured memory_bytes: 4412
#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <array>
#include <cassert>
#include <bitset>
#include <cstdint>
using namespace std;
using LL = long long;


int a, b;

int main() {
	cin >> a >> b;
	cout << max(a + b, max(a - b, a * b)) << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <math.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>

typedef unsigned long long ULLONG;
typedef long long LLONG;
static const LLONG MOD_NUM = 1000000007; //998244353;

template<class _T> static void get(_T& a) {
	std::cin >> a;
}
template<class _T> static void get(_T& a, _T& b) {
	std::cin >> a >> b;
}
template<class _T> static void get(_T& a, _T& b, _T& c) {
	std::cin >> a >> b >> c;
}

static void exec();

int main()
{
	exec();
	fflush(stdout);
	return 0;
}

static void exec()
{
	int N, Q;
	get(N);

	LLONG sum = 0;
	std::map<LLONG, LLONG> ai;
	for (int i = 0; i < N; i++) {
		LLONG a;
		get(a);
		ai[a]++;
		sum += a;
	}

	get(Q);
	for (int i = 0; i < Q; i++) {
		int b, c;
		get(b, c);

		LLONG diff = b * ai[b];
		LLONG plus = c * ai[b];
		ai[c] += ai[b];
		ai[b] = 0;
		sum = sum - diff + plus;
		printf("%lld\n", sum);
	}
}


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

int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  map<ll, int> mp1;
  //map<ll ,int> mp2;
  set<ll> index;
  //vector<int> map(pow(10, 9)+1, 0);
  //vector<vector<int>> index(pow(10, 9)+1);

  rep(i, N){
    cin >> A[i];
    mp1[i + A[i]]++;
  }


  ll ans = 0;
  for(int i = 0; i < N; i++){
    int Aj = i - A[i];
    ans += mp1[Aj];

  }
  cout << ans << endl;
}


Measured memory_bytes: 26672
//by szh
#include<iostream>
using namespace std;

#define pb push_back
#define fi first
#define SZ(x) (int((x).size()))
#define se second
#define ll long long
#define pq priority_queue
#define MP make_pair
#define pii pair<int,int>
#define mod 1000000007
#define debug(x) cerr<<#x<<"="<<x<<'\n'

const int maxn=2e6+10;

int x1,y1,x2,y2;
ll tmp[maxn];

ll inv(ll x,int p) {
	if (p==0) return 1;
	if (p%2==1) return x*inv(x*x%mod,p/2)%mod;
	else return inv(x*x%mod,p/2); 
}

ll f(int x,int y) {
	return tmp[x+y]*inv(tmp[x],mod-2)%mod*inv(tmp[y],mod-2)%mod;
}

ll solve(int x,int y) {
	ll res=0;
	for (int i=1;i<=x+1;i++) (res+=f(i,y))%=mod;
	return res;
}

int main(){
	tmp[0]=1;
	for (int i=1;i<maxn;i++) tmp[i]=(tmp[i-1]*(ll)i)%mod; 
	cin>>x1>>y1>>x2>>y2;
	ll ans=solve(x2,y2)-solve(x1-1,y2)-solve(x2,y1-1)+solve(x1-1,y1-1);
	ans%=mod;
	if (ans<0) ans+=mod;
	cout<<ans;
	return 0;
}


Measured memory_bytes: 15872