Жили собі два півники.один працьовитий,а другий ледар.колись завелась там лесичка. є перший,а другому всеодно.нічого мені вона не зробить.потім настала ніч.всі позасинали.а крадійка ока не зімкнула,крадеться непомітно до ледаря.цап! біжить перекидається.другий півник за нею.втекла,нічого за мною повернеться.він змайстрував пастку.чує крадеться,в раз і вона у клітці.питає: -де півник? за подвір*ям відпусти мене,а я заберуся звідсіля.побіг півник визволив ледаря й мовив: -ось бачиш ти на печі грівся із бідою стрівся.зрозумів все ледарь і став працьовитим.
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int N,k;
int a[1000000];
map <pair <int, int>, int> mem;
cin >> N;
//b.reserve(N);
memset(a,0,sizeof a);
//memset(b,0,b.size()*sizeof int);
for (int i=0;i<N;i++)
cin >> a[i];
cin >> k;
for (int i=0;i<k;i++){
int tmp,tmp2,tmp3,tmp4,sum{0};
cin >> tmp >> tmp2;
tmp--;tmp2--;
if (mem.find({tmp,tmp2})!=mem.end()) {cout<< mem[ {tmp,tmp2} ] << endl; continue;}
tmp3=tmp;
tmp4=tmp2;
for(int x=0;x<(tmp4-tmp3)/2+1;x++){
for(int z=0;z<(tmp2-tmp)/2+1;z++){
if (mem.find({tmp,tmp2})!=mem.end()) {sum= (sum+mem[ {tmp,tmp2} ])%998244353; break;}
for(int j=tmp+z;j<=tmp2-z;j++){
sum=(sum+a[j])%998244353;
}}
tmp++;tmp2--;
}
cout << sum << endl;
mem[{tmp3,tmp4}]=sum;
}
return 0;
}
Объяснение: