akhauriyash/Code-Regression huggingface dataset:
def main():
    import sys
    input = sys.stdin.readline
    class BIT:
        def __init__(self,n):
            self.tree = [0]*(n+1)
            self.size = n
        
        def add(self,i,x):
            while i <= self.size:
                self.tree[i] += x
                i += i&-i
        
        def sum(self,i):
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i&-i
            return s

    N,Q = map(int,input().split())
    bit = BIT(N)
    C = list(map(int,input().split()))
    query = []
    for i in range(Q):
        l,r = map(int,input().split())
        query.append([l,r,i])
    query.sort(key=lambda x: x[1])
    ans = [0]*Q
    #良い玉のindexを1-indexで管理する
    colorMemo = [0]*(N+1)
    cur = 1
    for q in query:
        l,r,j = q
        #良い玉の情報を更新する
        for i in range(cur,r+1):
            c = C[i-1]
            if colorMemo[c]:
                bit.add(colorMemo[c],-1)
            bit.add(i,1)
            colorMemo[c] = i
        cur = r + 1
        ans[j]=bit.sum(r)-bit.sum(l-1)

    for a in ans:
        print(a)
main()


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

pair<int, int> mul(int n) {
  int d1 = n % 10;
  int d2 = n / 10;

  pair<int, int> p = make_pair(d2, d1);

  return p;
}

int main() {
  int m;
  int d;

  cin >> m >> d;

  int ans = 0;

  for(int i=1;i<=d;i++) {
    pair<int, int> p = mul(i);
    if(p.first >= 2 && p.second >= 2 && p.first * p.second <= m) ans++;
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;

#define MOD 1000000007

vector<int> g[100];
vector<bool> visit(100);
vector<int> d(100), f(100);

int cnt = 0;

void dfs(int v) {
  d[v] = ++cnt;
  visit[v] = true;
  for (auto u : g[v]) {
    if (!visit[u]) {
      dfs(u);
    }
  }
  f[v] = ++cnt;
}

int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    int u, k;
    cin >> u >> k;
    u--;
    for (int j = 0; j < k; ++j) {
      int v;
      cin >> v;
      v--;
      g[u].push_back(v);
    }
  }
  for (int i = 0; i < n; ++i) {
    if (!visit[i]) {
      dfs(i);
    }
  }
  for (int i = 0; i < n; ++i) {
    cout << i + 1 << " " << d[i] << " " << f[i] << endl;
  }
  return 0;
}


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

int n, k, ans;
string s;
vector<int> v;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n >> k >> s;
	if(s[0] == '0'){
		v.push_back(0);
		v.push_back(1);
	}else{
		v.push_back(1);
	}
	for(size_t i=1; i<s.size(); ++i){
		if(s[i] == s[i-1]) ++v[v.size()-1];
		else v.push_back(1);
	}
//	for(size_t i=0; i<v.size(); ++i)
//		cout << i << " " << v[i] << "\n";
	for(size_t i=1; i<v.size(); ++i)
		v[i] += v[i-1];
	int m = v.size() / 2;
	if(m <= k) ans = v[v.size()-1];
	else{
		ans = v[2*k];
		for(size_t i=2*k+2; i<v.size(); i+=2)
			ans = max(ans, v[i]-v[i-2*k-1]);
		for(size_t i=2*k+1; i<v.size(); i+=2)
			ans = max(ans, v[i]-v[i-2*k]);
	}
	cout << ans << "\n";
}

Measured memory_bytes: 1020
#include <stdio.h>

int main(){
  long long int n,k;
  scanf("%lld %lld",&n,&k);
  long long int num;
  long long int answer;
  num = n/k;
  answer = num * num * num;
  if(k % 2 == 0){
    num = (n + k/2) / k;
    answer += num * num * num;
  }
  printf("%lld\n",answer);
  return 0;
}


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

P f(int x){
    int a = x%10;
    int b=0;
    while(x){
        b=x;
        x/=10;
    }
    return P(a,b);
}

int main(){
    int n;
    cin >> n;
    map<P,int> freq;

    for(int i=1;i<=n;i++){
        P p = f(i);
        freq[p]++;
    }
    ll ans = 0;
    for(int i=1;i<=n;i++){
        P p = f(i);
        P q = P(p.second,p.first);
        ans+=freq[q];
    }
    cout<<ans<<endl;

}



Measured memory_bytes: 256
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
ips = lambda:input().split()
import collections
import math
import itertools
import heapq as hq

n,m = ma()
s = ips()
t = ips()
dp = [[0]*(m+1) for i in range(n+1) ] # dp[i][j]は s[i],t[j]まで見た時初めて一致する整数列の個数 0idx
tot = [[0]*(m+1) for i in range(n+1) ] #tot[n][m] n,mまで見た時に一致するもの全部, sum dp[0:i+1][0:j+1]
mod=10**9+7
for i in range(n):
    for j in range(m):
        if s[i]==t[j]:
            dp[i][j]=tot[i-1][j-1]+1
        else:
            dp[i][j]=0
        tot[i][j] = (dp[i][j] + tot[i][j-1]+tot[i-1][j] -tot[i-1][j-1])%mod

print((tot[n-1][m-1]+1)%mod)
#print(tot)
#print(dp)


Measured memory_bytes: 132920
import sys
# from collections import defaultdict, deque
# import math
# import copy
from bisect import bisect_left, bisect_right
# import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10 ** 9 + 7
def solve():
    n, k, s = getList()
    if s > 10 ** 6:
        out = 1
    else:
        out = 10 ** 9
    ans = [out for i in range(n - k)] + [s for i in range(k)] #] + [0 for i in range(k-1)]

    print(*ans)

def main():
    n = getN()
    for _ in range(n):
        solve()
if __name__ == "__main__":
    # main()
    solve()


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

int main(){
  int N,sum;
  cin>>N;
  vector<int> vec(N);
  for(int i=0;i<N;i++){
    cin>>vec.at(i);
  }
  sum=0;
  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      if(i>=j){
        continue;
      }
      sum+=vec.at(i)*vec.at(j);
    }
  }
  cout<<sum<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;
#define FOR(i,a,n) for(ll i=(ll)a;i<(ll)n;i++)
#define RFOR(i,a,n) for(ll i=(ll)n-1;i >= (ll)a;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,0,n)
#define ALL(v) v.begin(), v.end()
#define bra(first,second) '(' << first << ',' << second << ')'
ll MOD = 1000000007;
//ll INF = 21474836470000000;
ll INF = 100000000000000000;
long double EPS = 1e-11;
long double PI = 3.141592653589793238;
template<typename T>
void remove(std::vector<T>& vector, unsigned int index){
    vector.erase(vector.begin() + index);
}

using Graph = vector<vector<ll>>;

ll dfs(ll x){
    if(x == 1){
        return 1;
    }
    return dfs(x/2) * 2 + 1;
}

int main(){
    ll H;
    cin >> H;
    cout << dfs(H) << endl;
}



Measured memory_bytes: 256
# include <iostream>
using namespace std;
string a;
void work (void)
{
	if (a[0]=='Y'&&a[1]=='A'&&a[2]=='K'&&a[3]=='I')
	cout<<"Yes";
else cout<<"No";
}
int main (void)
{
	cin>>a;
	work ();
	return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		while(true){
			int n = sc.nextInt();
			int h = sc.nextInt();
			if(n==0 && h==0) break;
			
			HashSet<Integer> set = new HashSet<Integer>();
			String s;
			int a, b, c;
			
			for(int i=0;i<h;i++){
				s = sc.next();
				a = sc.nextInt();
				b = sc.nextInt();
				if(s.charAt(1)=='y'){
					for(int z=1;z<=n;z++){
						c = z*501*501+b*501+a;
						set.add(c);
					}
				}else if(s.charAt(0)=='y'){
					for(int x=1;x<=n;x++){
						c = b*501*501+a*501+x;
						set.add(c);
					}
				}else{
					for(int y=1;y<=n;y++){
						c = b*501*501+y*501+a;
						set.add(c);
					}
				}
			}
			System.out.println(n*n*n-set.size());
		}	
	}	
}

Measured memory_bytes: 51584
n= int(input())
p =[float(x) for x in input().split()]
dp = [[0 for i in range(n+1)]for j in range(n+1)]
dp[0][0]=1.0

for i in range(n):
    for j in range(n):
        dp[i+1][j+1]+=dp[i][j]*p[i]
        dp[i+1][j]+=dp[i][j]*(1-p[i])
an=0
for i in range((n+1)//2,n+1):
    an+=dp[n][i]
print(an)

Measured memory_bytes: 223964
/*                        
                            In the name of Almighty ALLAH
                                    ISLAM IS PEACE

   code from :::::::::::::::::::::
   ******************************* R E S H A D ********************************
   
   
   
    FREE PALESTINE           FREE PALESTINE            FREE PALESTINE           FREE PALESTINE
   
                 FREE PALESTINE           FREE PALESTINE            FREE PALESTINE 
                 
    FREE PALESTINE           FREE PALESTINE            FREE PALESTINE           FREE PALESTINE
   
                 FREE PALESTINE           FREE PALESTINE            FREE PALESTINE
                 
    FREE PALESTINE           FREE PALESTINE            FREE PALESTINE           FREE PALESTINE
   
 
*/
// 90 degree = acos(x)*180/acos(0.0)
/*
bool isPrime(ll n){
    ll sqrtN = (double)sqrt(n);
    for(ll i=3; i<=sqrtN; i+=2){
        if(n%i==0) return false;
    }
    return true;
}
*/

#include <bits/stdc++.h>

#define ll               long long
#define db               double
#define Pi               2*acos(0.0)
#define pb(a)            push_back(a)
#define VI               vector <int>
#define FASTIO           ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ull              unsigned long long
#define all(v)           v.begin(),v.end()
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)

using namespace std;

int main() {
    
    FASTIO;
    
    ll n;
    cin >> n;
    if(n==0) cout << 1 << endl;
    else cout << 0 << endl;
    
    
	return 0;
}

Measured memory_bytes: 3596
import sys

X,N = map(int, input().split())
p = list(map(int, input().split()))

if not (X in p):
    print(X)
    sys.exit(0)

i = 1
while 1:
    if not (X-i in p):
        print(X-i)
        sys.exit(0)
    if not (X+i in p):
        print(X+i)
        sys.exit(0)
    i += 1

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


const int INF = 1000000000;

int main()
{
	int n, m;
	while(cin >> n >> m){

		if(n==0 && m==0)
			break;

		int C[100][100];
		int T[100][100];
		for(int i=0; i<m; i++){
			for(int j=0; j<m; j++){
				if(i==j){
					C[i][j] = T[i][j] = 0;
				}
				else{
					C[i][j] = T[i][j] = INF;
				}
			}
		}

		for(int i=0; i<n; i++){
			int a, b, c, t;
			cin >> a >> b >> c >> t;

			C[a-1][b-1] = C[b-1][a-1] = c;
			T[a-1][b-1] = T[b-1][a-1] = t;
		}

		for(int k = 0;k < m ;k++){
			for(int i = 0;i < m;i++){
				for(int j = 0;j < m;j++){
					if(C[i][j] > C[i][k] + C[k][j]){
						C[i][j] = C[i][k] + C[k][j];
					}
					if(T[i][j] > T[i][k] + T[k][j]){
						T[i][j] = T[i][k] + T[k][j];
					}
				}
			}
		}
		int k;
		cin >> k;
		for(int i = 0;i < k;i++){
			int p,q,r;
			cin >> p >> q >> r;
			if(r == 0){
				cout << C[p-1][q-1] << endl;
			}else{
				cout << T[p-1][q-1] << endl;
			}
		}
	}
	return 0;
}


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

public class Test
{
	public static void Main()
	{
		int n = int.Parse(Console.ReadLine());
		string[] line = Console.ReadLine().Split(' ');
		int[] nums = new int[n];

		int alice = 0;
		int bob = 0;

		for(int i = 0 ; i < n ; i++){
			nums[i] = int.Parse(line[i]);
		}
		Array.Sort(nums);

		bool turnAlice = true;
		for(int i = n-1 ; i >= 0 ; i--){
			if(turnAlice == true ){
				alice += nums[i];
				turnAlice = false;
			} else {
				bob += nums[i];
				turnAlice = true;
			}
		}

		Console.WriteLine(alice - bob);

	}                                                                                                                                                                       
}

Measured memory_bytes: 13140
//Totka hai dosto
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
int32_t main()
{
	string s;
	cin>>s;
	reverse(s.begin(),s.end());
	int n=s.length();
	for(int i=0;i<n;i++)s[i]-='0';
	map<int, int> m;
	
	int sum=0,mul=1;
	sum=s[0]%2019;
	m[sum]++;
	for(int i=1;i<s.length();i++)
	{
		mul*=10;
		mul%=2019;
		sum=(sum+s[i]*mul)%2019;
		m[sum]++;
	}
	
	
	int ans=0;
	for(auto i:m)
	{
		//cout<<i.first<<" "<<i.second<<"\n";
		int x=i.second;
		if(i.first==0)ans=(ans+(x*(x+1))/2);
		else
		ans=(ans+(x*(x-1))/2);
	}
	cout<<ans;
	
	
}

Measured memory_bytes: 3744
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL_DEBUG
  #include "LOCAL_DEBUG.hpp"
#endif
#define int long long

signed main(){

  vector<int> ans;
  auto dfs = [&](auto&& dfs, string s)->void{
    if(s.size() > 9) return;
    for(char i = '0'; i <= '9'; i++){
      char c = s[s.size()-1];
      if(abs(c - i) <= 1){
        string t = s+i;
        reverse(t.begin(),t.end());
        int u = 0, ten = 1;
        for(int j = 0; j < t.size(); j++){
          u += (t[j]-'0') * ten;
          ten *= 10;
        }
        ans.push_back(u);
        dfs(dfs, s+i);
      }
    }
  };
  for(char i = '1'; i <= '9'; i++){
    string s;
    s += i;
    dfs(dfs, s);
  }
  for(int i = 1; i < 10; i++){
    ans.push_back(i);
  }
  sort(ans.begin(),ans.end());

  int k; cin >> k;
  cout << ans[k-1] << endl;
  // for(int i = 0; i < 30; i++){
  //   cout << ans[i] << endl;
  // }

  return 0;
}


Measured memory_bytes: 2424
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.next());
        int tmp = 0;
        int count = 0;
        int maxCount = 0;
        int result = 0;

        for (int i = 1; i <= N; i++) {
            tmp = i;
            while (tmp > 0) {
                tmp = tmp / 2;
                count++;
            }
            if (count > maxCount) {
                maxCount = count;
                result = i;
            }
            tmp = 0;
            count = 0;
        }
        PrintWriter out = new PrintWriter(System.out);
        out.println(result);
        out.flush();
        sc.close();
    }
}

Measured memory_bytes: 35692
N = int(input())
AB = [[int(i) for i in input().split()] for _ in range(N)]

cnt = 0
for i in range(N-1, -1, -1):
    A,B = AB[i]
    A += cnt
    if A % B == 0:
        continue
    cnt += B - (A % B)

print(cnt)

Measured memory_bytes: 21156
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
    int a,b,c,x,ans=0;
    cin >> a >> b >> c >> x;
    for(int i=0;i<=a;i++)
        for(int j=0;j<=b;j++)
            for(int k=0;k<=c;k++)
                if(i*500+j*100+k*50==x)
                    ++ans;
    cout << ans;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair< ll, ll > Pi;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define rep3(i,i0,n) for(int i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
const ll INF = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}
#define all(x) x.begin(), x.end()
#define mp make_pair
bool compare(Pi a, Pi b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}


bool In_map(ll y,ll x,ll h,ll w){
    if(y<0 || x<0 || y>=h || x>=w){
        return 0;
    }else{
        return 1;
    }
}
const vector<ll> dx{1,0,-1,0};
const vector<ll> dy{0,1,0,-1};


int main() {
    ll H,W;
    cin >>H>>W;
    vector<vector<bool>>S(H+2,vector<bool>(W+2));

    rep2(i,H){
        rep2(j,W){
            char c;
            cin>>c;
            if(c=='#'){
                S[i][j]=1;
            }
        }
    }
    rep2(i,H){
        rep2(j,W){
            if(S[i][j]==1){
                rep(dir,4){
                    if(S[i+dx[dir]][j+dy[dir]]){
                        break;
                    }
                    if(dir==3){
                        cout<<"No"<<endl;
                        return 0;
                    }
                }
            }
        }
    }

    cout << "Yes" << endl;


    return 0;
    

}

Measured memory_bytes: 3636
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));



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

	int a, b, c, d;
	cin >> a;
	if (a < 1200)
		cout << "ABC" << endl;
	else
		cout << "ARC" << endl;
	return 0;
}



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

int main() {
  int n; cin >> n;
  if (n==0) cout << 1 << endl;
  else cout << 0 << endl;
  return 0;
}

Measured memory_bytes: 3632
#include <stdio.h>

int A[2000],n;
int solve(int,int);

int main(){
  int q, m, i;
  scanf("%d",&n);
  for(i = 0; i < n; i++) scanf("%d",&A[i]);
  scanf("%d",&q);
  for(i = 0; i < q; i++){
    scanf("%d",&m);
    if(solve(0,m)) printf("yes\n");
    else printf("no\n");
  }

  return 0;
}

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

Measured memory_bytes: 580
n, m = map(int, input().split())

maxNum = 0
minNum = 0

for i in range(m):
    a, b = map(int, input().split())
    if maxNum == 0:
        maxNum = b
    else:
        if maxNum > b:
            maxNum = b

    if minNum == 0:
        minNum = a
    else:
        if minNum < a:
            minNum = a

if maxNum - minNum >= 0:
    print(maxNum - minNum + 1)
else:
    print(0)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll mxn= 2e5+5;
// check for forloop
// intialize variable
// overflow
// go for easy solution
#define mod 1000000007
ll INF = 1000000000000000005LL;
#define endl '\n'
void rishabh(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}
int main(){
    int n;
    cin>>n;
    int arr[mxn]={};
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        arr[x]++;
    }
    int ans=arr[0]+arr[1];
    for(int i=1;i<=(int)1e5;i++){       
        ans=max(arr[i]+arr[i-1]+arr[i+1],ans);
    }
    cout<<ans;
}

Measured memory_bytes: 4308
import java.text.DecimalFormat;
import java.util.function.BiFunction;
import java.util.function.Function;
import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        DecimalFormat df = new DecimalFormat("0.00000000");
        final int R = Integer.parseInt(sc.next());
        double ans = 2.0 * R * Math.PI;
        out.println(df.format(ans));
        
        out.flush();
    }
}

Measured memory_bytes: 35880
#include<iostream>
#include<vector>
#include<string>
#define rep(i, start, end) for (int i = (int)start; i < (int)end; ++i)
#define rrep(i, start, end) for (int i = (int)start - 1; i >= (int)end; --i)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
template<typename T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return 0;}
template<typename T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return 0;}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    int cnt = 0;
    int ans = 0;
    rep(i, 0, 3) {
        if (S[i] == 'R') {
            ++cnt;
        } else {
            chmax(ans, cnt);
            cnt = 0;
        }
    }
    chmax(ans, cnt);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3644
use std::{cmp::{max, min}, collections::{BTreeMap, BTreeSet, VecDeque}};

fn read_line() -> String {
    let mut buffer = String::new();
    std::io::stdin().read_line(&mut buffer).expect("No Line");
    buffer
}
fn read_lines<R, T: Fn(&str)->R> (count: usize, transformer: T) -> Vec<R> {
    let mut buffer = String::new();
    let mut vec = Vec::with_capacity(count);
    for _ in 0 .. count {
        std::io::stdin().read_line(&mut buffer).expect("No Line");
        vec.push(transformer(buffer.trim()));
    }
    vec
}
fn read_value<T: std::str::FromStr>() -> T {
    read_line().trim().parse().ok().unwrap()
}
fn read_values<T: std::str::FromStr>() -> Vec<T> {
    read_line().trim().split(' ').map(|x| x.parse().ok().expect("Can't Parse")).collect::<Vec<T>>()
}
fn read_tabulate<T: std::str::FromStr>(count: usize) -> Vec<T> {
    let mut buffer = String::new();
    let mut vec = Vec::with_capacity(count);
    for _ in 0 .. count {
        std::io::stdin().read_line(&mut buffer).expect("No Line");
        vec.push(buffer.parse().ok().expect("Can't Parse"));
    }
    vec
}
macro_rules! assign {
    () => {};
    ($($token:tt)*) => {
        let mut iter = read_values::<String>().into_iter();
        assign_iter!(iter, $($token)*);
    };
}
macro_rules! assign_iter {
    ($iter:expr) =>{};
    ($iter:expr,) =>{};
    ($iter:expr, $id:ident:$t:tt $($tail:tt)*) => {
        let $id: $t = $iter.next().unwrap().parse().ok().expect("Can't Parse");
        assign_iter!($iter, $($tail)*);
    };
    ($iter:expr, mut $id:ident:$t:tt $($tail:tt)*) => {
        let mut $id: $t = $iter.next().unwrap().parse().ok().expect("Can't Parse");
        assign_iter!($iter, $($tail)*)
    };
}
fn main() {
    assign!{
        n: usize
        apple_limit: usize
    }
    let initial_price = read_values::<i32>();
    let mut max_diff = 0;
    let mut prev_min = i32::max_value();
    for &i in &initial_price {
        prev_min = min(prev_min, i);
        max_diff = max(max_diff, i - prev_min);
    }
    let max_diff = max_diff;
    let mut prev_min = i32::max_value();
    let mut count = 0;
    for &i in &initial_price {
        prev_min = min(prev_min, i);
        if i - prev_min == max_diff {
            count += 1;
        }
    }
    println!("{}", count);
}


Measured memory_bytes: 3396
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <iomanip>
#include <stack>
#include <queue>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define mod 1000000007
using ll = long long;
using namespace std;

int main(){
  int A, B, C, X;
  cin >> A >> B >> C >> X;
  int ans = 0;
  for(int a=0;a<=A;a++){
    for(int b=0;b<=B;b++){
      for(int c=0;c<=C;c++){
        if(500*a+100*b+50*c==X) ans++;
      }
    }
  }
  cout << ans << endl;
  return 0;
}


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

using namespace std;

namespace {

    typedef double real;
    typedef long long ll;

    template<class T> ostream& operator<<(ostream& os, const vector<T>& vs) {
        if (vs.empty()) return os << "[]";
        os << "[" << vs[0];
        for (int i = 1; i < vs.size(); i++) os << " " << vs[i];
        return os << "]";
    }
    template<class T> istream& operator>>(istream& is, vector<T>& vs) {
        for (auto it = vs.begin(); it != vs.end(); it++) is >> *it;
        return is;
    }

    int N;
    vector<string> W;
    bool input() {
        cin >> N;
        if (N == 0) return false;
        W.clear(); W.resize(N); cin >> W;
        return true;
    }

    bool check(int i) {
        const vector<int> a = {5, 7, 5, 7, 7};
        int j = 0;
        int c = 0;
        while (j < 5) {
            c += W[i].size();
            if (c < a[j]) {
                i++;
            } else if (c == a[j]) {
                i++;
                j++;
                c = 0;
            } else {
                assert(c > a[j]);
                return false;
            }
        }
        return true;
    }

    void solve() {
        for (int i = 0; i < N; i++) {
            if (check(i)) {
                cout << i + 1 << endl;
                return;
            }
        }
        assert(false);
    }
}

int main() {
    while (input()) solve();
    return 0;
}

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

#define rep(i,n) for(long long int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(long long int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(long long int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define Abs(a,b) max(a,b)-min(a,b)
#define YES(condition) if(condition){cout << "YES" << endl;}else{cout << "NO" << endl;}
#define Yes(condition) if(condition){cout << "Yes" << endl;}else{cout << "No" << endl;}
#define Cout(x) cout<<(x)<<endl
#define POSSIBLE(condition) if(condition){cout << "POSSIBLE" << endl;}else{cout << "IMPOSSIBLE" << endl;}
#define Possible(condition) if(condition){cout << "Possible" << endl;}else{cout << "Impossible" << endl;}
#define possible(condition) if(condition){cout << "possible" << endl;}else{cout << "impossible" << endl;}
#define Size(n) (n).size()

typedef long long ll;


using namespace std;

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


long long int n,cnt=0,ans=0,a,b,c,d,cmp,cmpp,m,h,w,x,y,sum=0,pos,ma[ohara];
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};

//-------------------------↓↓↓↓↓↓------------------------

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

      
      cin >> w >> h >> n;
      pair<ll,ll> p[ohara];
      rep(i,n){
        cin >> x >> y;
        ans = max(ans,y);
        p[i] = make_pair(x,y);
      }
       sort(p,p + n);
      ma[n - 1] = p[n - 1].second;
      rrrep(i,n - 2,0){
        ma[i] = max(ma[i + 1],p[i].second);
      }
      rep(i,n){
          cnt = p[i].first + ma[i + 1];
          ans = min(ans,cnt);
      }
      Cout(ans);
     

       
return 0;
}



Measured memory_bytes: 19648
//abc113_d2.cpp
//Thu Jun 11 20:06:00 2020

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define INTINF 2147483647
#define LLINF 9223372036854775807
#define MOD 1000000007

using namespace std;
using ll=long long;
typedef pair<int,int> P;

int main(){
	ll h,w,k;
	cin >> h >> w >> k;

	ll dp[101][8];
	for (int i=0;i<101;i++){
		for (int j=0;j<8;j++){
			dp[i][j] = 0;
		}
	}
	dp[0][0] = 1;
	for (int i=0;i<h;i++){
		for (int j=0;j<(1<<(w-1));j++){
			int flag = 1;
			for (int k=1;k<w-1;k++){
				if (j>>k&1 && j>>(k-1)&1){
					flag = 0;
					break;
				}
			}
			if (flag){
				for (int k=0;k<w;k++){
					if (k<w-1 && j>>k&1){
						dp[i+1][k] = (dp[i+1][k]+dp[i][k+1])%MOD;
					}else if (k>0 && (j>>(k-1))&1){
						dp[i+1][k] = (dp[i+1][k]+dp[i][k-1])%MOD;
					}else {
						dp[i+1][k] = (dp[i+1][k]+dp[i][k])%MOD;
					}
				}
			}
		}
	}

	cout << dp[h][k-1] << endl;
//	printf("%.4f\n",ans);
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

using namespace std;

int main() {
    int n;
    cin >> n;
    int p[n];
    rep (i, n) cin >> p[i];
    int ans = 0;
    rep (i, n-2) {
        if ((p[i] < p[i+1] && p[i+1] < p[i+2]) || (p[i] > p[i+1] && p[i+1] > p[i+2])) {
            ans++;
        }
    }
    cout << ans << endl;
}



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


typedef long long ll;

const int MXN = 1e5, INF = 1e9;
const bool scale = true;
int dist[MXN], ptr[MXN], src, dest, lim = 1;

struct Edge {
    int to, rev, f, cap;
};

vector<Edge>G[MXN];

void add_edge(int v, int u, int c, int r = 0) {
    G[v].push_back({u, (int)G[u].size(), 0, c});
    G[u].push_back({v, (int)G[v].size(), 0, r});
}

bool bfs() {
    queue<int> q({src});
    fill(dist, dist + MXN, -1);
    dist[src] = 0;
    while (!q.empty() && dist[dest] == -1) {
        int v = q.front(); q.pop();
        for (auto e: G[v]) {
            int u = e.to;
            if (dist[u] == -1 && e.f < e.cap &&
                (!scale || e.cap - e.f >= lim)) {
                dist[u] = dist[v] + 1;
                q.push(u);
            }
        }
    }
    return dist[dest] != -1;
}

int dfs(int v, int f) {
    if (v == dest || !f) return f;
    for (int &i = ptr[v]; i < G[v].size(); i++) {
        Edge &e = G[v][i];
        int u = e.to;
        if (dist[u] != dist[v] + 1) continue;
        if (int df = dfs(u, min(f, e.cap - e.f))) {
            e.f += df;
            G[u][e.rev].f -= df;
            return df;
        }
    }
    return 0;
}

ll dinic() {
    ll mf = 0;
    for (lim = (scale ? (1 << 30) : 1); lim > 0; lim >>= 1) {
        while (bfs()) {
            fill(ptr, ptr + MXN, 0);
            while (ll pushed = dfs(src, INF))
                mf += pushed;
        }
    }
    return mf;
}


int main() {
    int n, m;
    cin >> n >> m;
    
    src = 0;
    dest = n - 1; 
    
    while (m--) {
        int v, u, cap;
        cin >> v >> u >> cap;
        add_edge(v, u, cap);
    }
    
    cout << dinic() << endl;
}



Measured memory_bytes: 6304
#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
typedef pair< int64 , int64 > Pi;
 
int N, W, H, x[100000], y[100000];
int cpx[100000], cpy[100000];

 
int main()
{
  scanf("%d %d", &W, &H);
  scanf("%d", &N);
  for(int i = 0; i < N; i++){
    scanf("%d %d", &x[i], &y[i]);
    cpx[i] = x[i], cpy[i] = y[i];
  }
  int lowx = 0, highx = 1 << 30;

  sort( x, x + N);

  sort( y, y + N);

  int center = (N - 1) / 2;
  int64 ret = 1LL << 60, xx, yy;
  for(int i = center; i < center + 3; i++){ // 一緒になりそうなところ
    for(int j = center; j < center + 3; j++){ // 一緒になりそうなところ
      int64 dist = 0LL, big = 0LL, cost;
      for(int k = 0; k < N; k++){
        cost = llabs( x[i] - cpx[k]) + llabs( y[j] - cpy[k]);
        dist += cost * 2;
        big = max( cost, big);
      }
      dist -= big;
      if(ret > dist){
        ret = dist;
        xx = x[i];
        yy = y[j];
      }
    }
  }
  cout << ret << endl;
  cout << xx << " " << yy << endl;
}

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

using namespace std;

int main() {
	char m[10],st[150],c1[32]={' ','E','P','C','D','I','K','R','F','O','S','T','L',39,',','.','?','A','H','W','X','Y','Z','-','B','G',
	             'J','M','N','Q','U','V'};
	char da1[32][9]={"101","110","111","0101","0001","0111","0110","1000","01001","00101","00110","00111","00100",
		             "000000","000011","010001","000001","100101","010000","000010","10010010","10010011","10010000",
					 "10010001","10011010","10011011","10011000","10011001","10011110","10011111","10011100","10011101"};
    int d[256],i,j,k,a,b,c;
	for (i=0;i<26;i++) d['A'+i]=i;
	d[' ']=26; d['.']=27; d[',']=28; d['-']=29; d[39]=30; d['?']=31;
	while (gets(st)!=NULL) {
		c=0;
		for (i=0;i<strlen(st);i++) for (j=16;j>0;j/=2) {
			m[c++]=((d[st[i]] & j)==0) ? '0' : '1'; m[c]='\0';
			b=0;
			switch(c) {
              case 3: a=0; b=2; break;
			  case 4: a=3; b=7; break;
			  case 5: a=8; b=12; break;
			  case 6: a=13; b=19; break;
			  case 8: a=20; b=31; break;
			}
			if (b>0) for(k=a;k<=b;k++) if (strcmp(m,da1[k])==0) { cout << c1[k] ; c=0;}
		}
		cout << endl;
	}
	return 0;
}

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

int main(){
    int n;
    while(cin>>n){
        if(n==0) break;
        char c[n];
        int cnt[26]={};
        int m=0;
        bool flag=false;
        for(int i=0;i<n;i++){
            cin>>c[i];
        }
        int g=0;
        for(int i=0;i<n;i++){
            cnt[c[i]-'A']++;
            if(m<cnt[c[i]-'A']){
                m=cnt[c[i]-'A'];
                g=c[i]-'A';
                
            }
            int t=0;
            for(int j=0;j<26;j++){
                    if(j!=g){
                        t=max(t,cnt[j]);
                    }
                }
                if(m>t+n-i-1) {
                    char ans=g+'A';
                    cout<<ans<<" "<<i+1<<endl;
                    flag=true;
                    break;
                }
        }
        if(flag) continue;
        cout<<"TIE"<<endl;
    }

}


Measured memory_bytes: 3076
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;

ll modpow(ll a, ll b, ll p = 998244353){
    if(b == 0)  return 1;

    if(b % 2 == 0){
        ll d = modpow(a, b/2, p);
        return (d*d) % p;
    }else{
        return (a%p * modpow(a, b-1, p)) % p;
    }
}

const int mod = 998244353;

int main(){
    int n, k, a;
    cin >> n >> k >> a;
    vector<int> v(k-1+n+1, 0), acc(k-1+n+1, 0);
    a = (ll)a * modpow(100, mod-2, mod) % mod;
    int invn = modpow(n, mod-2, mod);
    for(int i = 1; i <= n; i++) v[i] = invn;
    acc[1] = v[1];
    for(int i = 2; i <= k-1+n; i++){ 
        int bef = acc[min(i-1, k-1)] - acc[max(0, i-1-n)];
        if(bef < 0) bef += mod;
        bef = (int)((ll)bef * a % mod * invn % mod);
        v[i] = (v[i] + bef)%mod;
        acc[i] = (acc[i-1]+v[i])%mod;
    }
    int ans = 0;
    for(int i = k; i <= k-1+n; i++) ans = (ans + v[i])%mod;
    cout << ans << endl;
    return 0;
}


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

int main() {
	int ans=0, n;
	string s,t;
	cin >> s;
	cin >> t;

	n = s.length();

	for (int i = 0; i < n; i++) {
		if (s[i] != t[i]) {
			ans++;
		}
	}
	
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 3844
#pragma GCC optimize("O3")
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#include<set>
#include<vector>
#include<sstream>
#include<queue>
#include <iomanip>
#include <fstream>
#include<unordered_set>
#include<stack>
#include <map>
#include<unordered_map>
#include<time.h>
#include <chrono>
constexpr auto INF = 9223372036854775807;
typedef long long int ll;
typedef unsigned long long int ull;
typedef unsigned long int ul;
#define f(i,a,b) for(ll i=(ll)a;i<(ll)b;i+=1)
#define rf(i,a,b) for(ll i=(ll)a;i>=(ll)b;i-=1)
#define endl '\n'
#define N 1000000007 // prime modulo value 
#define all(x) x.begin(),x.end()
using namespace std;
#define MAX 1000001 
#define M 998244353
ll inverse(ll n)
{
	ll modu = M;
	ll m = modu;
	ll a = 0, b = 1;
	if (modu == 1)
		return 0;
	while (n > 1)
	{
		ll quo = n / modu;
		ll temp = modu;
		modu = n % modu, n = temp;
		temp = a;
		a = b - (quo * a);
		b = temp;
	}
	if (b < 0)
		b += m;
	return b;
}
int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	ll a, b;
	cin >> a >> b;
	ll ans = -1;
	f(i, 1, 3000)
	{
		ll tax = (i * (0.08));
		ll tax2 = (i * (0.1));
		if (tax == a && tax2 == b)
		{
			ans = i;
			break;
		}
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define ll long long
#define rep2(i,a,b) for(int i=a;i<=b;++i)
#define rep(i,n) for(int i=0;i<n;i++)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define tii tuple<int,int,int>
#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>>
#define pb push_back
#define edge(v,a,b) v[a].pb(b);v[b].pb(a);
ll MOD=1e9+7;
#define INF 2*1e9
#define N 1000010
#define MAX_V 900010
using namespace std;
ll pow1(ll n,ll x){
  ll res=1;
  rep(i,x)res*=n;
  return res;
}
main(){
    ll n,k;
    cin>>n>>k;
    if(k%2){
        cout<<pow1((n/k),3);
    }
    else{
        k/=2;
        cout<<pow1((n/k+1)/2,3)+pow1((n/k)/2,3);
    }
}

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

int N,L;
int main(void){
  cin>>N>>L;
  int sum=0;
  int min=abs(L);
  int minv = L;
  for(int i=0;i<N;i++){
    sum+=L+i;
    if(abs(L+i)<min){
      min=abs(L+i);
      minv = L+i;
    }
  }
  cout<<sum-minv<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>

using namespace std;
int n,a[100+5],x,y,h;
int main()
{
  scanf("%d",&n);
  for(int i=1;i<=n;i++){scanf("%d",&a[i]);h+=a[i];}
  scanf("%d",&n);
  for(int i=0;i<n;i++)
  {
    scanf("%d%d",&x,&y);
    printf("%d\n",h-a[x]+y);
  }
  return 0;
}

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

int main(int argc, char const *argv[])
{
    int n,k,ans=0;
    cin>>n>>k;
    int v[n];
    for(int i=0;i<n;i++)
        cin>>v[i];
    sort(v,v+n);
    for(int i=0;i<k;i++)
        ans+=v[i];
    cout<<ans<<endl;
    
    return 0;
}


Measured memory_bytes: 3600
//
// Created by Leo Chen on 2019-08-28.
//
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int i = 1;
    while(true) {
        i = i * 2;
        if(i > n) {
            i = i / 2;
            break;
        }
    }
    cout << i << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int bubbleSort(int *, int);

int main(){
  int A[100];
  int N,sw,i;

  scanf("%d",&N);
  for(i=0;i<N;i++){
    scanf("%d",&A[i]);
  }

  sw = bubbleSort(A, N);

  for(i=0;i<N;i++){
    printf("%d",A[i]);
    if(i<N-1)printf(" ");
  }
  
  printf("\n");
  printf("%d\n",sw);
  
  return 0;
}

int bubbleSort(int A[], int N){
  int i=0,j,temp,sw,flag;
  flag=1;
  sw=0;
  while(flag){
    flag=0;
    for(j=N-1; j>=i+1; j--){
      if(A[j] < A[j-1]){
	temp = A[j];
	A[j] = A[j-1];
	A[j-1] = temp;
	flag=1;
	sw++;
      }
    }
  }
  return sw;
}



Measured memory_bytes: 2128
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define mkp make_pair
#define rep(i,s,f) for(i=s;i<f;i++)
#define db cout<<'h'<<'i'<<endl 
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
#define vi vector<int>
#define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define PI 3.14159265
#define mod 1000000007
#define mod2 998244353
#define space 100005
#define lg 18
//<<fixed << setprecision(9)

int main()
{
    int n,i,j,t;
    boost;

    cin>>n>>t;
    int arr[n+1];
    rep(i,1,n+1)
    {
        arr[i]=t-1+i;
    }
    // sort(arr+1,arr+n+1);

    int ans=0,mn=1e9;

    rep(i,1,n+1)
    {
        ans+=arr[i];
        if(mn>abs(arr[i]))
        {
            mn=abs(arr[i]);
            j=arr[i];
        }
    }
    cout<<ans-j;
    return 0;
}



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

using namespace std;

#define INF 1000007
#define MOD 1000000007
#define int long long int
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define rep(i, n) FOR(i, 0, n)
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
int lcm(int a, int b) { return a / gcd(a, b) * b; }
int mpow(int N, int P, int M) //繰り返し自乗法
{
    if (P == 0)
        return 1;
    if (P % 2 == 0)
    {
        int t = mpow(N, P / 2, M);
        return t * t % M;
    }
    return N * mpow(N, P - 1, M) % M;
}
signed main()
{
    int N, M;
    cin >> N >> M;
    vector<int> X;
    vector<int> dis;
    rep(i, M)
    {
        int a;
        cin >> a;
        X.push_back(a);
    }
    sort(X.begin(), X.end());
    if (N >= M)
    {
        cout << "0" << endl;
        return 0;
    }
    rep(i, M - 1)
    {
        dis.push_back(abs(X[i + 1] - X[i]));
    }
    sort(dis.begin(), dis.end(), greater<int>());
    int ans = 0;
    for (int i = N - 1; i < dis.size(); i++)
    {
        ans += dis[i];
    }
    cout << ans << endl;
}


Measured memory_bytes: 2548
#include<bits/stdc++.h>
using namespace std;
int wq[100003],st[100003];
int mic(int g)
{
    if(g<=0)return 0;
    if(st[g]!=1e9)return st[g];
    st[g]=mic(g-1)+abs(wq[g]-wq[g-1]);
    if(g>1)st[g]=min(st[g],mic(g-2)+abs(wq[g]-wq[g-2]));
    return st[g];
}
int main()
{
    int g,t;
    scanf("%d",&t);
    for(g=0;g<t;g++)
        scanf("%d",&wq[g]),
        st[g]=1e9;
    mic(t-1);
    printf("%d\n",st[t-1]);
    return 0;
}


Measured memory_bytes: 4096
/*************************************************************************
    > File Name: c.cpp
# File Name: c.cpp
# Author : xiaobuxie
# QQ : 760427180
# Email:760427180@qq.com
# Created Time: 2019年09月01日 星期日 20时17分33秒
 ************************************************************************/

#include<iostream>
#include<cstdio>
#include<map>
#include<cmath>
#include<cstring>
#include<set>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define pq priority_queue<int,vector<int>,greater<int> >
ll gcd(ll a,ll b){
    if(a<b) return gcd(b,a);
    return b==0?a:gcd(b,a%b);
}
const int N=1e5+9;
int dp[N];
int a[N];
int main(){
    ll n;
    scanf("%lld",&n);
    printf("%lld",n*(n-1)/2);
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;
import java.lang.reflect.Array;
import java.math.BigInteger;

import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
 
public class Main{
    static long mod=1000000007;
//    static int dx[]={-1,0,1,0};
//    static int dy[]={0,-1,0,1};

    public static void main(String[] args)   throws Exception, IOException{        
        Reader sc = new Reader(System.in);
        PrintWriter out=new PrintWriter(System.out);

//        int n = sc.nextInt();
        long w=sc.nextLong();
        long h=sc.nextLong();
        long x=sc.nextLong();
        long y=sc.nextLong();
        double ans=(double)w*h/2;
        int b=0;
        
        if(w%2==0 && h%2==0 && w/2==x && h/2==y)b=1; 
        
        out.println(ans+" "+b);
        out.flush();
    }

    static boolean validpos(int x,int y,int r, int c){
        return x<r && 0<=x && y<c && 0<=y;
    }

    static void db(Object... os){
        System.err.println(Arrays.deepToString(os));
    }
}
//class P {
//    int id, d;
//    P(int  id, int d) {
//        this.id=id;
//        this.d=d;
//    }
//}

//class P implements Comparable<P>{
//    int a,b;
//    double c;
//    P(int a, int b) {
//    	this.b=b;
//    	this.a=a;
//    	this.c=(double)b/a;
//    }
//
//    public int compareTo(P p){
//        return Double.compare(p.c,c);
//    }
//}

class Reader
{ 
    private BufferedReader x;
    private StringTokenizer st;
    
    public Reader(InputStream in)
    {
        x = new BufferedReader(new InputStreamReader(in));
        st = null;
    }
    public String nextString() throws IOException
    {
        while( st==null || !st.hasMoreTokens() )
            st = new StringTokenizer(x.readLine());
        return st.nextToken();
    }
    public int nextInt() throws IOException
    {
        return Integer.parseInt(nextString());
    }
    public int[] nextIntArray(int size) throws IOException{
        int r[] = new int[size];
        for (int i = 0; i < size; i++) {
            r[i] = this.nextInt(); 
        }
        return r;
    }
    public long[] nextLongArray(int size) throws IOException{
        long r[] = new long[size];
        for (int i = 0; i < size; i++) {
            r[i] = this.nextLong(); 
        }
        return r;
    }
    public long nextLong() throws IOException
    {
        return Long.parseLong(nextString());
    }
    public double nextDouble() throws IOException
    {
        return Double.parseDouble(nextString());
    }
}


Measured memory_bytes: 23124
//ABC106C
#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <math.h>
#include <stdio.h>
#include <climits>
#include <cfloat>
#include <string>
using namespace std;

int main(){
	string s;
	long long int k;
	cin >> s >> k;
	long long int count = 0;
	for(int i=0;i<s.size();i++){
		if(s.at(i) == '1'){
			count++;
			continue;
		}else{
			break;
		}
	}
	if(count < k){
		cout << s.at(count) << endl;
	}else{
		cout << '1' << endl;
	}
	return 0;
}

Measured memory_bytes: 256
n = int(input())
P_n = list(map(int, input().split()))

num = 0
for i in range(n):
  if i == 0 or i == n-1:
    pass
  else:
    if (P_n[i]-P_n[i-1])*(P_n[i]-P_n[i+1]) < 0:
      num += 1
    else:
      pass
print(num)

Measured memory_bytes: 3060
unittest
{
	assert( [ "3 5 2", "3 2 3 4", ".....", ".@..@", "..@.." ].solve == 5 );
	assert( [ "1 6 4", "1 1 1 6", "......" ].solve == 2 );
	assert( [ "3 3 1", "2 1 2 3", ".@.", ".@.", ".@." ].solve == -1 );
}



import std.algorithm;
import std.conv;
import std.format;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.solve.writeln;
}

auto solve( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto h = 0L;
	auto w = 0L;
	auto k = 0L;
	input.front.formattedRead!"%s %s %s"( h, w, k );
	input.popFront;
	auto sy = 0L;
	auto sx = 0L;
	auto gy = 0L;
	auto gx = 0L;
	input.front.formattedRead!"%s %s %s %s"( sy, sx, gy, gx );
	auto css = new dchar[][]( h, w );
	foreach( ref cs; css )
	{
		input.popFront;
		cs = input.front.to!( dchar[] );
	}
	sy--;
	sx--;
	gy--;
	gx--;
	
	auto dsss = dijkstraGridEx( css, k, sy, sx );
	auto ans = dsss[ gy ][ gx ].reduce!min;
	return ( ans == long.max ) ? -1 : ( ans + k - 1 ) / k;
}

// 正のグリッドマップの始点指定最短経路探索（ダイクストラ法）
auto dijkstraGridEx( T, T W = '@' )( T[][] css, long k, long sy, long sx )
{
	import std.container.binaryheap;
	
	auto dsss = new long[][][]( css.length, css[ 0 ].length, 4 );
	foreach( ref dss; dsss )
	{
		foreach( ref ds; dss ) ds[] = long.max;
	}
	dsss[ sy ][ sx ][] = 0;
	auto usss = new bool[][][]( css.length, css[ 0 ].length, 4 );
	
	auto queue = heapify!( ( a, b ) => b[ 3 ] < a[ 3 ] )( [ tuple( sy, sx, 0L, 0L ), tuple( sy, sx, 1L, 0L ), tuple( sy, sx, 2L, 0L ), tuple( sy, sx, 3L, 0L ) ] );
	while( !queue.empty )
	{
		auto fy = queue.front[ 0 ];
		auto fx = queue.front[ 1 ];
		auto ff = queue.front[ 2 ];
		auto fd = queue.front[ 3 ];
		queue.popFront();
		
		if( usss[ fy ][ fx ][ ff ] ) continue;
		usss[ fy ][ fx ][ ff ] = true;
		
		foreach( i, p; [ [ -1, 0 ], [ 1, 0 ], [ 0, -1 ], [ 0, 1 ] ] )
		{
			auto ty = 0L;
			auto tx = 0L;
			auto td = 0L;
			auto tf = i.signed;
			
			if( ff == tf )
			{
				// 前進
				ty = fy + p[ 0 ];
				tx = fx + p[ 1 ];
				td = fd + 1;
				
				if( ty < 0 || css.length <= ty || tx < 0 || css[ ty ].length <= tx ) continue;		// マップ外
				if( css[ ty ][ tx ] == W ) continue;												// 壁
			}
			else
			{
				// 方向転換
				ty = fy;
				tx = fx;
				td = ( fd + k - 1 ) / k * k;
			}
			
			if( dsss[ ty ][ tx ][ tf ] <= td ) continue;
			
			dsss[ ty ][ tx ][ tf ] = td;
			queue.insert( tuple( ty, tx, tf, td ) );
		}
	}
	return dsss;
}


Measured memory_bytes: 185424
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    S=STR()
    sl=len(S)
    for i in range(sl):
        if S[i]=='A':
            cta=i
            break
    for i in range(sl):
        if S[(sl-1)-i]=='Z':
            ctz=sl-1-i
            break
    print(ctz-cta+1)
if __name__ == '__main__':
    do()

Measured memory_bytes: 3516